CSP-S 2025游记

· · 生活·游记

:::epigraph[……] 黑发不知勤学早，白首方悔读书迟 :::

本文纯人工，无 AI。坐标 SH，初二蒟蒻一枚，文学功底较为蒟蒻，若有字文不顺通的地方还请解谅。本校 OIer 较少。考试时正值期中考试周（校内命卷），抱歉了老师，没法复习了。

Day 0

学校下午的培优课请了假，去考场试机，机子状态不错。敲了一遍线段树模板？好像是的。然后回到家，早早地睡觉了。

Day 1

上午没去 CSP-J，因为没去报。颓废了一个上午，whk 作业一点也不想写，也没兴趣打 OI。CSP-J 考完后水谷，发现大家的评价都是“非常简单”。

吃完午饭，紧急准备了 eps 船黑巧并购买 eps 吨某品牌 9.9 元拿铁。以防出现意外，我选择了热拿铁并装进保温杯。

下午，闪现到考场，碰到了 10^9 个熟人。伴随着杂乱而有力的脚步声，楼梯间里每一个人的眼神都流露出一股杀气，誓在本次 CSP-S 考试中取得比别人更高的分数。我的考场座位号是 2 号，所以进场时，场内空空如也——但这一片空白也即将被我的对手们填满。

机房相比昨天，多了一块块的木制隔板，无声地宣告着“这次考试不同于往常”。拉开椅子，我缓缓屈腿，就座。紧张又兴奋地，忐忑又坚定地，我等待着时间流逝，等待着时间走到那一个瞬间。

略微挑选了一下 PDF 打开方式，最终还是选择了 Edge。划过题面，稍瞥了一眼规则，快速来到了 T1。第一遍看题，大约读懂了题意。但是，教练提醒过我们，T1 不一定是签到题，于是先花 5min 浏览了一遍所有题的题面。看起来 T1/T2/T3 比较可做，那就先开 T1。很快想到了反悔贪心的思路，于是随便打了一坨，样例过了。不急，先在虚拟机里跑一跑。机子不错，虚拟机挺流畅的，不用时就挂起也没什么影响。大样例过了，高兴地奖励了一口热拿铁，棕褐色的液体抚过我的喉咙，在秋日中为我带来一丝暖意。 此时大约过去了 30min。马不停蹄地打开 T2，先是想了 $k$ 有没有不放在指数上的做法，结果都是假的。那好了，$2^k$ 肯定优化不了，就去想怎么快速地算出最小生成树。一边喝拿铁一边想，心路历程大约在[这篇题解](https://www.luogu.com.cn/article/cwjcujif)里面： ::::info 我们考虑先跑出原图最小生成树，缩小 $m$ 至 $n-1$，再枚举加哪些点，每次跑一遍 Kruskal，时间复杂度 $O(m \log m + 2^k nk\log nk)$。带入最大值口算一下，来到了惊人的 $2\times 10^9$ 量级，遂考虑优化。 发现若使用 dfs 而不是二进制枚举，每次就可以在上一次的基础上进行迭代，使边的数量与 $n$ 同阶，此时每次 Kruskal 中的 $k$ 被消去，单次时间复杂度降至 $O(n\log n)$，总时间复杂度 $O(m \log m + 2^k n\log n)$。时间复杂度仍然稍高，考虑继续优化。注意到跑完 Kruskal 的边集总是有序的，不妨对增加的 $k$ 个点的邻边也进行排序，这时我们每次要做的就是对两个有序数组的并进行排序，使用归并排序的思想可以做到 $O(n)$，如果使用按秩合并并查集，就做到了 $O(m \log m + 2^k n\alpha(n))$！ 实现时，考虑到常数问题，我使用了常规并查集，因为 $\log n$ 卡不满。 :::: 好嘛，调完测完已经 2h30min 了。有些紧张，因为测的时候发现手搓的极限数据能在本机上跑 1.2s，有可能挂分。不敢再搞了，去打 T3 暴力。用神秘字符串哈希写了一个 25pts 的 $O(|L|^2)$ 写法，但是……有点假，总之是能被卡到 10pts 的。 最后看 T4。还能怎么办？8pts 到手。 最终估分：$100+[80,100]+[10,25]+8=[198,233]$。 ## Day 出分 好的，233pts，理论最高分，也不知道该哭还是该笑。机房人均 250pts+，不过因为我是机房内年级的严格最小，不算单调队列。遇到了场上会做 T3 的初一群友，好嘛，保留节目还是逃不了。 ## 番外 - 某日自测 CSP-J，用了 $(1,1.5)$ 小时 AK。 - SH 有一人单队了我，七年级，288pts。%%% - SH 同届 rnk11，全国同届 rnk135。本市前 10 名中有 8 名报名在了 efz，喷不了。 - 期中裸考，考试时严重脑抽，数理化 93/91/92，全面崩盘。结果总分 509.5/560，相当一般，可是年级分数普遍偏低，老师定的冲“四校”的线只有 508。 - 面对即将到来的 NOIP，正在尝试冲一等线。 - 最新一次 1000m 测试，$4'12''$，比上一次 $4'35''$ 快了 23s，有些高兴 ~~（虽然还是很拉）~~。 - 坐位体前屈 $+16cm$。 --- :::align{right} **OI 之路，还有很长……吗？** :::