CSP-S 2025 游记

· · 生活·游记

人生最后一场 CSP 啦！希望不要是人生倒数第二场 OI 比赛。

考试前一天打颓到半夜是传统了。下午 2:30 开考，我 1:30 到的考场校门外，暂时还进不去，所以就在车上睡了会。

我发现每次中午考试前的午睡我都会有一种“所以我刚才到底睡没睡着？”的感觉，这一次也不例外，感觉眨了下眼睛，一个恍惚，几十分钟就过去了。

但是这一次有我的老父亲明确告诉我，我刚才是睡着了的。所以我终于确定前几年考试我也是睡着了的，也不用像之前一样从进考场学校到开始比赛都一直思考这种奇怪的问题了。

扯远了。

进考场都快开考了才想起来已经有代码收集系统网页了，找了好一会才发现网址写在考场黑板上（wssb），手忙脚乱打开网页的时候已经开考了，赶紧下载和解密题目。

T1 看起来像贪心，直接想正解。

若没有 \frac{n}{2} 限制，直接每组选最大值即可，但是有限制的时候……十分钟想了一堆贪心策略但是一个都没法证明。

该不会是 DP 吧？接着想了五分钟还是觉得应该就是贪心，这个时候才想起来还有特殊性质可以用。

特殊性质 A 是简单的，直接排序后取前 \frac{n}{2} 个即可。

特殊性质 B 是套路的，因为必然有一半组取了第 1 项，另外一半组去了第 2 项，所以考虑调整法。

什么时候让选了 a_{i,1} 的第 i 组和选了 a_{j,2} 的第 j 组交换选择会更优？写出来就是 a_{i,1}+a_{j,2} < a_{i,2}+a_{j,1}

也就是当 i,j 冲突时，若 a_{i,1}-a_{i,2} < a_{j,1}-a_{j,2}，则让第 i 组选择第 2 项，让第 j 组选择第 1 项更优。

所以按照 a_{i,1}-a_{i,2} 将所有组从小到大排序，前一半选择第 2 组，后一半选择第 1 组即可。

特殊性质 C 不是简单的，我一开始项想的是先按照 B 的方法将两个位置合并成一个选择，然后再跟最后的围桌合并得到每组的最终选择，但是想了想发现不太对劲（会漏情况，而且此时两个组之间竞争关系没有那么强）。

然后找性质，发现按照一开始想的“无限制时每组直接取最大值”的方法，将所有组按照最大值所在的位置分类以后，最多只有一类的大小 >\frac{n}{2}，会有组间冲突；其他两组不会有冲突，所以可以无脑直接选最大。

对于冲突的这一类，一定是有 \frac{n}{2} 个选择了最大值（一个类中所有组的最大值都在同一个位置），剩下的只能退而求其次，这样的严格冲突情况恰好就是 B 性质所解决的，所以按照 B 性质排序后挨个选取即可。

大样例全过了，就是不知道会不会挂。

谁 TM 给 T1 降的黄？

T1 用时 50 分钟。

一眼 MST，k 特别小所以放在指数上是可以接受的。

直接暴力的时间复杂度是 O(2^k m(\log m + \alpha(n)))，似乎已经能卡很多分了。

再用一个预排序的方法（提前将边排好序，2^k 次枚举的时候直接忽略没选中的新边）可以把排序的复杂度丢出去，变成 O(m \log m + 2^k m \alpha(n))，好像能卡更多分了。

然后我想把一堆必定会形成的子树提前建出来，这就需要一种局部 MST 算法，好像是 Boruvka 状物？完蛋，不会写。

那么换一种思路，考虑哪些边一定不会被加入？感觉上似乎是“即使所有新边都不加入，也依然不在 MST 中的边”，证明了一下发现应该是对的。

按长度排序后跑 Kruskal，那么对于任意一条边：其前面所有边的端点一定会被合成一个整块，加入新边后合成的整块不可能变小。

所以这条边在没有新边的时候就已经加不进去了（两端就在一个块内），加入新边以后块内点集是原点集的超集，这条边就更不可能被加入了。

推广一下，这个方法也能判断哪些新边是一定不会被加入的。

因为 MST 的边数为 n - 1，所以最终保留下来的边数也是 O(n) 级别的，那么时间复杂度也可以优化成 O(m \log m + 2^k n \alpha(n))，能过全部大样例。

考后听说最后的样例不是极限数据，过了以后仍然有 TLE 的可能性，是真的吗？

今年评测器是神机，根本不慌。

感觉 T1 比 T2 难为什么 T2 反而是蓝？

T2 用时 40 分钟。

《求方案数怎么不取模？》

《这个特殊性质怎么这么怪？》

《这个部分分代码怎么这么难写？》

《这个样例怎么过不了？》

《啊？一个 s 只能用一次吗？》

《怎么这样还过不了样例？这样例有问题吧？》

《艹，不是求方案数。》

《距离考试结束还有 6 分钟》

不幸中的万幸是我在写之前就觉得这题代码很难写，所以先去把 T4 暴力打了……也只打了个暴力……

《O(n^4 2^n) 的状压是什么鬼？》

最后还是只打了个 O(n!) 暴力 8 分走人。

:::info[T3 不保证 \lvert t_{i,1} \rvert = \lvert t_{i,1} \rvert？]

原估分 100+100+25+8=233（好数字），然后……

CCF 甚至连 25 分都不肯给我。

:::

:::info[CCF 变性]

听说今年 CCF 突然变性子了，评测器用了神卡 Intel Core Ultra 9 285K（还有 96 GB 的内存——这是租了谁家的服务器？），那不是 T2 得被一堆人用暴力艹过去？

:::