CSP 2025 游记

· · 生活·游记

初赛

赛前自己做了做 22 年的题，发现 77.5 分，感觉问题不大。

今年没有考 J，下午去绍一，在车上打了一会 CR，因为有点晃打了一会就不打了。虽然我和 ZYZ 的准考证号的差只有 2，但是分到了不同的教室，为啥呢。

去考场，看到了绍一的同学，监考老师居然是我以前在绍一的宿管。先整体看了一眼，果然有交互，还是两道，不过今年居然没有 Linux 命令题？慢慢做，做了 1.5h 把所有题目做完了，居然没有我不会的题。那个等差数列交互题感觉挺好，我一开始看到题只想到了 2\sqrt n。

话说省选之后，我发现坐我右边的那个同学通过了 D2T2 的 C 性质，真是太牛了，让我佩服得五体投地。发现他和我一个考场，考完之后找他拍了一张合影。下去之后见到了绍一的同学，和紊莫还有 ZQX 拍了合影。

出场发现错了两个题，生气了。

9.25：出分了，95 应该可以过初赛吧 QAQ

复赛

出准考证号，和 ZYZ 准考证号只相差 1，但是我是 Linux 他是 Windows，显然不在一起。

赛前一天摆了摆，刷刷 B 站，随便打了点板子，上午继续摆。12:30 出发，出发前吃了碗兰州拉面，感觉完全不如麦当劳。

车开了好久好久，终于到了杭州。带了点巧克力和一瓶生椰拿铁饮料进场，假装可以提神。发了草稿纸后，在纸上写下“一定要 AK”。

2:30 开题，先看了眼前两题，感觉完全不会！我们还是来看 T1 吧，感觉这就是一个模拟费用流，但是我有点忘了怎么模拟，再说这是 CSP-S T1，肯定有简单做法。

思考一下发现如果每个人都选最喜欢不行，肯定有一个选满，枚举哪个选满接下来。花 5min 写了一下发现第二个样例过不去，反复想了 10min 感觉没有问题。于是写了个暴力，发现做法完全正确啊！最后发现调了半天发现数组开了 a[N][2]，绷，这怎么过的第一个样例。

此时已经 0.5h 超出了，赶紧看 T2。瞄了一眼数据范围看到什么 10^6,10，感觉看到要找性质，想了一下发现如果一个乡镇选的话必须连权值最小的边。再看了眼数据范围，发现 n\le 10^4，那好像性质没用，直接来就可以了？

花 10min 写了一个做法，写完才发现怎么是 \mathcal O(nk\log n\cdot 2^k)，最后一个大样例要 2.4s。改成了 \mathcal O(nk^2\cdot 2^k) 的归并，发现还是要 2s，不是哥们，这不对吧。此时是 1h 不到点，先把 T2 丢掉看 T3 去。

感觉 T3 完全简单，马上就会了。想了一下 ACAM 跟 trie 树二维数点哪个好写，由于我好久没写 ACAM 了，有点不会写，于是打算写那个二维数点。

先写了个暴力，写的时候没想灵清，写了 30min。写了发现第三个大样例 WA 了，瞪不出来，这么大的数据怎么调啊！又写了个更加暴力的暴力，硬调，真的急急急！如果是 NFLS 模拟赛这个时候我已经摆了，但是这个他妈是 CSP，怎么办啊！！调了半天，最后发现忘记把前缀翻转了，改了就过了。此时距离开 T3 已经过了 1h 多。

赶紧把后面算答案部分改成 trie 加二维数点，算了一下空间发现开 2\times 10^7 个 vector 要爆空间，还得精细实现。写了半天，反复调试，极度紧张又有点犯晕，每次对比输出结果都满怀希冀，答案却一次次出错。这种感觉让我想起了两年前被 CSP-S2023 T3 创飞的经历，难道这种悲剧今天又要重演了吗？已经过了 2.5h，我却只过了 T1，真的快死了。

终于，在 2h40min 的时候调了出来。有惊无险，测了最后一个样例顺利通过。

急忙去看 T4，感觉完全不会。看到 A 性质，以为答案是 n!，写完发现不过去大样例，才发现有 c_i=0。试图冲击正解，决定如果想到 3h 还不会就拼暴力。

如果确定每个人是否录用会怎么样？这样好像是每个位置有上下界的排列计算，这个可以容斥但是可能没啥前途。又思考了一下别的，好像也不行。于是仔细想了一下，好像容斥是可以的，限制单调不降，直接 DP 就可以了？

上了个厕所，心跳超快。冷静一下，发现好像确实做完了，写了一下，把小样例调对后直接通过了所有样例。此时 3.5h，翻盘了？

别急，T2 还没过。先把归并改成了 \mathcal O(nk\log k)，但是完全没有变快。不过还发现一个事情，就是大样例 2.4s 是因为没有关 fsanitze，关了之后极限数据 1.8s。此时强烈的情绪已经把我冲晕了，完全冷静不下来，没有发现直接把 nk 条边排好序就可以把 log 去掉。思考了几下，发现记录每个集合的边集可以 \mathcal O(nk\alpha(n)\cdot 2^k)，但是空间也是这个，算了一下好像没有超过 512MB。于是写写写，发现极限数据还是要 1.4s。

已经没时间了，只能丢掉，检查了几遍文件就结束了。

出场之后跟 hcy 交流了一下，发现我的做法直接把多余的边丢掉就是 \mathcal O(n\alpha(n)\cdot 2^k)，我草！在大巴上还发现了一件事，我算空间是当 int 算的，但是一条边有 3 个 int，算了一下空间刚好超过 512MB，彻底死了。

回到县里已经八点多了，吃了个麦当劳回家。在家里复现了一下 T2，果然 80，加了几行代码改成 \mathcal O(n\alpha(n)\cdot 2^k) 就过了，哈哈。CSP-S T2 没过，要被嘲笑一辈子了。

预期得分：100+80+100+100=380。

唉算了，不挂分就行，380 应该也说过得去。只求千万别挂分！！

Mortidesperatslav 说要跟我面基，在出校门的时候找到了他，拍了一张合照，哦耶。

upd on 11.5：出分了，T3 挂了 30，难过。

实际得分：100+80+70+100=350。

CSP 只过了两个题，比去年还要少，怎么办？？