CSP-S2025游寄

· · 生活·游记

上午：

没报J组，在机房玩了一上午，吃完饭后就和机房的几个人一起去考点了。

14：15

进考场开始打缺省源 （吐槽一下那个机房键盘好硬，不过还好没出什么问题）。

然后开始玩小恐龙。

14：30~14：50（T1）

打开PDF后光速看 T1，然后看到 \frac{n}{2} 的限制就知道是贪心，口胡了一下证明就写代码了。

T1像绿，感觉不太妙。

14：50~16：00（T2）

想半天想不到合适的多项式做法，就拉下去看数据范围准备打部分分了，结果看到 k\le10 就知道是要枚举选哪些乡村进行改造了。再结合前面的思考就知道是和原图的最小生成树的边一起跑最小生成树了。最后代码没优化，时间复杂度应该是 O(mlog(m)+2^knklog(n)),但时间复杂度算成 O(mlog(m)+2^knlog(n)) 了，还疑惑为什么大样例跑得那么慢 ，最后宁愿自我安慰是考场机子太烂都不愿意回去思考是不是自己算法的问题，100->?。

16：00~18：00（T3）

初看以为是AC自动机，但AC自动机不是提高组考点就没继续想了。紧接着想到 KMP 大暴力，然后意识到一对替换的贡献只有从第一个不同的字符到最后一个不同的字符，而一对询问所需的贡献也是这些，于是就可以把 n 对替换分成若干类，询问时只需要在对应的类里去找就行了，然后用两个 trie 分别记录不同类的字符的前后缀来统计答案，其实很接近正解了，但我没想到怎么统计答案，开始想了个在线枚举询问时后缀经过的点有哪些对应的前缀经过的点，但没调出来，然后换了个离线统计答案 （总之就是离正解越来越近但就是想不到）。

另外开字典树时害怕开不下，但看到 2GB 的空间限制后瞬间安心了。

18：00~18：30

T4解法肯定是没时间想了，赶紧打了个状压拿了20分后走人，最后再把每个题的样例都测了一遍后就开睡了

总分

预估 100+（80~100）+（?~100）+20

但愿CQ别太离谱吧