CSP-S 2025 游记

· · 生活·游记

1

发现 B 是图论，$k=0$ 摆明了是最小生成树。发现 $k\le 10$，然后会了一个 $O(2^k(m+nk)\log(n+k))$ 的做法，就是枚举改造子集 $S$ 跑 MST，然后发现 $m\le 10^6$。怎么办？？不管它，继续阅读题面。 C 是个字符串，多串匹配相关问题，至少要个 Trie。D 是个排列计数，$n\le 500$，当然是个 DP。想了一会儿 C 和 D，没有思路。 $14:50$，准备开始写 A 的代码。突然想起来这是 OI 赛制，最好要先证明贪心的正确性。花了一分钟给出感性证明，两三分钟说服自己这个证明是对的。然后 $15:00$ 写完了。认为 A 题难度黄/绿。 想 B 题。以为是要建一个 $O(nk)$ 个点的新图跑 MST，不会建图。发现特殊性质就是个缩点。想如果特殊性质稍微弱一点，只有 $c_i=0$ 的保证，那么怎么做。发现还是不会。有点红温。出去上个厕所冷静一下，回来发现大脑仍一片空白。 随便在草稿纸上画了几张图，凌乱的笔迹中仿佛藏着我无法捉摸的秘密。在不断的尝试中，我仿佛看到一个孤独的、绝望的自己——难道 CSP-S 的 T2 我都做不出了吗？我不由得想起去年 CSP 的赛场上，做出 T3 时的那种激动之情。如同光明和黑暗中的自己，形成了鲜明的对比。 审题。这是制胜的法宝之一。发现 $n\le 10^4$ 有点不对劲，$n\times 2^k=1.024\times 10^7$ 是个合理的复杂度。我想，大概还是需要枚举改造子集 $S$，不过需要加速 MST 的计算。这时，看着 $n\le 10^4$ 与 $m\le 10^6$ 的对比，我恍然意识到，加入改造点带来的边的增加量，相对原图是微不足道的。我想，或许可以递推求 MST。 草稿纸上的图忽然像闪起了光。摆弄了几分钟后，我发现了关键结论：向一个图中加边，原来不在 MST 中的边再也不会回到 MST 中！这样边数缩小到了 $O(n)$ 量级！ 于是对原图求 MST，每次求子集 $S$ 的 MST 时，选一个点 $p\in S$，从 $S\setminus \{p\}$ 递推过来跑一次 Kruskal 就行，一次 Kruskal 的点与边都是 $O(n)$ 个。复杂度看着是 $O(2^kn\log n)$ 的，能过。 ## $2

赶紧写，15:50 写完了，一测大样例，答案正确——但是怎么跑得这么慢？加了一句 cerr<<clock()<<endl; 一看，1.155 秒，有点慌。过了一会儿发现输入文件怎么有十几个 MB，那我加个快读，再测，怎么还是接近 1 秒，是不是还要卡卡。

决定给考场的机子测个速。发现 10^9 次取模要 3.3 秒，似乎不算很快。瞄了一眼 PDF 第一页的评测机配置，怎么看起来很高端的样子，应该比考场的机子要好吧。欸不对，那个跑了 1 秒的样例怎么 n=1000 啊？？好像有点寄。

这时突然发现 Kruskal 里的对边排序可以省省，用归并好像可以去 \log，变成 O((n+m)\log n+2^kn)。于是写，写完一测发现 <0.5 秒，然后注意到数据造满时 (n+m)\log n 和 2^kn 是接近的，于是判断 CCF 的机子上肯定不会超时。现在 200 分应该到手了。

先前那种近乎绝望的心情已消失不见。这时刚过 16:00，剩余 2.5 小时。然而我觉得既然 B 题的难度大概有蓝，C 和 D 应该不会好做，不过似乎又都不至于不可做……大概是两个紫题罢！2.5 小时的时间似乎并不多，尽管比赛仍未过半。

场切紫题？或许我从来没有真正想过，自己是否有这样的实力。NOIP 2023 中，在想出 T4 正解的情况下，我遗憾没有写完。NOIP 2024，再次冲击 T4，写出 O(n\log^2 n)，却被 n\le 5\times 10^5 切割得遍体鳞伤，只留下 52 分。隐隐之中似乎有个力，阻止着我的前进。

但是刚开始还是毫无思路。我问自己，这是什么类型的字符串题目？再读一遍题，哦是多模匹配，欸我直接建两个 AC 自动机，把询问串在自动机上走，统计答案不就好了。不对，AC 自动机在 NOI 大纲里是几级算法来着，好像是 $7$ 级来着？不管了，先用着吧。 我时刻提醒自己，今天四个题的时间限制都是 $1$ 秒，空间限制大都是 $512$ MB，但 C 题是 $2048$ MB。现在一上来就建 AC 自动机，空间是 $|\Sigma|\sum L_1=26\times(5\times 10^6)=1.3\times 10^8$ 个 `int`，好大，那么思路应该没错。 统计答案自然变成了 $O(\sum|L_2|)$ 次树上询问，那么八成要数据结构了，那么优势在我？哦，代码可能会很长，一百几十行，但是我没有时间胆怯。 ## $3

建 AC 自动机后套路地建 Fail 树。询问的大概是两棵树上的两个从根到某点的树链上，同时出现的颜色个数。直接做不太行吧，那我离线，算每种颜色对询问的贡献怎么样。贡献在子树里吧，那我拍成 DFN 序，欸剩下的问题是不是二维数点，做完了？

但是想不清楚细节。于是强迫自己用数学式子把询问所求表示了出来。发现可能需要差分，常数 \times 4。但是 \sum|L| 有 5\times 10^6 诶！O(n\log n) 可能有点悬，难不成和去年 CSP-S 的 T4 一样，CCF 又来卡 \log 了？怎么 \sum|L|\le 2\times 10^6 都只有 60 分啊？还有，我前面推的结论真的对吗？

不过反正不用数据结构，直接暴力处理询问也有点分。于是 16:30 时，我开始写 AC 自动机，写复杂度平方的暴力确认正确性。

哦怎么要建 Fail 树，5\times 10^6 个 vector 是不是要完蛋？于是决定使用链式前向星，连对 Fail 树的 DFS 都采用了栈模拟，好在一切似乎很顺利。

完了，我对贡献计算的限制不完全！还要加个 `i>=r` 以及自动机上深度的限制！这时猛然发现数据结构统计的限制多了一维，静态二维数点变成了动态的。 无数矛盾的念头在对撞着，仅剩的不到 $1.5$ 小时仿佛压得我喘不过气。我又瞥了一眼 D 题 $n\le 18$ 的部分分，想到状压 DP 可能要调一会儿，却也没有写。 我又要失败了吗？莫名地，B 题又闯入了脑海。样例没有开到最大的数据范围，你的代码要是被卡常了怎么办，或者正确性假了，数组越界了怎么办？要对拍吗？这样，要是今年的一等线超过了 $200$，还能赢吗？经历了 B 题的煎熬后，这是我第二次想起了“退役”这个词。 不可能——要是我打了 C 与 D 的暴力分，怎么可能达不到一等线来着。况且 B 题也有蓝题的难度，一等或许也不是人均能做出 B 题：参照去年的 CSP。 我决定让那些复杂的询问限制纠缠住我，忘却一切不好的念头。加了一个深度的限制，我在原来的代码上修修补补。 ## $4

改好了，暴力过了两个小样例。怀着等待几分钟的准备测试了样例三，却发现程序只跑了约 7 秒——看来没刻意卡，样例不强呀。于是 fc replace3.ans replace3.myout……怎么 WA 了？？？

完全不知道怎么调，难道我要再写一个暴力对拍？那样肯定写不完正解吧……肉眼对比 fc 的信息却无果，看起来错误挺严重的。于是用 IDE 打开 ans 和 out 尝试找出一个不同之处。翻了好久发现第 484 行的答案小了，去 in 里面找找对应的询问……欸，怎么 |t_{484,1}|=|t_{484,2}|=1？

这时突然想到，好像可能有相同的 s_{i,1} 或 s_{i,2}，然而我的暴力做法直接用了一个 clr[M] 数组维护字符串的末尾标记，然后原来的值就被覆盖了，寄！

不过问题不大。我想，或许不该花时间把暴力改对了：要对每个点维护 vector<int> clr，比对相同的 clr 值太麻烦，又和正解没什么关系。不过发现可以换一种好写一点的暴力方法，5 分钟改掉了，跑了十几秒过了样例三，又过了样例四。这时已经 17:25 了。

然后就只有数据结构的问题了。发现是动态 4-side 矩形加，单点查值。只会 \log^2，怎么办？这条路真的被堵死了吗？我想起来矩形加的 x,y 轴的区间是由树的 DFN 序转化来的，或许在树上，这个问题将会有更好的性质。可是同时处理两个不同树的子树或树链，也不好做。

想了很久。最后发现可以只把一棵树拍成 DFN 序，把修改和询问挂到另一棵树上，遍历这棵树，等于是要支持加入一个区间，求某个历史时间段加入的区间中，有多少个包含一个给定点，支持撤销。欸，那可持久化线段树不就完了？但是常数有点大，空间也大，不算好写。此时已经 17:50 了，我决定再思考一会儿。

然后就注意到“历史时间段”是假的，只要差分后把询问挂在正确的结点处理即可，这样只要一棵线段树，支持区间加，单点值……欸这不是 BIT 吗，常数还小，又好写。

胜利的曙光。火红的希望燃烧起来了。

不过怎么还要维护一个倍增数组啊。我看着 cerr<<(&mbe-&med)/1048576.<<endl; 逐渐增大的数字，不禁提醒自己空间问题。

此时已经 18:00，还有半小时。为了方便写代码，我咬咬牙，还是用了 vector 存 Fail 树以及挂在树上的修改与询问。静态空间不断增大，隐形的动态空间也开始显现。不过 2048 MB 的空间还是比较友好的。

5

数据结构部分比我预想的还要顺利，十分钟写完了。不过发现再次过不去样例一，心里还是直打鼓。不久后发现是：

void _add(int p,int d){ } // BIT update
void add(int l,int r,int d){
    _add(l,d);if(r<n)_add(r,d);
}

原来差分写错了，应该是 _add(r+1,d)。修改后直接过了所有样例，但是好像有点慢。加了一句 cerr<<clock()<<endl，发现样例四跑了 937 毫秒！

不过仔细一想，认为我的算法在具有性质 B 的样例四基本是跑满的。加之 CCF 的机子挺快，于是先不卡时间的常数——更重要的是空间，MLE 的后果比 TLE 严重多了——我对 NOI 2022 的 10^6 个 deque 的事情也有所耳闻。

现在已经 18:15，但我还是花时间把空间卡下去 200 MB 左右。然后随便放不等式得到 \text{Mem}_{\text{Static}}+\text{Mem}_{\text{Dynamic}}\le 2\times 10^3 \text{MB}。于是 18:20，C 题就这么结束了。

我场切紫题了？！

不禁忆起去年的 CSP，那天早上我刚复习一道与当天的 T3 手法相同的题目，于是下午的考试中几乎是秒杀了 T3。从在这题上以 1.04 秒的时间功亏一篑后，我一直尝试寻找一个场切蓝题的契机。CSP 2024 时，我做到了——并且之后的比赛中，蓝题我再也没有失手过。那时，我真切的感受到，自己已经摸到了那“更高的水平”的那个“敲门砖”，触及了那份梦想的一角。

上个赛季，我一路走到 NOI 的赛场，看见了不知多少比我强上几倍甚至几十几百倍的选手。我意识到，或许自己离梦想还很远。在 NOI 2025 的 Day 1 我曾尝试冲击 T3 的正解，但是失败了。省选与 NOI 没能检验我的实力，我质疑着，自己真的变强了吗？

今年，又在这题中（话说此题也是字符串+数据结构（分块）），我在想出正解的情况下，由于时间略微不足没能场切，赛后才过。我不断寻觅着场切紫题的契机，总希望着能看到，自己确实增进了实力。这次 CSP，我想，我做到了。或许我的代码会被略微卡时卡空，但是这不重要了。原来，一年以来，我已向着梦想又迈出了一大步。

比赛的剩余 10 分钟，我决定在 D 题写一个 O(n!) 暴力（我认为 n\le 18 的状压是来不及了）。这时我已经忘了 m=1 与 m=n 的存在。

然而暴力怎么在样例二挂了？原来是字符比较写成了 s[i]==0，改掉就对了。18:27，比赛接近尾声了。在欣慰中，我在 D 题的最后，写下：

Break free we chased our dreams
Beneath the starry night
In the face of god
We rose as one

希望我们无畏地追逐梦想，最后终能抵达理想的彼岸。

后记

发现 15:00 时，我的某个朋友给我发来了 CSP rp++ 的祝福。心中忽然涌起一股暖流。

洛谷上，这次 CSP 的四个题评了绿蓝紫紫的难度，看来我的估计挺准。

原来 AC 自动机不在提高组考纲里吗？

不久 T1 有了民间数据。我用 3 分钟复现了考场代码——通过了，我的贪心确实正确。

我站起身，窗外灯影闪烁，我感到十分地安心了。