CSP-S 2025 游记

发表于 2025-11-02 更新于 2026-01-31

Day \(\le\) -1

模拟赛爆爆爆！

Day 0 (10.31)

试机，但没有机。

已完成今日「学长能不能给我签名？五块还是五百块」大学习。

Day 1

哎怎么七点半就醒了。

上午复习了一些板子，包括但不限于 FWT、点分治、割点，以及 SAM。感觉都不像会考的。

中午睡了半个小时。

去考点！！！

好像到考点到得比较早，于是开始水群，得知评测机 CPU 更新为 U9 285K。

进考场！！！

监考老师要求阅读电脑桌面上的一个可能是须知的 Word 文档，经仔细阅读后发现第二页中 NOI Linux 虚拟机相关内容中有“应提供虚拟机密码”类似文本。但显然要求选手提供密码并没有道理，合理猜测是下发前忘记将这里替换为密码了。

开考！！！

打开虚拟机，发现直接进入了桌面，并不需要密码。

开 A，\(\sim 20\) min 写完，经过一顿 ulimit 与 -fsanitize=address,undefined 的测样例和对拍后时间成功来到 \(\sim 40\) min。

看 B，感觉一秒时限是很困难的，糊出 \(O(nk\log k \cdot 2^k)\) 做法并认为太过逆天，思考了几分钟没动电脑后发现虚拟机自！己！锁！屏！了！

发现自己并不持有虚拟机密码的相关知识，尝试 cqbz 与 noi 未果，遂向监考老师求助。监考老师尚未走到就已看到屏幕，便说：“哦密码 123456”随后转向继续行走，全程均速。

继续思考 B，发现可以将所有 \((k+1)n - 1\) 条边的边权离散化，随后在 \(2^k\) 枚举中每次只需要进行一次计数排序，时间降为 \(O(nk2^k)\)，开写。

写完测完发现大样例的 \(n = 10^3\)，于是自己造了一组 \(n = 10^4\) 的数据，发现运行秒数 \(> 1\)。稍微卡两下卡到了 \(\sim 0.7\)。

此时感觉这场已经不会特别炸了，看完 C 根据参加模拟赛的经验想要开拼部分分时反应过来这是 CSP-S 不是 CSP-S 模拟赛。

发现一个替换合法的充要条件：

\([l', r']\) 覆盖了 \(t_1\) 与 \(t_2\) 的第一个不同位置 \(l\) 与最后一个不同位置 \(r\)。
\(s_1\) 与 \(t_1[l', r']\) 相同，\(s_2\) 与 \(t_2[l', r']\) 相同。

认为第二个条件可以通过将字符集平方后合并 \(s_1, s_2\) 与 \(t_1, t_2\) 变为“\(s = t[l', r']\)”。然后可以对所有 \(s\) 建 AC 自动机。按照 \(t\) 在 AC 自动机上转移，当第 \(i \ge r\) 个字符转移完后计算 \(r' = i\) 的 \([l', r']\) 对答案的贡献，需要对于 AC 自动机上，根到某结点的路径上，满足 \(\mathrm{dep} \ge i - l + 1\) 的结点的点权求和。这个显然是做个前缀和后倍增找到最后一个 \(\mathrm{dep} < i - l + 1\) 的路径上的结点就可以做了。

感觉很好，但是 \(L_1 \le 5 \times 10^6\) 完全无法接受 \(\Sigma = 676\) 啊！

我们发现不用扩字符集，可以直接将 \(s_1\) 和 \(s_2\) 中的字符交替插入合并为 \(s\)，将 \(t_1\) 和 \(t_2\) 中的字符交替插入合并为 \(t\)。此时上面的 AC 自动机做法可以照搬。复杂度 \(O(L_1 (\Sigma + \log L_1) + L_2 \log L_1)\)，开写！！！

欸 AC 自动机怎么写的来着，这下回收伏笔了。

追忆写法并成功写完了 AC 自动机，在 -fsanitize=address,undefined 与 -D_GLIBCXX_DEBUG 的庇佑下发现了样例中的 \(|t_1| \ne |t_2|\)，大样例 \(\sim 0.4\) s。

此时还有 \(\sim 80\) min，开 D，一开始看错题认为每个人判的是最近的未被录取的连续段。认为可以拿 \(32\) 分。

打完 \(n \le 10\) 发现样例二跑出来完全不对，回去看看题面发现读错了。

重新想了一下发现可以拿 \(24\) 分。

写完差不多就可以开始检查了，备份代码后 ulimit 测一遍，开 sanitizers 再测一遍。

结束啦！！！

出考场与【a】交流了情况，得知 D 与【c】前几天才讲的一道题差不多，但我当时被拉到下面机房做心理测评了？？？

得知【a】【b】C 题写的是 \(O(n \log \text{不知道什么东西})\) 的二维偏序，且大样例不是极限数据，且【a】的的大样例跑了 \(\sim 0.1\) s 后自造数据仍然跑了 \(>1\) s，十分绝望。

回去后才想起来还有个 \(O(L_1\Sigma)\)，上 QQ 询问【a】他的 C 做法是否有这项，得到肯定回答。

我还以为我的 C 要慢 \(>20\) 倍呢（划掉）。

墓前估分不高于 \(324\)。

感觉这个 D 完全是来破坏我的赛后心态的，明明打得没什么大问题却还是有点难过。

目前想法是不想在乎 CSP-S 分数了，反正结果只有“上 WC 线”“上 NOIP 线”和“爆完了”三种。

Day 5

哎怎么就 Day 5 了？

\(\mathrm{score} \le 324 \land \mathrm{score} \ge 324\) 了。

有 WC 去吗？