CSP-S 2025 游记

· · 生活·游记

记比赛日（即 11.1 日）为 Day 0。

Day -？

人生中第一次女装，同学的执行力还是太强了/kel。

Day 0

听了一上午的歌，shower 好听！！！

下午两点半开考，欸密码咋是人杰地灵？

开考前先通读一遍题面，并在 14:50 多的时候正确理解了所有题的题意。由于读题的时候就秒了 T1，所以在 15:10 多的时候过了 T1。

然后对着 T2 玉玉，想了一万种做法，发现这些做法全能通过前三个样例，但是第四个样例就是过不去。这些做法的本质都是将那 k 个乡镇转化到原图里然后 kruskal。此时大概是 16:00。

这个时候我发现这种做法完全没有前途，遂尝试暴力枚举城市化的乡镇，发现立刻会了 O(2^k m \alpha(m))。这时候我认为只有最初的 MST 中的边有用，然后就可以 O(2^kkn\alpha(kn)) 了。遂写，遂过大样例。此时大概是 16:50。

开 T3，发现可以先找到中间的一段不同串，然后按这些串分类。显然只有同一类的串才能产生影响，然后就转化成了计数一个串匹配后缀，一个串匹配前缀的方案数。这个东西直接扔到 Trie 上，然后按 DFS 序二维数点不就做完了吗？？？这是 T3？？？复杂度好像是 O((n+q) \log L + L {\lvert \Sigma \rvert})，应该能过吧，先写写。中途写了个暴力，最后也是在大概 18:10 的时候过了大样例。

最后不敢冲分了，检查检查就结束了。

期望得分：100 + 100 + 100 + 0 = 300。

出场发现 T3 可以直接 AC 自动机。欸好像对的。

Day 5

出分。没挂。