CSP-S2025 游记

· · 生活·游记

懒得复现了，赛时也没拍，感觉会挂很多分。

本人坐标 HN。

预计：100 + 100 + 50 + 20 = 270。

实际：100 + 100 + 50 + 20 = 270。

翻盘了！！！！

Day -?

考号怎么是 748，这么不吉利吗。

Day -1

whk，打摆，没精神，打了板子但是效率极低。

Day 0

上午 J 组没考，认真打板子。（虽然最后一个都没用上）

大概 10 : 30 的时候从家里出发往考场那边赶，没想到这地方这么偏（我是云塘校区），到的时候大概 11 : 30，在那里的学校食堂吃午饭，辣椒炒肉过于好吃了，感觉自己吃多了。

中午 12 : 30 开始睡午觉，躺在床上感觉特别紧张，不过还是睡着了。

13 : 50 左右起来了，在考场门口进行小型面基，进去之后一开始还不让进，吐槽一下座位号居然得在考场外面的墙上面的纸上看，然后还缺了一大堆。

发现旁边是 livedream 认识的同学，放松下来了，进行友好交流，一直聊到开考前最后一分钟了才发现，这个时候我居然一点也不紧张。

开题！

乍一看这个第一题好像很困难，有点方。先把 pdf 刷了一下，这个 T3 空间怎么这么大，题面其实压根没看清，然后还是回去看 T1 了。

然后发现是唐题，首先 n 是偶数所以只会有一个超过一半，所以我们可以直接先按最大的选然后再一个个撤销超过一半的人就做完了，感觉上并不需要证明正确性。

不过还是稍微检查了一下，确定小根堆没有写成大根堆，然后就没看了。 T2 是真的很困难。我一开始特殊性质看错了，先认为有 $48$ pts，然后再去看后面两道题，决定先把 T4 的 $n \le 10$ 写了。 然后我就陷入了沉思，在 T2 和 T3 之间反复横跳，时间过去了一个小时，我没有什么进展。 这时候其实稍微有点急了，我强迫自己冷静下来，毕竟也才过去一小时。重新开始深度思考，发现自己 $k = 0$ 都不会，稍加思考发现自己之前猜的连成链的结论错完了，不过改成最小生成树就对了。 所以 $k = 0$ 就会了，跑 kruskal 就对了。那么暴力的做法也呼之欲出，直接枚举哪些乡镇进行改造再跑 kruskal 可以做到 $O(2^km \alpha(n))$，因为我可以预先排序，然后这个做法加上一点剪枝已经把大样例过了。不过首先复杂度就没对，再看了一眼大样例发现不对劲，数据没顶满，那我还说啥了兄弟。 不过这个做法已经至少有 $64$ pts 了，所以可以再打打暴力，反正赛前觉得能拿 $200$ 就很牛了。 思考了很久，T3 想了个暴力，就是直接哈希匹配然后哈希判断一下除了替换的这一段别的是不是一样，然后复杂度比我想象的劣，有 $O(nL_2)$，只有 $25$ pts，跑得贼慢。 这个时候只剩两个小时，还没上 $200$，有点方了。毕竟我每个题都已经思考过了。不过那个时候我没有心态爆炸，毕竟觉得这个 T2 就差一点应该就能想出来，能想出来我就能赢！ 然后开始严肃思考 T2，$2^k$ 很难优化了，考虑减少边数，想了十分钟想起来一个应该是很常见的结论，就是只有原图的最小生成树里的边才是有用的，这样是 $O(2^knk \alpha(n))$，大概 $10^8$，大样例对了，虽然这个结论我不能证明或者证伪，但是当时的我觉得能过。 然后就感觉如释重负了，还有 1.5h，先回去想 T4 的 A 性质，思考不能还是放弃了，回去想 T3，发现可以换一下匹配对象，就是说首先只有两个询问串不同的部分能匹配才是有用的，所以先处理出不同的一段然后我再拿替换串去匹配这一段，这样复杂度是 $O(qL_1)$ 的，可以过 $q = 1$，不过写得有点挂，严肃调试之后过了大样例。 这下只有 T4 了，其实时间只有半小时了，本来我打算摆了，发现自己会状压的 $n \le 18$，十分钟写对了，这下又多了 $12$ pts。 然后只剩十五分钟了，严肃检查了 freopen 和目录，然后十分紧张的等待考试结束，不是紧张成绩，因为现在我挂一点分也比较难输，除非犯了啥致命错误。突然有点想哭，毕竟赛前这一个月我的发挥都是一坨大的，天天拿机房倒数第一，发挥最好的一次可能居然是在赛场上，本来我都觉得我的 OI 生涯要到此为止了。 至于为什么没有对拍，T1 我觉得没必要，然后后面几题数据我都不会造，那咋办。 考完出来发现自己分数还真可以。开心了，虽然可能挂分但是我不去想了，期中考试在等着我。 晚上吃烤肉，真 tmd 好吃。23 : 00 严肃观看曼联 vs 诺丁汉森林，上半场 1 : 0，然后我妈不让看了。 ### Day 1 我去曼联怎么差点输了？？？？？