CSP-S 2025 游记

· · 生活·游记

又一个赛季，就这么开始了。

从八月份开始就在随机写初赛题。感觉绝大多数题目都能看懂它在干什么，似乎之前费很大劲才只能连蒙带猜地填完所有空的试题，现在看也都如此简单。除了洛谷 SCP 的阅读程序 阅读理解（像我这种蒟蒻根本看不懂它在干什么）以及绝少数的试题之外，总的做下来，感觉还是可以的。

我也不知道题目为什么这么水，这很不符合我对 CSP-S 第一轮的想象。

期间打了一场市赛，题目是啥我忘了，T1、T3 都很水，T2 卡了一小会儿然后发现暴力剪枝（应该是这个做法，反正很暴力）可以通过，T4 在考场上推出了线段树优化 dp 但是最后一个大样例死活过不去。故最终未能拿到满分（不过好像是拿了很多的部分分），也未能 AK，不过当时也没有人 AK 啊？

T4 出成这样，有点不符合我对市赛的想象了（以往市赛都是 T1 到 T3 很水，T4 很难，只会打暴力，300+ 收场）。

初赛考试前打了几场信心赛增强信心。感觉题都还可以，难度 CSP-J 左右吧。

九月二十日，初赛现场。

上午看了下 CSP-J 的试题，为什么有两个 33 题？

以及最后一道完善程序 完形填空 为什么原题是黑题？根本不会做。

到初赛考点后随机游走，看到了许多认识的人和不认识的人，随机说了会儿话，然后就进场了。

下发卷子，怎么变成 16 开（我也不知道是几面，好像是单面）印刷了？难评。

怎么题目跟之前做的几套初赛题一样水？不多评价。感觉今年一车人要 AK 了吧。

我是很菜的，没有 AK 过一场初赛，不过感觉这次晋级线会很高吧。

但是 90 多分真的会被卡在晋级线外吗？不可能吧。

出场的时候和同学交流情况，不出意料，他们也都接近 AK 了。然后发现有个勾股数的题目算错了，我只考虑了勾三股四弦五和勾五股十二弦十三，没考虑到勾六股八弦十（为什么我当时没考虑到？）和勾九股十二弦十五（讲真这组勾股数在数学卷子里都很少出现），挂 3 分。

同时在出场前用某种加密方式加密了一下答案，回去估分得分 94，但除了刚才挂的那 3 分外我不知道哪里又挂了 3 分。

然后几天后在机房查成绩时，由于技术手段过于不优秀，导致同时开 Microsoft Edge、Google Chrome，并同时用虚拟机在 Firefox 下访问查询页面查成绩时，都等了好长时间，最后还是虚拟机下的 Firefox 下查到了。

与估分一分不差，94，但怎么一个个分数都比我高，只有我这么蒟蒻吗？

不过 S 组全国前 25\%（即优先晋级线）为什么连 75 都没到？ZJ S 组晋级线为什么连 S 组优先晋级线都没到？是同学实力整体变强了，还是其他人过于问号了？

问号。

十月下旬，机房。

打了一些复赛模拟赛，通常情况下可以写对 T1 和 T2，但是有一次被卡空间导致 T1 fst，具体原因是未将 O(nm) 的空间滚动数组优化到 O(m)。就当攒 rp 了。

复赛当天看一个同学在发关于 stdin=fopen(".in","r"); 的帖子，研究了一下，在 Windows 下这玩意直接 CE，在 NOILinux 下不 CE 但无法正常使用 cin（可以正常使用 getchar 和 scanf，而 cin 会直接无视掉这条命令，从标准输入中读取数据）。

机房里一些同学都报 Linux 了，就我还是 Windows，当然机房里也有一些 Windows 选手的，不过对我而言 Windows 环境和 Linux 环境差别不是很严重，只要能打开命令行并且能用 g++ xxx.cpp -o xxx 编译 C++ 文件，以及有文本编辑器（不过 Windows 下默认的记事本真的不是很好用，代码不会自动缩进）写代码，那么问题通常不大。

十一月一日，路上。

和同学简单预估了一下情况，然后看到了钱塘江。壮观。

基本上都在杭师大仓前恕园 16 号楼，有几个在勤园 13 号楼。我是恕园 16 号楼的。

进去之前，大概还在路上吧，有个同学说要给四个题时间分配 20+40+60+120 然后 AK。我是没这个水平的。不过他很显然不是说他自己，好像他说他也不可能有这个水平 AK CSP-S。应该说的是另外一个人吧。

进恕园 16 号楼之前碰到了几个人，简单聊了几句，就进场了。

当天下午，复赛现场。

开考前还有一段时间，窗帘没拉上，阳光照得有点刺眼。问了下旁边的考生。

“您好，窗帘能不能拉上？”

“我不知道。”

“？”

“我不知道，问监考老师。”

问完监考老师并得到允许之后，把窗帘拉上了。

罚坐了一段时间，等下发压缩包密码。怎么今年套了两个压缩包，没法提前得知试题英文名了。

密码是人杰地灵的拼音夹杂着一些其他的字符。我也忘了是哪些字符了。

怎么里面还有一层密码？

怎么里外两层密码是一样的啊？

开题，怎么没有签到题了？

简单分析了一下，发现 T1 不考虑每个部门最多 \frac{n}2 人的限制可以直接贪，然后注意到如果有部门超限，最多只会有一个，不可能有两个超限。然后把超限部门中次大值减最大值所得差值最大的那些人移到次大部门去，此时超限部门只有 \frac{n}2 人，剩下两个部门加起来只有 \frac{n}2 人，不可能再次超限。这样的解应该是比较优的。

样例全部通过，但我虽然感觉这么搞是对的，T1 要是挂了就挂完了，显然这样 1= 直接没戏。遂写对拍，结果发现造数据的时候没有保证 n 是偶数导致最终程序与暴力输出不一致，发现之后改完数据生成器，一直拍到晚上 6 点多（应该拍到了那个时候），应该都没拍出问题。

看 T2。感觉 k \le 10 就是用来 O(2^k) 枚举对哪些乡村进行城市化改造的，枚举完之后跑最小生成树即可算出答案，但是复杂度略微高了一点。

然后发现，如果一开始对原图 G 做一遍最小生成树得到树 T，那么在进行 O(2^k) 枚举时，在 G 中但不在 T 中的边显然没用，这样复杂度可以略微降一些。

但是还是要跑三四秒。

感觉在 O(2^k) 枚举时，用 Kruskal 跑最小生成树有点费时，遂将其更换为 Prim。前面一开始求树 T 还是用 Kruskal，我不信 CCF 连这都要卡！

换完之后简单测了下大样例，过了，但是还要两三秒。CCF 神机跑的肯定比仓前机子要快，应该可以通过。

此时大概是下午 4 点半前后，看 T3 和 T4。

发现 T4 完全不会做，分析了一会儿 T3，发现 |t_1| \ne |t_2| 显然无解，s_1=s_2 显然无用，记 s_1=l+mi_1+r,s_2=l+mi_2+r,t_1=L+Mi_1+R,t_2=L+Mi_2+R，其中 + 表示字符串拼接，l,r 是 s_1,s_2 的最长公共前后缀，L,R 是 t_1,t_2 的最长公共前后缀，根据题设显然可以求出 l,r,L,R,mi_1,mi_2,Mi_1,Mi_2。那么使用 (s_1,s_2) 这条规则能使 t_1 变成 t_2，必然有 Mi_1=mi_1,Mi_2=mi_2，s_1 是 t_1 的后缀，s_2 是 t_2 的前缀。

然后就可以把 (mi_1,mi_2) 相同的 (s_1,s_2) 归为一类，然后对于一个询问 (t_1,t_2) 仅需查询 (mi_1,mi_2)=(Mi_1,Mi_2) 的 (s_1,s_2) 即可。但是后面又不好做了。

然后想了一会儿发现要使 s_1 是 t_1 的后缀，s_2 是 t_2 的前缀，s_1+*+s_2 一定是 t_1+*+t_2 的子串，其中 * 是一特殊字符。然后问题就变成了 t_1+*+t_2 里出现了多少次 s_1+*+s_2（因为每个 s_1+*+s_2 最多出现一次，可以发现这是对的），这可以用 AC 自动机维护。

？根本没写过 AC 自动机，只是听说过这个算法而已。

想想单字符串匹配可以用 KMP 做，然后开始将 KMP 扩展到字典树上，发现是对的，然后开始写。

同时也想到了 T3 基于哈希的 50 分做法，但是并没写。

写 T3 期间（差不多下午 5 点多）把 T4 O(n! \times n) 的暴力写了，测了样例，过了。也曾尝试过思考 s_i=1 的数据点，但假了，遂放弃。

终于把 T3 码完了，感觉字典树上 KMP 还是不难写的。样例 1 过，样例 2 过，样例 3,4 炸。开始瞪大样例，过于困难，偶然发现自己 KMP 计算 next 指针时的一个错误，修改，再测，样例 3,4 仍炸。发现 next 指针还是没算对，再改了几回，样例 4 过，样例 3 炸。此时已经晚上 6 点多，简单检查一下，再尝试继续改，但直到晚上 6 点半收卷前一两分钟，样例 3 还是死活过不去，遗憾离场。

交卷前简单填写了下字节数确认表，天已全黑。

归程

交流了一下。

有人 T1 不会。

有人 T2 因为对 CCF 神机的错误估计导致未能写出正解。

T3 我还以为是怎么了，结果和同学交流了下做法，发现我 KMP 的时候应该以 bfs 的顺序计算 next 指针，我写成 dfs 了！

真的遗憾离场了。

以及后来才知道，T4 n=m 的 4 分很好拿；后来才知道，T2 我那个写法还是会 TLE，正解复杂度比这要少一只 \log……

本以为去年拿过 1=，今年情况应该会好一些。

可看到这种试题，谁又笑得出来呢？

看到 J 组的试题，T1 直接排序后贪心，T2 直接算或者模拟，T3 转成前缀异或和后不难维护，T4 更与当时我被卡空间的那道题很像，基本上不到十分钟就口胡出来了。

我想，今年的 J 组，应该不难 AK 吧……但是 S 组为什么会……

杭城的夜景很美，钱江的壮观也不减来路，但此时此刻，谁又有心情看景呢？

如果市赛大样例过不去，我可以假装市赛的 std 挂了，但这是正赛啊？

如果模拟赛卡空间，我可以说我在为正赛攒 rp，但这本身就是正赛啊，我给什么东西攒 rp 去？

也许我可以说我给 NOIP 攒 rp，但是，

未拿 CSP-S 高分，又哪来的 NOIP 机会呢？

我想，这对于很多人来说，也是一个赛季的结束吧。

查分的前一夜，有人发现可以通过添加申诉的方式提前看到成绩，但我去查的时候，CCF 已经把这个 bug 给修复了。

第二天查分，也许是因为一车人前一夜查过分了，这次网站一点都不堵。

100+80+50+8=238 \text{。}

很遗憾，您的《CSP-S 2025 游记》不符合推荐标准。原因是：338 在哪。。

完了连计算题都不会做了，实际上应该是 238，被我算成 338 了…… 写完这句之后又拿计算器算了一遍。

其实我 T3 代码能过大样例 4，本身又何尝不暗示有奇迹发生？只不过我不知道，这份代码能过特殊性质 B。

我现在也不知道这份代码为什么会通过特殊性质 B，既不会证明它在这种情况下是对的，也不会构造这种情况的 hack 数据让它 WA 掉。有没有大神能够证明或者 hack 一下？

回过神来。

无论如何。

该发生的，都已经发生了，但还未发生的，我们还有机会。

我想，无论如何，在 NOIP 赛场上，乃至将来的一切赛场上，总可以一战翻盘的吧。

刚才的 238 算成 338，我想，虽然今年的 NOIP，基本上我难以拿下 338，但是，脑抽归脑抽，谁说谁没有希望，在将来的某一天，考出自己的 338？

我们所可以自慰的，想来想去，也还是所谓对于将来的希望。

希望是附丽于存在的，有存在，便有希望，有希望，便是光明。

——《记谈话》