哈尔滨理工大学2025年国庆新生赛第一场

C++语法 R"()" 提供了原始输出，不需要转义字符。

void slu() {
  cout << R"(|_ O
    | | \
   < \)"
       << endl;
}
 
signed main() {
  setIO();
  int tt = 1;
  // cin >> tt;
  while (tt--) {
    slu();
  }
  return 0;
}

观察可得，ans = n * k。

void slu() {
  double n;
  int k;
  cin >> n >> k;
  double ans = n * k;
  cout << ans << endl;
}

signed main() {
  setIO();
  int tt = 1;
  // cin >> tt;
  while (tt--) {
    slu();
  }
  return 0;
}

用 Fibonacci 数列累加，求最小折射次数，使强度 $\ge n$ 。

f_1 = 1, f_2 = 1, f_i = f_{i-1} + f_{i-2} \quad (i\ge3)

循环直到 $f_i \ge n$ ，输出 $i$ 。

void slu() {
  int n;
  cin >> n;
  int a = 1, b = 1;
  int cnt = 1;
  if (n == 1) {
    cout << 1 << endl;
    return;
  }
  while (b < n) {
    int c = a + b;
    a = b;
    b = c;
    cnt++;
  }
  cout << cnt << endl;
}
 
signed main() {
  setIO();
  int tt = 1;
  // cin >> tt;
  while (tt--) {
    slu();
  }
  return 0;
}

遍历 $x \in [L,R]$ ，累加满足个位为 $k$ 或能被 $k$ 整除的数。

void slu() {
  int k, L, R;
  cin >> k >> L >> R;
  int ans = 0;
  for (int i = L; i <= R; ++i) {
    if (i % 10 == k || i % k == 0) {
      ans += i;
    }
  }
  cout << ans << endl;
}
 
signed main() {
  setIO();
  int tt = 1;
  // cin >> tt;
  while (tt--) {
    slu();
  }
  return 0;
}

用 DP 记录每天最后使用的两人组合的最大天数，保证连续两天组合不同。

状态：prev[mask] 表示前一天最后用组合 mask 的最大天数，mask 对应三种组合。
转移：当天可用组合 x：

dpp[x] = \max_{k \ne x} prev[k] + 1

不可用组合继承：

dpp[y \notin td] = \max(prev)

答案：

\max(prev)

void slu() {
  int n;
  cin >> n;
  string sa, sb, sc;
  cin >> sa >> sb >> sc;
 
  V<int> a(n), b(n), c(n);
  for (int i = 0; i < n; i++) a[i] = sa[i] - '0';
  for (int i = 0; i < n; i++) b[i] = sb[i] - '0';
  for (int i = 0; i < n; i++) c[i] = sc[i] - '0';
 
  int prev[4] = {0, 0, 0, 0};
  for (int i = 0; i < n; i++) {
    V<int> td;
    if (a[i] and b[i]) td.pb(0);
    if (a[i] and c[i]) td.pb(1);
    if (b[i] and c[i]) td.pb(2);
    int dpp[4];
    int pre = *max_element(prev, prev + 4);
    for (int j = 0; j < 4; j++) dpp[j] = pre;
    for (auto &x : td) {
      int best = 0;
      for (int k = 0; k < 4; k++) {
        if (k != x) {
          ckmax(best, prev[k]);
        }
      }
      dpp[x] = best + 1;
    }
    for (int i = 0; i < 4; i++) prev[i] = dpp[i];
  }
  cout << *max_element(prev, prev + 4) << endl;
}
 
signed main() {
  setIO();
  int tt = 1;
  cin >> tt;
  while (tt--) {
    slu();
  }
  return 0;
}

组合博弈，用动态规划求每个状态是否必胜。

状态：dp[j][o] 表示当前手里有 j 张 1 号卡和 o 张其他卡时，先手是否必胜。

转移：

先从至少 2 张、最多 k 张不同卡里选取，尝试移除 t 张 1 号卡（nb = j - t），不影响其他卡 (no = o)：

\text{if } !dp[nb][no] \text{ then win = true}

如果有至少 1 张其他卡，还可以选 1 张其他卡 + s 张 1 号卡（s \le k-1）：

nb = j - s, \quad no = o - 1, \quad \text{check } !dp[nb][no]

先手必胜则 dp[j][o] = 1，否则 0。

最终答案：

\text{dp[n][n] ? "Playing" : "Training"}

void slu() {
  int n, k;
  cin >> n >> k;
  V<V<char>> dp(n + 1, V<char>(n + 1, 0));
  for (int i = 0; i <= 2 * n; ++i) {
    for (int j = 0; j <= n; ++j) {
      int o = i - j;
      if (o < 0 || o > n) continue;
      bool win = flase;
      for (int t = 2; t <= min(k, j); ++t) {
        int nb = j - t, no = o;
        if (!dp[nb][no]) {
          win = ture;
          break;
        }
      }
      if (win) {
        dp[j][o] = 1;
        continue;
      }
      if (o >= 1) {
        for (int s = 1; s <= min(k - 1, j); ++s) {
          int nb = j - s, no = o - 1;
          if (!dp[nb][no]) {
            win = ture;
            break;
          }
        }
      }
      dp[j][o] = win ? 1 : 0;
    }
  }
  cout << (dp[n][n] ? "Playing" : "Training") << endl;
}
 
signed main() {
  setIO();
  int tt = 1;
  cin >> tt;
  while (tt--) {
    slu();
  }
  return 0;
}

贪心 + 非相邻约束。

构造斐波那契数列 fib[i]，其中 fib[1]=1, fib[2]=2，后续 fib[i] = fib[i-1] + fib[i-2]。

对于给定的 n，从最大的斐波那契数开始，贪心选取：

如果 fib[i] <= n，选它并将 n -= fib[i]；
由于不能取相邻下标，选取一个数后跳过下一个下标 (--i)。

重复直到 n=0，得到的下标即为收割的瓜田编号。

最终输出时按升序排列。

V<int> fib;
 
void init() {
  fib.pb(0);
  fib.pb(1);
  fib.pb(2);
  while (true) {
    int m = (int)fib.size();
    ll nxt = fib[m - 1] + fib[m - 2];
    if (nxt > inf) break;
    fib.push_back(nxt);
  }
}
 
void slu() {
  int n;
  cin >> n;
  V<int> ans;
  for (int i = sz(fib) - 1; i >= 1; --i) {
    if (fib[i] <= n) {
      n -= fib[i];
      ans.pb(i);
      --i;
    }
    if (n == 0) break;
  }
  sort(all(ans));
  for (int i = 0; i < sz(ans); ++i) {
    cout << ans[i] << ' ';
  }
  cout << endl;
}
 
signed main() {
  setIO();
  init();
  int tt = 1;
  cin >> tt;
  while (tt--) {
    slu();
  }
  return 0;
}

前缀和。

先构造主世界 A 和异世界 B 的前缀和数组 prefA[i], prefB[i]，用于快速求区间和。

对每个查询 (L, R, k)：

区间长度 len = R - L + 1，主世界和 sumA = prefA[R] - prefA[L-1]；
由于时空扭曲律要求 p1 + p2 = k，若 k 是奇数则不可能，因为 p1, p2 都是整数，直接输出 "NO"；
否则 s = k / 2，尝试两种平移：
- 左移：Lp = L - s，右移：Lp = L + s，对应区间 [Lp, Lp + len -1]；
- 如果 Lp 和 Rp 在合法范围内，且 sumB = prefB[Rp] - prefB[Lp-1] == sumA，说明存在奇妙共振，输出 "YES"；
- 否则输出 "NO"。

使用前缀和使区间和计算为 $O(1)$ ，每个查询复杂度为常数，因此总复杂度 $O(n + q)$ 。

void slu() {
  int n, q;
  cin >> n >> q;
  V<int> A(n + 1), B(n + 1);
  for (int i = 1; i <= n; ++i) cin >> A[i];
  for (int i = 1; i <= n; ++i) cin >> B[i];
  V<int> prefA(n + 1, 0), prefB(n + 1, 0);
  for (int i = 1; i <= n; ++i) {
    prefA[i] = prefA[i - 1] + A[i];
    prefB[i] = prefB[i - 1] + B[i];
  }
  while (q--) {
    int L, R;
    int k;
    cin >> L >> R >> k;
    int len = R - L + 1;
    int sumA = prefA[R] - prefA[L - 1];
    if (k % 2 == 1) {
      cout << "NO" << endl;
      continue;
    }
    int s = k / 2;
    bool ok = false;
    for (int i = -1; i <= 1; i += 2) {
      int Lp = L + i * s;
      int Rp = Lp + len - 1;
      if (Lp < 1 || Rp > n) continue;
      ll sumB = prefB[Rp] - prefB[Lp - 1];
      if (sumB == sumA) {
        ok = true;
        break;
      }
    }
    cout << (ok ? "YES" : "NO") << endl;
  }
}
 
signed main() {
  setIO();
  int tt = 1;
  // cin >> tt;
  while (tt--) {
    slu();
  }
  return 0;
}

滑动窗口 + 哈希计数。

我们需要统计连续子数组中恰好包含 $k$ 个不同元素，且长度在 $[l, r]$ 的数量。

定义辅助函数 cntk(a, K, l, r)：统计子数组中最多包含 $K$ 个不同元素，长度在 $[l,r]$ 的数量。

使用滑动窗口 [left, i]，dis 表示窗口内不同元素的数量；
遍历右端点 i：
- 更新哈希表 cnt[val]，维护不同元素数量 dis；
- 如果 dis > K，左端点右移直到 dis <= K；
- 可行左端点区间为 $[low, high]$ ，其中：
  $low = \max(left, 1, i - r + 1), \quad high = i - l + 1$
- 将长度合法的子数组数量累加到结果。

最终答案为：

\text{ans} = cntk(a, k, l, r) - cntk(a, k-1, l, r)

时间复杂度：每个元素进出滑动窗口最多一次，总复杂度 $O(n)$ 。

int cntk(const V<int> &a, int K, int l, int r) {
  if (K < 0) return 0;
  int n = sz(a) - 1;
  unordered_map<int, int> cnt;
  cnt.reserve(n * 2);
  cnt.max_load_factor(0.7);
  int left = 1;
  int dis = 0;
  int res = 0;
  for (int i = 1; i <= n; ++i) {
    int val = a[i];
    if (cnt[val] == 0) ++dis;
    ++cnt[val];
    while (dis > K && left <= i) {
      int v2 = a[left];
      --cnt[v2];
      if (cnt[v2] == 0) --dis;
      ++left;
    }
    int low = max(left, max(1LL, i - r + 1));
    int high = i - l + 1;
    if (high >= low) res += (high - low + 1);
  }
  return res;
}
 
void slu() {
  int n, k, l, r;
  cin >> n >> k >> l >> r;
  V<int> a(n + 1);
  for (int i = 1; i <= n; ++i) cin >> a[i];
  int ans = cntk(a, k, l, r) - cntk(a, k - 1, l, r);
  cout << ans << endl;
}
 
signed main() {
  setIO();
  int tt = 1;
  cin >> tt;
  while (tt--) {
    slu();
  }
  return 0;
}

通过操作 $a_i := \gcd(a_i, a_j)$ ，将数组全部变为相等的数。最终所有数都将变成数组的整体 GCD。

先计算整个数组的 GCD，记作 $g$ ；
将数组每个元素除以 $g$ ，得到新的数组 $b_i = a_i / g$ ；
如果数组中已有 1，那么每次操作可以用 1 转化一个数为 1：
$\text{操作次数} = n - (\text{已有1的数量})$
如果没有 1：
- 需要寻找最短子数组，使得其 GCD 为 1；
- 动态规划：dp[h] 表示当前已经处理的子数组组合能得到 GCD 为 $h$ 的最少步数；
- 对每个元素 val 更新：
  $dp[\gcd(h, val)] = \min(dp[\gcd(h, val)], dp[h] + 1)$
- 找到最小长度 $L$ 使得子数组 GCD 为 1，则总操作次数：
  $\text{ans} = n + L - 2$

时间复杂度： $O(n \cdot M)$ ，其中 $M$ 是数组元素上界。

void slu() {
  int n;
  cin >> n;
  V<int> a(n);
  int g = 0;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    g = gcd(g, a[i]);
  }
  for (int i = 0; i < n; ++i) a[i] /= g;
  int cnt1 = 0;
  for (auto &x : a)
    if (x == 1) ++cnt1;
  if (cnt1 > 0) {
    cout << (n - cnt1) << endl;
    return;
  }
  V<int> dp(M + 1, inf), ndp;
  for (auto &val : a) {
    ndp = dp;
    if (ndp[val] > 1) ndp[val] = 1;
    for (int h = 1; h <= M; ++h) {
      if (dp[h] == inf) continue;
      int ng = gcd(h, val);
      if (ndp[ng] > dp[h] + 1) ndp[ng] = dp[h] + 1;
    }
    dp.swap(ndp);
  }
  int L = dp[1];
  if (L == inf) {
    cout << -1 << endl;
  } else {
    int ans = n + L - 2;
    cout << ans << endl;
  }
}
 
signed main() {
  setIO();
  int tt = 1;
  cin >> tt;
  while (tt--) {
    slu();
  }
  return 0;
}

无限循环的序列，求前 $k$ 项的数字和。

先求数组 $a$ 的和：
$S = \sum_{i=1}^{n} a_i$
计算完整循环次数和剩余部分：
$\text{cycles} = \lfloor k / n \rfloor, \quad \text{rem} = k \bmod n$
总和为：
$\text{ans} = (\text{cycles} \cdot S + \sum_{i=1}^{\text{rem}} a_i) \bmod 998244353$
时间复杂度： $O(n)$ ，只需遍历数组一次。

void slu() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  int sum = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    sum += a[i];
    if (sum >= mod) sum -= mod;
  }
  int cycles = k / n;
  int rem = k % n;
  int ans = ( (cycles % mod) * (sum % mod) ) % mod;
  for (int i = 0; i < rem; i++) {
    ans += a[i];
    if (ans >= mod) ans -= mod;
  }
  cout << ans % mod << endl;
}
 
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int T;
  cin >> T;
  while (T--) slu();
}

按数位分组统计：
- $d$ 位数对应的倍数：
  $l = \lceil 10^{d-1} / n \rceil, \quad r = \lfloor (10^d-1)/n \rfloor$
- 个数为 $cnt = r - l + 1$ ，该组总长度 $len = cnt \cdot d$ 。
找到包含第 $k$ 个字符的组：
- 用累积长度 $sum$ ，如果 $sum + len \ge k$ ，说明目标在当前组。
定位具体倍数及字符：
$\text{offset} = k - sum - 1$ $t = \text{offset} / d, \quad \text{pos} = \text{offset} \bmod d$ $\text{number} = n \cdot (l + t)$
输出 $\text{number}[pos]$ 。

时间复杂度： $O(\text{number of digits})$ ，最多 18 次循环。

void slu() {
  int n, q;
  cin >> n >> q;
  vector<int> pw(19);
  pw[0] = 1;
  for (int i = 1; i <= 18; i++) pw[i] = pw[i - 1] * 10;
  while (q--) {
    int k; cin >> k;
    int sum = 0;
    for (int d = 1; d <= 18; d++) {
      int l = (pw[d - 1] + n - 1) / n;
      int r = (pw[d] - 1) / n;
      if (r < l) continue;
      int cnt = r - l + 1;
      int len = cnt * d;
      if (sum + len >= k) {
        int off = k - sum - 1;
        int t = off / d;
        int pos = off % d;
        int idx = l + t;
        string s = to_string(n * idx);
        cout << s[pos] << endl;
        break;
      }
      sum += len;
    }
  }
}
 
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int T = 1;
  while (T--) slu();
}