CSP-S，2025

· · 生活·游记

啊啊，恍惚间就 2025 了啊，也该到面对一切的时候了。

CSP-S 2023，或许只算是接触了一点算法竞赛的我，独自为在比赛结束前调出的 T2 35pts 暴力欢呼。

CSP-S 2024，虽然最终的分数并不高，作为 whk 选手的我也还是拿到了梦寐以求的，闪亮的蓝色钩子，获得了加入曾经传说中的 LA 群的入群资格。

CSP-S 2025，又将发生什么……呢？

进场，还算快速地写完了 T1，开 T2。

因为大量测试点的 m 都很大，于是先猜复杂度是 O(2^k n)。稍微感受了一下，觉得应该可以先处理出最小生成树，然后枚举选择的乡村集合并做生成树上 dp 之类的事情。但是直到四点一刻测大样例的时候才发现假了。这时已经开始急了，CSP NOIP 省选好像都没出现思路假掉的情况。权衡了一下觉得还是先开 T3。首先这个 A 性质好像很可做啊，但是根本写不明白啊。

此时昨晚失眠的影响已经开始显现了，感觉自己已经在昏睡过去的边缘了，好像一切都在向着彻底完蛋的边缘倾斜啊……

好想哭，怎么办怎么办。

反正 WC 肯定已经没了，在混沌之中还是决定先拼到一等再说。仔细想了想之后发现 T2 直接枚举选定的乡村，并把这 nk 条边加到原图的最小生成树里跑 kruskal 即可做到 O(2^k nk \log(nk))；进一步地，考虑枚举乡村集合并由较小集合转移过来，因为小集合的生成树边数不超过 n + k，而新加入的边只有 n 条，故每次就只需要对 O(n) 条边跑 krukal 了，复杂度是 O(2^k n \log n) 的，写了一下发现极限数据要跑 2.5s，不过感觉还是能拿 80 的，拼上 T3 T4 最低档的暴力，就是 220+eps 了吗……

但在拼暴力的时候突然想到，T2 在枚举集合后，我们可以不直接对边集排序，而是在保证合并的两类边都有序后归并即可！这样复杂度就变成了 O(2^k n \alpha(n)) 的了，至少有一定过的道理是不是。写完之后发现极限数据要跑 1.8s，但在卡常的过程中发现原来是 \text{sort} 忘删了。/cf

因为拼暴力的过程中还出现了各种失误，在把所有代码写完后已经六点多了。再改了几个很奶龙的错误之后就下播了，甚至连 T4 阶乘的 4 分都没拼上，流泪了。

出场之后果然发现自己是认识的人当中的垫底分，但往好了想起码比去年自己的分数高是不是。/ll

不多说了，就先写这么多吧。训练了一年之后发现还没有去年同省同届的选手强，虚无缥缈的梦真该醒了。明年就要以高中生的身份面对这一切了，赶紧现实一点吧。