CSP 2025 游记

· · 生活·游记

省流：100+80+30+24，t3 数组开小了无敌了。WC2027 再见。

:::info[游记内容]

前言

去年的游记。

把神秘话术删掉了。

是这样的，前几天我回去看了染色这个题，发现这个题把 \Theta(n^2) 优化成 \Theta(n) 是一眼能秒掉的，就是简简单单打个标记就做完了。

但是我考场上并没有想到，之前补这个题的时候也用的是别人依赖于结论的做法，但这次我想到的优化没有使用结论。

具体原因我考虑了一下，好像就是我去年在考场上，对切两题的成绩过于满足了，然后就拼暴力开摆了。

虽然跟同届的人比还算可以，但是低一届的有人能够做出来，高一（现在高二）届的几乎全都做了出来，所以我觉得去年还是没发挥好的。

今年争取能拿分就多拿吧，不要重蹈覆辙了。大家 rp++。

初赛

初赛有什么好怕的，随便考考睡睡觉，考完打 phigros 四次 AP 了个新 15（很久没打了 qwq）。

分数就不说了，【数据删除】完了。

复赛 Day 1

考前在打 phigros，爽。

考场上不知道人杰地灵是什么意思，尴尬。

想了一会好像没啥问题，直接开写，$2:45$ 过了所有大样例，不管了。估计是黄。 然后开 t2，马上发现 $k\leq10$（主要是 $2023$ 年 t1 吃过亏，长了点记性）！复杂度是可以带上 $2^k$ 的。 发现自己忘记复习 Prim 了，只会 Kruskal，手搓 Prim 没搓出来，复杂度被迫带 $\log$，已经有点破防了。 显然可以 $\Theta(2^k(m+nk)\log(m+nk))$（省略 $\alpha(n)$ 了），$3:00$ 写了个。$3:15$ 测大样例，跑得好慢啊，回头看数据范围，分太少了。 不行，我怎么可以不切 t2？ $3:20$ 就想到可以只保留原图 MST 上的边，时间复杂度是 $\Theta(2^knk\log(nk))$ 的。 然后就一直想能不能做到 $\Theta(2^kn\log n)$，做了 $10$ 分钟无用思考（在想 dp），结果是放弃了。 $3:30$ 打算先写 $3:20$ 想的那个做法，$3:45$ 写完了，看大样例跑得不慢就没管了，常都没卡一下。 开 t3，$3:50$ 想到 $\Theta(L_1L_2)$ 的做法，但这分太少了，放弃。 看到 $q=1$ 很多分，打算换个角度。$3:52$ 马上想到 $\Theta(nq)$ 的做法，有 $50$ 分！ 考场上发现 t3 的 $50$ 分做法套 ACAM 可过，但忘记 ACAM 了，又一次破防了。 但感觉 $50$ 也不好写，$4:00$ 的时候决定先开 t4。 开 t4，感觉有 $52$ 分。写状压 $20$ 分的时候，调了 $75$ 分钟，才发现我把“前面有 $c_i$ 个未录用的人”看成了“前面有连续 $c_i$ 个未录用的人”，生气了。 $5:25$ 调完重新看特殊性质，感觉不好搞，$20$ 分先放着了。 回来赶紧冲 t3，哈希真的难调。$6:21$ 的时候调完了，过了小样例没空管了（感觉不太稳），检查工作目录去了。 赛时觉得最高 $100+100+50+20=270$，其实已经有点失望了。 --- 出考场，等同学说的时候才发现 t2 大样例 $n\leq10^3$，气炸了，看那个大样例运行时间，估计是过不了了，应该是 $80$ 分。 回家路上一直在用 phigros 发泄。 回家看 QQ 发现，同学说 t3 不保证 $|t_1|=|t_2|$，完蛋了，这下 $50$ 分也不保了。 目前最坏打算是 $100+80+0+20=200$。 不是，今年怎么这么难啊。 管它呢，又不是 NOIP，嘿嘿。 ### 复赛 Day $2

回老家玩去了。

下午看了眼 t1 t2 的题解。t1 做法是正确的。t2 做法也是正确的。欸？

听 __Allen123_\ 说 t2 \Theta(2^knk\log(nk)) 就是正解，还能过洛谷数据，我 100 分的希望又来了，打算晚上自测。

晚上自测，只写了前两个题。t1 过了，t2 还是 80，愤怒。

发现 t2 并查集没写按秩合并，尴尬，但写成路径压缩估计没太大差别（CCF 应该干不出这种事情）。

听说可以改成桶排优化掉那个 \log，改完过了，何意味？

又听说 t3 正解就是 50 分 ACAM 优化，我错了我以后再也不说字符串算法没用了。

### 后记 $100+80+30+24=234$。 t3 可能是写挂了，$|t_1|\neq|t_2|$ 的数据并不存在，下次要合理分配时间了。 哦不我的 WC，膀胱爆炸了 /ll。 然后发现 t3 是数组开小了？？？？？？？我是傻逼吗？？？？？？？？？？？？和暴力 KMP 同分，流泪。下次记得检查数组大小。 ::: 还好不是 NOIP，要是这个是 NOIP 我就完蛋了。 NOIP rp++。