CSP-S 2025 游记

zhoumurui · 2025-09-19 21:32:05 · 生活·游记

是不是该写游记了。

9.19（距离 CSP-S1 还有 1 天）

放一张图，转自 @Moya_Rao。注意到图中出现了我。

9.20（CSP-S1）

没什么可写的吧。

You have no egg!

10.31（距离 CSP-S2 还有 1 天）

CSP-S RP++！

11.1（CSP-S2 当天）

上午一觉睡到十点，起来打板子。

打了三种 tarjan 就去吃饭了。吃完睡个午觉就退了房，坐车到考场。

进场先打缺省源，打完缺省源发现题目已经发了。于是看题。

T1 一眼唐题，只要先贪心分配然后如果有超员的部们再贪心分给别的部门就可以了。二十分钟写完开 T2。

T2 注意到数据范围 k \le 10，很快考虑枚举哪些乡村要升级。但是如果每次都求一遍最小生成树的话，复杂度就直接炸掉了。

T2 想不出来去看 T3。注意到这个替换就是纯诈骗，因为只能替换一次，所以真正有用的就是 t_1 和 t_2 去掉最长公共前缀和最长公共后缀的部分。

推了一下感觉纯唐题，直接上一个 trie 套 trie 就做了。但是开始写的时候，发现并没有这么简单，因为 s_1 和 s_2 没用的部分也需要和 t_1 和 t_2 没用的部分匹配上。

先去想 T2。想了一下觉得原图中最小生成树以外的边是没有用的，就先求了一遍最小生成树把它们筛掉了。那之后就只剩下 kn 条边可能会用到，就有了一个 O(nk2^k \log n) 的做法。

大样例跑得飞快，感觉不对劲。发现大样例并不是极限数据。自己搓了一个极限数据，发现跑了两秒。

思考了一下能不能优化，无果。于是随手加了个剪枝，一秒，跑路。

瞄一眼 T4。感觉很困难，而且部分分很碎。还有两个小时，重新看 T3，我觉得它是可做的。（记住这句话）

考虑将 s_1,s_2 分解成 CAD 和 CBD，t_1,t_2 分解成 EAF 和 EBF，那么 s_1,s_2 能贡献 t_1,t_2 当且仅当 C 是 E 的后缀且 D 是 F 的前缀，也就是 C|D 是 E|F 的子串（| 是占位符）。

然后感觉可以直接上 AC 自动机做（实际上就是多测版的 P3808）。这时还有一个小时，光速开写，花了半个小时写了个大概。侧样例发现没过。

发现不能直接在自动机上跳，每次跳了以后需要统计从当前位置沿着 fail 树向上跳经过的位置的答案。但是如果暴力向上跳的话，每次询问都会花费 O(\text{Trie 树大小}) 的复杂度，那么它就假掉了。

紧急思考了一下能不能优化它。但是还有二十分钟，只能考虑暴力跳 Trie，O(L_1 q) 跑路得了。

结果样例 2 RE 了。在剩下的时间里没能调出来，耻辱下播。

检查了下文件写没写错，22 年就是因为文件写错痛失提高组二等奖，血的教训。