CSP 2025 游记

· · 生活·游记

坐标 CQ，考点在一中。

day -1

写 whk 作业，做 J 组真题，AK CSP-J 2022、2023。

day 1
上午

7:40 进考场、拍合照。

8:30 开题。
T1 巨水，5 min 秒了。
T2 手推规律公式，时间拖长了一点，20 min 切了。
开 T3。发现居然是异或区间？校内模拟赛中几乎每回必有区间划分题，每回都是 dp。遂 dp 秒了。
开 T4。一开始想到将木棍按长度从小到大排序，然后直接背包 dp。时间复杂度 O(n \times \sum_{i=1}^{n} a_i)，80 pts。

It's time to check!
T1 没什么好检查的，大样例过完完事。
T2 写了另一份正解代码，对拍。n=10,m=10 时过了，但 n=1,m=10 时爆了，改完代码后对拍通过。
T3 大样例通过了，对拍也过了，暂且认为 AC 了吧。
T4 同 T3，也是大样例通过，对拍通过。
2h 搞定。

最后 30 min, 想 T4 正解无果。
出考场，估分 100+100+100+80=380 pts，自以为很高了……
结果发现同学 @lifeiyang1 和 @Aurelia_Veil 两位巨佬 AK 了，在此膜拜不尽。

中午

和 @hardme 在同一家饭馆里吃饭、聊题。

下午

1:40 进考场。2:30 开题。
T1 是一道反悔贪心（类似）的板题，30 min 秒了。

CSP-S T1 如果要考贪心，那大概率是反悔贪心。 ——lhy

没想到还真被他说中了。
开 T2。想了一会，发现可以枚举每个乡村选或不选，再用归并优化与并查集按秩合并优化，遂写出 O(2^k \times (kn \log kn+m \alpha (n))) 的 64 pts 暴力做法。
开 T3。猜到要用 Trie，但不会写。遂 hash 骗 25 pts。
T4 直接不看，暴力骗 8 pts 走人。
此时，还剩 2h。
考虑 T2 的 A 性质，还能骗 8 pts。
距离考试结束还有 1h ,我突然发现 T2 的一个重要性质：

如果一条边在原图的最小生成树中没有被选择，那么它在最终的连接中也一定不会被选择。

遂优化到了 O(2^k \times (kn \log k+n \alpha (n)))，手造极限样例，本地跑了 1.9 s。只能祈祷 CCF 评测机跑快点了。

晚上

打开 ABC，想切两道水题，结果网炸了……
开洛谷，发现 @Aurelia_Veil 居然没做出来 T1，挺意外的。

估分

J 估分：100+100+100+80=380 pts。
S 估分：100+[80,100]+25+8=[213,233] pts。

得分

J：100+100+100+80=380 pts，没挂。
S：100+80+0+8=188 pts，T3 爆了（悲）。

后记

T2 加了一堆卡常与剪枝后在洛谷的官方数据中过了……

还是太菜了，T2 人尽皆知的性质我居然还要想。要是知道了这个性质，早些卡常、剪枝，说不定就过了……

T3 也不知道为何而 WA。也许写错，也许 hash 被卡，也许两者兼之。看着 B 性质，居然没想出最终的解。要是把暴力与 AB 性质都拿到，也许就有 70 pts 了……

T4 的状压 DP 的分也没拿到。

就是这个结果……

望着初三学长的 AK，我只能望而兴叹。