CSP-S 2025 游记

· · 生活·游记

赛前几天打了一下板子，tarjan 挂了，manacher 挂了，线段树没挂，看了一眼 dfn 序求 lca，可能有用。看了一眼去年 T3，发现已经推不出式子了。感觉状态有点差，可能要比不过学弟了。

上午请假在家里睡了一上午的觉，中午到考点外面吃了午饭，糖醋里脊好吃。听说 J 组变简单了，希望 S 组也简单一点。进考场前被同学问今年 T3 能不能像去年一样场切，回答别出字符串就行。

14:00

我勒个 4:3 分辨率。

打了个 dfn 序求 lca，发呆。

14:30

这次下载题面非常流畅。看 T1，贪心？先取一列然后作差贪心取最大，但是可能反悔，跳了。看 T2，图论，MST？不管了先跳了。看 T3，布豪是字符串，我们没救啦。可能是哈希？跳了。看 T4，看不懂，疑似 DP？

回到 T1，感觉先取最大值，然后取次大值，证了一下，对了，写一下，调一下，过了。

15:30

看 T2，k 很小，可能是 2^k，可能可以把所有边按边权排序跑 Kruskal，但 m 太大，思考怎么办。

看一下原图的 MST，感觉不在 MST 上的边一定不在最后的图里，算一下复杂度，刚好卡满 10^8……

反正感觉挺难写的，先看 T3。先把最小的包含所有不同位置的区间求出来，分成三部分分别哈希一下，询问也一样。中间得一样，左右分别是后缀和前缀，用神秘的东西维护个数。只会暴力，回去写 T2，写完了，调一下，对了。

16:30

看一下特殊性质，B 性质太鸡肋，A 性质刚好让我写暴力，那就看一眼 T4。T4 有一个 O(n^22^n) DP，能拿 20pts，没 T3 暴力拿的高，回去打 T3。写完了，调一下，应该能拿 50pts。

17:30

写一下 T4 的指数级 DP，过了。看一下 A 性质，这不就是 n 的阶乘吗？写到一半发现不对，c 可能为 0；把 0 放后面，然后不为 0 的拿一些放到后面，试推 DP 式子，推完式子写到一半发现自己有一堆东西没有考虑，遂放弃。最后给 m = n 写了个特判，应该能拿 24pts。

18:30

赛前打的板子全都没用上。

出考场和同学讨论时算错分，发表暴论红红黑黑（挂分了另当别论），回家路上想起来 T3 没判 t_1 \ne t_2，遂安详地开始打游戏。

后记

T2 挂成 80pts，似了。