CSP-S 2025游记

· · 生活·游记

省流：坐标GD，在深圳外国语考试，炸了。

Day 0

14：27，可以动键盘鼠标了，遂立即开始解压缩包（怎么套了两层压缩包），解压密码人杰地灵？？？

看 T1，好熟悉的感觉。细细阅读后发现居然不是签到题，遂爆炸。看到数据范围，直接考虑贪心。先统计一下每个人的最优社团，然后按社团顺序排序每个人的贡献。然后假了，样例1第三组过不去，然后炸了。读了T2，发现是最小生成树，k 很小，但并不明白前 k 个能乡镇改造是什么鬼，直接认为是前 k 个城市改造。继续看T1，一阵推导后发现每个人选的社团要么是贡献最大的要么是贡献次大的，既然前面的贪心假了就反悔一下，开了两个优先队列，写写写，1.5h时过了大样例。

该看T2了。此时人有点破防，因为赛前想着难度应该和去年差不多，这次能一雪前耻拿个300，但情况却不是这样。T2 k 很小，n 也不大，算了一算感觉 O(2^k n\log n) 能过，大概就是枚举状态，每次跑个最小生成树。但脑海里并没有想起什么 O(n\log n) 的最小生成树算法。当时误以为 Prim 就是，想到上午看了板子又忘了十分后悔。又浪费时间乱推了一会。

没办法，先看T3。发现样例很多0？再看性质，感觉就是有可能全0啊，遂全输出0。看了半天题目，并没有看懂替换的意思，以为能替换多次，但不符合样例，过了好一会才明白只能替换一次。多模配似？AC自动机？当时想到了这个，但复杂度不对（以为串长还要再乘个 n），其实就是AC自动机，而且AC自动机板子也忘了，于是没写。

看T4，感觉方案数也有可能是0啊，输出0 ^_^。

在这样下去又要像去年一样拿100分了，于是以退求进，T2用复杂度劣一点的 Kruskal。写写写，并查集写炸过，终于编译通过了，把样例粘贴过去，输出12？打印了一下选边情况，和样例解释一样？怎么样例还要多加一条连 1 的边？？？

重读题，发现城市和乡村是两回事，此时还有 30 分钟，人要报废了。突然发现可以强制选了的乡村必须连边，不干扰答案，代码不难改，又写写写，过了小样例。去测大样例，大大超时，吸取T1的经验，关了同步流，最慢的样例0.5s？我的复杂度是 O(2^k(m+kn\log kn)) 的，怎么过的？？？CCF又出水大样例（愤怒愤怒愤怒）。不管那么多了。

打开虚拟机，全部编译一下，都通过了。时间不够，就不模拟测评了，文件输入输出应该没锅。

最后的几分钟，本来想写一下T4的暴力，但感觉写不完，且并不好写，于是没写。

18：27，GAME OVER!!!

出考场，大佬们都好强%%%。交流后才知道T2的 m 条边只有构成最小生成树的 n-1 条才有用，复杂度可以优化到 O(2^k(n+kn\log kn))，愤怒！！！

Day 1

把T2代码复原了一下，洛谷民间数据 80 pts，感觉CCF数据应该不能再强了。优化了一下，只选 n-1 条边，还是 80 pts！！！开心。

然后写了这篇游记。

And I'm hoping to see and dreaming, The day, We are together.

Fix my Broken Dream. ^_^

The End.