CSP 2025 游记

· · 生活·游记

整个 OI 生涯都没有 AK 过一次 CSP 初赛才是 OIer 最大的失败。

9.20

J 不会哈夫曼，虽然最后蒙对了，但 97。S 没有题不会，但是挂飞了，仅 89。

看来我只能度过一个相对失败的人生。

11.01

早上吃了自己几个月没吃过的肉夹馍，馍太干了非常难吃，杯子没洗又没法喝水，最后硬撑着吃完两个，非常害怕要因为早饭挂了。

准时进场，先调五分钟 Code Runner。A 是啥，哦好简单，写五分钟写完了，大样例过了。B 有点抽象，哎怎么第一个样例输出反了，哎怎么第二个样例完全不一样啊，哎怎么是从大到小排序啊，哎完蛋了，哎改改就过了，成功花费 15 分钟。C 好像挺难的啊，怎么不送了啊，没事启动大脑，不难想到设 f_i 表示 i 之前的答案且不强制选 i，转移直接找 j 使得 \oplus_{p = j}^{i} a_p = k，直接维护到值域上做完了，8 分钟秒了。D 怎么又这么难，完了只会 n, a_i \leq 500 了，哎好像可以排序把 \max a_i 直接丢掉，那不就背包秒了，10 分钟写完。全部丢到虚拟机里开始跑样例，一通乱搞全都过了，一看时间 9 : 29 : 49，不到一个小时。

完了做太快了没事干了，我能提前离场吗，好像不能。那先别急推一发 exgcd 先，哎怎么假了，不行重推，太好了证出来了，怎么才过去 15 分钟，要不在把之前那道高数大题做一遍，不行啊那个太丑陋了不好算。正好有点困睡觉吧。

半睡半醒到十点多一点，发现 D 写丑了，稍微改了一下继续回去睡，但是这个椅子好劣质，屁股开始酸了。十一点半起床检查目录，摆烂到考试结束，有效答题时长一小时多几分钟。

中午出去吃饭，玩手机，子夜将至好听。明天去白云机场 T3，那要不把虎门北站一起去了吧。

依然准时进场，哎解压完怎么没东西，叫监考员过来了，哦密码输错了，一按 Alt + Tab 发现两个 360 压缩错误页面。A 有点像去年给的贪心，依然需要一个关键结论，但是并不太确定不敢写，看 B，感觉挺送的，要不先写 A 吧。不难想到一个简单的反悔贪心策略，好像能证，手玩样例也过了，那就先写吧。好像维护社团的优先队列里没法直接插入两个差值，只能插入位置，还要手写大小比较，最后写了 3KB 的不可名状物，不管了 15 : 20 测过了 A。

做 B，发现极其类似刚做完的 P3639，甚至更为简单。首先 k \leq 10 肯定枚举改造的乡镇，不难注意到只有在原图最小生成树中的边才可能在后面被用到，于是直接 \mathcal{O}(2^knk\log nk) 做 Kruskal，到这里仅仅才三点半多。发现跑的有点慢，后面那个 \log 太丑陋了，容易想到将排序转化为归并，但是怎么归并 k 个数组呢，聪明的我做过 P1631，想到用优先队列维护 k 个指针，每次去除最小的并将其向后移动丢回去，将 \log nk 优化到 \log k，几乎常数了，并且我实在想不到优化了，运行量 3 \times 10^8 上下，仍然有点悬，到这里已经四点多了。赛后看到两两归并就可以去掉 \log k 之后直接回到普及组了。

开 C，没啥思路，安慰自己这题最多蓝，C 放紫实在不太好。发现一个变换可以掐头去尾，仅保留最左和最右不同位置中间的那一段，一个查询也可以掐头去尾，仅保留不同的一段。我们发现一个变换能用于一个查询至少要保证保留的不同部分变化前和变化后完全相同，这个哈希一下简单做。我们又发现能贡献还有一个条件是该变换被删去的前缀恰好是该查询被删去的前缀的后缀，该变换被删去的后缀恰好是该查询被删去的后缀的前缀，这两个拼起来就是充要条件了。第二个尤为难做，我选择先看特殊性质，B 性质保证了只要长度满足条件就一定是前 / 后缀，二维偏序即可，但是这对整题作用并不大。最终快五点时选择要不你先写写看呢，没有 B 性质的部分直接写 \mathcal{O}(nq)，写完快五点半了，拿下 50pts，开始写 B 性质，写完发现根本过不去，发现没有保证变化部分的哈希值相等，而这个写起来要维护二元组做下标，最终用 map 写了很长，写出一堆弱智错误拼命调，18 : 17 调出来，拿下 70pts。注意到我贪图方便仅判断了 s_i 是否满足 B 性质的条件，所以可能会挂飞。

最为精彩的是我早在刚开始写时就注意到了题目并未保证 |t_{i, 1}| = |t_{i, 2}|，于是在代码里写了个 if 判断，不满足直接输出 0 并 continue，但是我在写 B 性质时似乎并未将这个 if 丢到不满足 B 性质的代码里，也就是即使其满足 B 性质我也会在线地输出一个 0，再离线输出所有答案。这最多可以导致我挂掉 B 性质的全部 25pts。

更为精彩的是就算我把这个 continue 丢到了不满足 B 性质的代码里，我肯定没有在 B 性质的代码里判断 |t_1| \neq |t_2|，而直接将其扔到了二维偏序的数组里，从而会输出错误的结果。

综上，无论如何 B 性质的分是挂定了。

无论如何肯定没时间写 D 了，测了一下虚拟机就结束了。估分 100 + [80, 100] + [45, 70] = [225, 270]，上限很好看，下限也很难看。

反正结束了。

广州在降温。

别傻了，十一月降温很正常。