2025-10-23模拟赛总结

前言

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 的人👏

代码

CPP

#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 就看不到样例解释了~~

8 : 30 \sim 9 : 00

一段时间内，~~cch 不在~~，大家都在激情讨论 T2 的样例。经过同学们的手动模拟，几乎没有一个人得到了与样例相同的结果，有

21, 24, 26, 27, 28, 30, 31, 32, 36, 38

等各种各样的结果，过了好一会才统一（其实还有部分同学心态崩了）。

我也是脑子一抽，直接想到神秘贪心，发现可以枚举一个分界点

i

，

i

左边的每个数都走一个长度为

1

的小 “Z”，右边的数都包含在一个长度为

n - i

的大 “Z” 里。于是直接 dp 处理左边，后缀和处理右边就可以了。

经过半小时的调试环节，惊喜的通过了全部样例，成为班上第一个通过 T2 样例的同学😊

代码

CPP

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 1e6 + 5;
LL n, a, b, c, d, w[N], s[N][2], p[N];
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> a >> b >> c >> d;
  s[0][1] = 1e18;
  for (int i = 1; i <= n; i++) {
    cin >> w[i];
    s[i][0] = min(s[i - 1][0] + w[i] * a + c, s[i - 1][1] + a + b);
    s[i][1] = s[i - 1][0] + a + b + 2 * d;
  }
  for (int i = n; i; i--)
    p[i] = p[i + 1] + min(w[i] * a + c, a + b + (i == n ? 2 * d : 0));
  LL r = min(s[n][0], s[n][1]);
  for (int i = 1; i <= n; i++)
    r = min(r, min(s[i - 1][0], s[i - 1][1]) + p[i] + (n - i) * d);
  cout << r + (n - 1) * d;
  return 0;
}

测完后，不出所料，直接 WA，挂掉

10

分。正解好像是神秘 DP，如下：

正解

设

f_i

为杀死前

i − 1

关的 boss 的最少用时。

f_{i + 1} = \min(f_{i + 1}, f_i + a_i \times r_1 + r_3 + d)

f_{i + 1} = \min(f_{i + 1}, f_i + \min((a_i + 1) \times r_1, r_2) + d + d + r_1 + d)

f_{i + 2} = \min(f_{i + 2}, f_i + \min((a_i + 1) \times r_1, r_2) + d + \min((a_{i + 1} + 1) \times r_1, r_2) + d + r_1 + d + r_1 + d)

唉……要是 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

😘

代码

CPP

#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

分🥵 到底是谁拿到了🤬

代码（只有暴力）

CPP

#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 🤕

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

2025-10-23模拟赛总结

文章操作

前言

A

B

C

D

后记

相关推荐

评论

2025-10-23模拟赛总结