CSP2025游记

lunivia · 2025-09-22 11:13:33 · 生活·游记

好笑吗，我不觉得

初赛。

说实话根本没复习。一星期都在摆。初赛训练量为 1/4 套 2024 年真题，还是我做过的。

做了四年的初赛能忘带铅笔，是神人。结果老师给了一个快断的还钝的不行的铅笔给我，应该不至于刷不出来吧。

然后忘记带水杯出考场。

GZ 下大雨真恶心。

自测 78，因为最后一道题看不太懂所以开蒙。怒扣 9 分。

然后过了。分数线不知道。

考试前随便写了个最短路，看着自己两年前就会写的板子如今还在复习我就想笑，两年了一事无成。

买了瓶冰红茶，希望给予我好运。

开题后发现第一题很典，然后光速开写。

花了一点点时间写了个暴力，然后想了一想 a_{i,3}=0 的做法并写出来了。我维护了选择了多少个 a_{i,1} 和 a_{i,2}，维护他们的差值，在大于 \frac{n}{2} 的时候替换成目前差值最小的。

我不知道为什么我能想出来这个东西然后还不会做。自己猜的结论其实和这个也有关系，不知道该说可惜还是活该。

正解维护次大值即可，替换成最大值。由于这样替换后最多的元素依然 \ge\frac{n}{2}，于是替换后的位置的个数 \le\frac{n}{2}，可以保证正确性。实在是太菜了

搞了半天都失败告终，我把目光移到了第二题。（1.5h）

第二题其实是个生成树。Task 1~4 为纯最小生成树，而实际上观察可得这是必要过程。我虽然没复习但是 dsu 和 kruskal 还是会写的。写完之后也没挂。

我观察了特殊性质 A，然而把存在看成了任意，写了一个没有任何意义的部分分。

看到了 k=5。由于最小生成树后没有包括在内的边没有任何意义，于是在接下来的做法中都不需要，剩下的边只有 n-1 条。手算了一下复杂度为 \Theta(m\log m+2^kn\log n) 好像能过 k=5，然后写写写。

结果大样例挂了，对于 k=10 如果不特地卡好像也能过，但是是 WA 了，跑出来的仍然是最小生成树的答案。

很疑惑，找了半天错误点都没找出来，现场心态要炸了。因为我知道这道题跑不出来期望值 1= 就没机会了。

检查了各个位置都没看出来问题，就有点崩溃。3.5h 开了个 D 缓了一缓，C 看了一眼题目太长就没心情读下去。

D 先写了个 n\le10，然后观察了一下不同的特殊性质。 n\le18 提示我 \Theta(2^n) 的复杂度，但是发现维护完之后有很多相同的，而这个容斥我似乎不会做。

现场炸完了，最后 D 好像就 12pts，貌似写了个 m=n。

检查了一下 A 和 B 但没啥进展，C 剩了 10min 没写完暴力。考的很砸。

我回到家重新写的时候发现了 B 的一个小错误，实则是我 a 数组范围开错了，我貌似开成了 [1e4+5][15]，而实际需求则为 [15][1e4+5]。然后没有 RE 和 MLE 提醒我，也算是给自己敲了个警钟了吧，毕竟很少检查数组大小。

本来我秉承着打炸丢人所以不写游记的做法，但是想到了今年是最后一次参加 CSP 了那还是写写吧，不然万一 NOIP 也打炸了那我今年不是像消失了一样？（NOIP2023 和 NOIP2024 都参加了但是都打得不好所以没写，而且我甚至都不知道能不能打 NOIP2025）

这次题目难度应该都在我可做范围内，会补的。

对自己没有信心，或许对 OI 的真正 passion 早已死在了 2023 了吧。从 2024 年后期就真的没有任何兴致搞了，或许上天就是想让我对 OI 的一切幻想死在那时候。

CSP2023：1=，CSP2024：1=，CSP2025：3=？

NOIP2023：2=，NOIP2024：3=，NOIP2025 能进都是个问题。

算了就这样吧。