2025-10-23模拟赛总结

liuyi0905 · 2025-10-23 16:23:30 · 生活·游记

前言

666之前连续萎亖次差点亖了

终于发力了一次了好吧😎

成绩 100 + 90 + 80 + 20 = 290 直接班排 rk1 好吧😀

虽然不知道为什么 T2 挂了 10 分，不然就上 300 了啊啊啊 我是责任人。不过 T3 \mathcal{O}(nq) 加玄学小优化卡到 80 分还是挺高兴的😁

A

还是一如既往的有一道签到题好吧，而且是原题😂貌似在遥远的两年前考过

直接递归转移，设 S(l, r, c) 表示将 s[l, r] 变成 c 好串的最小修改次数。

设 m = \frac{l + r}{2}，则 S(l, r, c) 可从这两种方式转移：

• 将 s[l, m] 变为 cc \cdots c，将 s[m + 1, r] 变为 c + 1 好串，即 w + S(m + 1, r, c + 1)。
• 将 s[l, m] 变为 c + 1 好串，将 s[m + 1, r] 变为 cc \cdots c，即 S(l, m, c + 1) + w。

因为每次除以二，所以类似线段树结构，递归一共 \log n 层，时间复杂度 \mathcal{O}(n \log n)。

于是就愉快的 AC 了😚

恭喜可爱的 lzh 同学写了一大堆神秘贪心，成为班上唯一一个没有通过 T1 的人👏

::::success[代码]

#include <bits/stdc++.h>
using namespace std;
int n, v[1 << 18][26];
string s;
int S(int l, int r, int c) {
  if (l == r) return s[l] - 'a' != c;
  int m = l + r >> 1;
  int a = m - l + 1 - (v[m][c] - v[l - 1][c]) + S(m + 1, r, c + 1);
  int b = S(l, m, c + 1) + r - (m + 1) + 1 - (v[r][c] - v[m][c]);
  return min(a, b);
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> s, s = " " + s;
  for (int i = 1; i <= n; i++)
    for (int j = 0; j < 26; j++)
      v[i][j] = v[i - 1][j] + (s[i] - 'a' == j);
  cout << S(1, n, 0);
  return 0;
}

::::

B

题意极其难以理解，样例极其不为严谨😠

甚至样例解释只发到了 QQ 群中😡 要不是上课水 QQ 就看不到样例解释了

::::

唉……要是 T2 过了就 300 分了……😪

C

最开始脑抽了，只想到了 \mathcal{O}(n!) 的暴力😣 后来发现脑抽了，不难发现最优策略是每次选择能删的中最右边的那一个删，可以保证所有能删的全部删完。于是记 c_i = i - a_i，当 c_i < 0 时视为 10 ^ 9，枚举一边计算数量即可。

突然又发现当 x, y \le 5 时，总共最多只有 25 种情况，直接预处理一下，最后输出即可。

哈哈，前 4 个点直接过掉😋 轻松拿捏~

比赛最后 5 分钟没事干，突发奇想，因为对于 c_i < 0 的数对答案没有任何影响，所以考虑先把 c_i < 0 的数全部删掉，只处理剩下的数。因为通过大眼观察法，发现 i \le a_i 的数不会特别多，所以最后可以得到很大的优化 我还以为能过呢

事实证明有很大作用，直接 50 \to 80 😘

::::success[代码]

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, M = 5e3;
int n, m, q, a[N], p[N], c[M][M];
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> q;
  for (int i = 1; i <= n; i++) cin >> a[i], i >= a[i] && (p[++m] = i);
  fill(c[0], c[0] + M * M, -1);
  for (int l, r; q; q--) {
    cin >> l >> r;
    if (l < M && r < M && ~c[l][r]) {
      cout << c[l][r] << "\n";
    } else {
      int x = lower_bound(p + 1, p + m + 1, l + 1) - p;
      int y = upper_bound(p + 1, p + m + 1, n - r) - p - 1;
      int s = 0;
      for (int i = x; i <= y; i++) p[i] >= a[p[i]] && (s += (p[i] - a[p[i]] <= s));
      l < M && r < M && (c[l][r] = s);
      cout << s << "\n";
    }
  }
  return 0;
}

::::

最后发现我是唐氏，这就是责任人题啊，直接线段树二分（或树状数组），随便统计答案啊。痛失 100 分。😫

还是得嘲讽一下 lzh 的 freopen("array3.in", "r", stdin) 好吧😆😆😆

D

可惜了，没写基环树的暴力分，明明那么简单😌

当 n, m \le 8 时，很简单，直接暴力枚举 2 ^ m 种走的边数，对于走了的边建新图，统计出每个点的度数。不过要怎么判断遍历完所有点走回起点呢？🤔 灵机一动，不就是判断每个点的度数是否为偶数即可。于是很快便拿到了 20 分。

基环树的做法更无脑，可惜太懒了😴，没写😯 直接找出基环树中的那个环，判断一下是否包括所有边不就可以了，我是责任人，明明比 n, m \le 8 的还简单😑

甚至暴力+基环树有惊人的 45 分🥵 到底是谁拿到了🤬

::::success[代码（只有暴力）]

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int t, n, m, c[N];
array<int, 3> z[N];
int main() {
  cin.tie(0)->sync_with_stdio(0);
  for (cin >> t; t; t--) {
    cin >> n >> m;
    for (int i = 0; i < m; i++)
      cin >> z[i][0] >> z[i][1] >> z[i][2];
    bool q = 0;
    for (int i = 0; i < (1 << m) && !q; i++) {
      bool l = 1;
      fill(c + 1, c + n + 1, 0);
      for (int j = 0; j < m; j++) {
        auto [u, v, k] = z[j];
        k && (l &= (i >> j) & 1), (i >> j) & 1 && (c[u]++, c[v]++);
      }
      if (l) {
        for (int j = l = 1; j <= n; j++) l &= !(c[j] % 2);
        q |= l;
      }
    }
    cout << (q ? "Yes" : "No") << "\n";
  }
  return 0;
}

::::

其实正解也不算特别难，可以直接缩点然后跑欧拉回路。顺带膜拜一下初一巨佬 syc 场切 T4 orz %%%

后记

又是原题大赛，四道全是 CF 的（话说既然有原题狗狗怎么都没做出 CD，deepseek 太菜了🤨）

xbt 再次 AK 虐全场，还是太超标了 nerf when 🤕

经过两小时终于肝完总结，求赞😻