CSP-S 2025游记

Day 0

周五一早 7 点起床，然后坐火车到天津，下车后打车到酒店。酒店没有抽纸且早餐极其敷衍，差评！

点了一份吉野家吃，吃完之后小睡一下。

睡醒后，开始考前热身训练。找了今天的 2 道羊蹄，1 道茶，1 道之前做过的数学题，一道火车上看到的洛谷的黄题，然后还有一道 2022 年 CSP-S 的 T1，准备从这几个题里面选三四道做一下。

下午先是花了 20 分钟把洛谷黄写了，是个简单 DP，完成对拍后提交一发入魂。之后考虑到考前不适合打击信心，于是做了羊蹄中简单的那道，是个博弈论，我最开始看错了数据范围，先用 DP 去做的，写到一半发现时空都过不了，但是猜结论怕猜错，所以还是先把 DP 写完了，等会儿可以对拍，之后手玩样例发现似乎只要有奇数就是先手必胜，和 DP 对拍了一下发现没问题，提交，一发 AC。

晚上又点了吉野家，简单吃了个晚饭，然后骑电动车去考点南开大学逛了逛。南开大学门口的小吃车真的多，有种回到聊城大学门口的感觉，真可惜北京不允许有这种存在。回来路上实在是馋，去小吃车买了两根炸淀粉肠。

晚上回来之后，写了下 2022 CSP-S 的 T1，之所以做这个题，是因为我觉得今年的 S 组应该不会那么签，可能会一道题都无法完整做出来，所以要做好面对困难的准备。我之前这个题写的 55 分暴力，现在拿过来继续想，发现容易进一步想到预处理所有的最短路，然后枚举中间的 B 和 C，去快速找距离不超过 k + 1 的 A 和 D，统计答案。暴力去做的话时间是 $O(n^3)$，但是我们发现其实只关心离 B 距离 k + 1 以内的前 3 大的点就好了，这样就一定不会重复，写好之后发现多一个 log 只能 85 分，去掉 log 之后就成功 AC 了。整体上感觉今天状态正常，脑子转得不是很快但是执行力很强，失误也比较少。

洗洗澡睡觉，准备第二天的考试！

Day 1

早晨不到 7 点就醒了，然后找前台要早餐，催了两次结果 8 点半才送过来，只有一包牛奶、一根火腿肠和一个面包，太乐了。

吃完早饭，上午打了几个模板，比如 exgcd、二分图匹配以及 tarjan，其他的模板就不管了。写完模板之后，快速浏览了一下之前记录的好题集锦以及考前打的几场模拟赛的赛时发挥情况，总结了一些要点转发到自己的手机上。然后尝试躺床上补觉，可惜睡不着，10 点半点了个外卖，结果 11 点半才送到，吃了一下饭，等到 12 点半就从酒店出发了，顺道买了士力架和巧克力。

我 1 点 10 分左右就到了考场门口，不让进，一直到 1 点 45 左右才能开始进。进去之后我把两个系统都试了一下，发现 kaoshi 文件夹在 NOI Linux 虚拟机中可以在 /mnt/hgfs 访问。建好文件夹，打好对拍框架，测试了一下两个系统里的编译运行和 debug，感觉没问题。

今年打的主要目标是拿 S 一等，进阶目标是达标 6 级，考前我正常发挥的话，基本上是不可能低于天津的一等线的，然后基本上也能超过 6 级线 10-20 分，考虑到考场的 debuff，所以我还是围绕拿 S 一等指定的战术，求稳，不追求完整做出来任何一道题，只要拿到充足的部分分就好，然后还有一点就是注意到自己考场上码力总共也就只能写六七百行代码，所以想到一个部分分未必要马上写，可以再想想之后再写，防止写错或者写太多无用的代码导致思考时间不够，这一点是我从前几次模拟赛中总结出来的对我比较有用的一个策略。只要开始写代码，那么就是前期准备完全做好，现在要一招制敌。

过了一小会儿就 2 点 25 了，老师通过系统发放试题，解压密码人杰地灵，有趣。

开始看题，首先 T1 明显是一个 DP 或者贪心题，首先有一个 $O(3^n)$ 的暴力很好写，然后 $n = 200$ 可以写一个三维的 DP 做（压了一维可以被推导出的状态），性质 A 是容易的，相当于只能从第一组里选一半最大的。这个做法目前能拿 60 分。

先想到这里，我就去看 T2 了，T2 有 16 分白给的最小生成树板子，然后性质 A 的意味是我们总可以把城镇升级，这样是白嫖的，并且可以无代价和某个村庄相连，所以本质上还是求最小生成树。接着，我又发现其实 $k$ 并不大，我们强行 $2^k$ 枚举升级哪些城镇，然后求最小生成树就好了，这样就计算全了所有情况。由于边数很多，但有个部分分点数不多，所以可以用 Prim 最小生成树去做。这样理论上能拿 64 分。

T3 是一个字符串题，由于我只会哈希，所以理论上只能拿前两个部分分，但由于哈希不好写，我会根据考场上剩余时间决定写不写第二档部分分，但第一档纯暴力还是很简单的，理论上能拿 10-25 分。

T4 稍微看了一下，8 分的全排列很好写，剩下的性质的话，A 性质看起来是全输出 0 ？但实际上不是，因为有人无理由弃考，稍微想了一下，还是只有 8 分的暴力做法最好搞。

至此，过去了半个小时，我估计了一下理论上目前有 150+ 分能做的题了，于是可以开始写代码了。

我先快速打好了 T1 的暴力和 DP，然后对拍，3 点半的时候对拍通过+大样例通过。

然后写 T2，先快速写了 kruskal 拿第一档分，然后写性质 A 的分数，最后写 $2^k$ 枚举的分数，这个暴力枚举写的时候遇到一点麻烦，写出了一些小 bug，大概用了一段时间才搞定，在 4 点半的时候完成的 T2 已经想出来的 64 分部分分。

接着写 T4，因为我觉得 T4 更无脑，用了 15 分钟左右就搞定了，然后测了几个手造的用例。

4 点 50 了，回过头来写 T3，发现这个暴力匹配其实也不太好写，我大概写+调试到 5 点 20 才搞定这部分。

接下来需要抉择了，是去搞 T1 的正解或性质分，还是搞 T3 的哈希，想了一下，由于代码能力的衰减，我觉得还是写 T1 比较好，于是回头去想 T1 了。

T1 的性质 B 也并不困难，因为第三个显然选了是不优的，所以只能在前两个里面选，而前两个都必须小于等于一半，所以只能是一人一半，我们按照 $a[i][2] - a[i][1]$ 排序，小的一半分到第一组，大的一半分到第二组就好了。至此，我写了一个 70 分的做法，5 点 50 左右对拍觉得应该没问题，于是 T1 就这样了。

回到 T3，我不打算写哈希了，我想写一下性质 B 的做法，这个好像只需要看每个模式的 b 在哪里，两个模式的 b 的位置差，以及左右两边 a 的个数，根据这些信息就可以解决一个 5 分的测试点，结果这个时候有个老师上台讲怎么收卷，扯了一大堆，导致我在写代码时写出了 bug，又花了一会儿来调试和对拍，6 点 10 的时候对拍没问题，最后补了个全输出 0 的骗分（不可以，总司令！）。接下来我就不继续写题了，开始准备提交相关的事项，检查文件名、文件读写、solve 函数、linux 下的运行情况等，然后删除无用文件，在 6 点 27 分时提交了自己的代码。至此，理论得分 70 + 64 + 15 + 8 = 157 分，可能的波动点在于 T3 的纯暴力时间上到底能不能过，但应该总有 140 分以上才对。

民间测试

2 号回到北京之后，把 4 道题的代码都重新复现了一遍，并进行了同样的对拍，发现在洛谷上是 70 + 64 + 15 + 8 = 157 完全符合预期，核桃上是 152 分，T3 少了 5 分，原因是我没看到 $len(t_1) \ne len(t_2)$ 所以挂了 5 分，云斗学院居然拿了 197 分，T3 居然给了 55 分，太水了这数据。

后来发现云斗学院上拉取了整个省的赛时代码进行了评测，我在这组数据下，在 TJ 排并列 30 名，在山东只能排并列 278 名，按照比例的话，TJ 应该是有 120 个左右一等奖，山东有 300 个左右一等奖，我都是可以上线的，但数据过水导致真实性存疑了。但至少，我提交的代码能运行，并且得分均不小于预期，这就挺好了，贷款 TJ 省一+6级了。如果能达标山东这种中强省省一的话，我对这次的发挥就可以打 100 分了，毕竟是第一次打。下次争取能 200+，其实 T1 和 T2 都离 AC 不远了，再给我三个月我可能就能突破这个瓶颈。

出分

11.5 号晚上通过神秘链接查到了分数，官方数据 70 + 64 + 15 + 8 = 157，完美符合预期，在 TJ 应该能稳稳拿到省一，但是能否达标 6 级勾还不好说。

11.6 号晚上云斗学院使用官方数据测了一多半省份，并拉了全国排名，当时是排 4006/19736，去年 S 组全国 2.7w 人，6 级勾给到了 4800 多名，感觉自己还是有希望的。

赛后补题

T1

我想到的方法：

每个人有 3 种选择，在题目的限制下，选不了最大值意味着最大值超过一半了，那次大值就必然后边怎么选都不会超过一半，所以次大值是必然可以选到的。

然后我们就可以考虑按照最大值和次大值的差做一个反悔贪心。具体的反悔贪心逻辑如下：

• 当最大值的组不满时，用最大值。
• 最大值的组满了的时候，我们有两种选择：让当前这个选次大值，或在最大值组中已经存在的人里面，找最大值减次大值最小的那个人，让他换组。由于上面的分析，我们知道这两种选择一定都是合法的（因为最大值组已经满了，另外两个组后边的全选也不可能爆），我们只需要关心这两个决策哪个更优。

具体实现时，我们要维护 3 个小根堆，表示 3 个组中已经存在的人，以最大值减次大值的差值为键，按照顺序枚举人做。

代码实现时有一个小技巧，当我们发现一个组满了的时候，别的组就不可能满了，所以其他的几个堆就无需再维护后边的元素了，只有这个满了的组可能插入和删除元素。

这样并不需要排序，只要用堆维护就好了。

客观来讲，我觉得这个题一定是能评到绿的。

不反悔的话怎么做？

我们按照最大值和次大值的差进行降序排序可不可以呢？

T2

在想出正解之前，我的做法是 $O(2^kn^2)$ 的做法，这个做法之所以慢，是因为处理不了点数太多的情况。

由于边数是 $10^6$，所以还是最好让复杂度和边数有关，于是考虑如何去优化基于 kruskal 的解法。

如果最开始的 $m$ 条边已经排好序了，然后选的 $k$ 个升级点的边也是排好序的，那么好像可以归并，无需重复排序，如果并查集同时使用了路径压缩与按秩合并，复杂度 $O(kn\log n + m\log m + 2^k(n + m) \alpha(n + m))$。这个应该是可以通过 $m = 10^6$ 但 $k = 5$ 的情况的。亲测确实通过了 17-20 这几个测试点。

目前还差 15-16 以及 21-25 没有过，它们的特点是 $k = 10$ 且没有特殊性质。我们上面的做法可以近似看成 $O(2^km)$ 的，继续优化的话要么去掉 $2^k$，要么把 $m$ 变成别的。

我们刚才的做法，每次似乎都要把 $O(m)$ 条原始边的重新跑一遍，这个感觉非常的浪费，或许可以把 $2^k$ 枚举时每次计算的这部分提前出去，这需要我们先对原图求一遍最小生成树，把 $m$ 条边缩减成有用的 $n - 1$ 条边，再和每次枚举时的 $kn$ 条边求 MST，这样复杂度就是 $O(kn\log n + m\log m + 2^kkn \alpha(n))$ 了。

T3

T4

非常后悔的一道题，这个题目其实特殊的分数还挺多的，但是我考场上确实没时间在这上面花更多时间了。

$n \le 10$，直接枚举全排列判断即可。

$n \le 18$，这个范围一看就很像把阶乘优化成指数的状压解法，

$m = 1$，我们可以暴力枚举哪个人是第一个被录取的，然后前面都得是不能被录取的，后边随便，求这个方案数。