CSP-S2025 有寄
yinianxingkong · · 生活·游记
感觉 T3 出现了一堆没被样例卡掉的错误。
考前一天机房准备考场用自己的电脑，然后水了一天。
考试上午没报 J 组，然后又水了一个上午。
由于在自己学校考的所以感觉像回家了一样，心态良好。
T1 很快秒了，很快假了，很快改对了。此时过去 10min。
T2 一看原图保证连通立马想到可以把新点的边替换进去，立马想到 LCT，发现复杂度
T3 一看字符串就不想做。
T4 一看计数更不想做了。
于是去上了个厕所，注意到已经有人开始冲浪了。
再看 T3 发现原来只替换一次，那么必然覆盖所有不同的地方，进而发现极小不同子段相同是能匹配的必要条件，只需要再满足前缀被包含和后缀被包含就行了。建俩 Trie 发现是求祖先链并集于是扫描线树状数组。
T4 感觉很困难啊，先想特殊性质。
对着 B 性质嗯想没思路，于是对着 A 性质嗯想，倒是想出了个插入 dp。尝试拓展，发现完全没法拓展。然后一看卧槽只有 40min 了，然后胡了胡
考后发现怎么有 AK 了的啊，怎么初三的也有 AK 了的啊。
另外突然发现 T3 好像一没判
突然发现 T4 好像没测空间啊，好像又有一点寄了。
总之得分看 CCF 脸色了。
T4 看到了个简洁的容斥做法：注意到这本质是个有上限排列计数问题，这种限制强的包含限制弱的都先满足强的一定没有后效性。然后发现实际上还有下界，容斥一下即可。代码比我 A 性质短。
总结一下。 结果上来讲这一场应该留点时间查一下 T3 这种码量很大的题
T4 至少容斥做法是一个省队选手可以通过训练想到的，当然我在这道题的问题不是没想到容斥，而是没有将题目的限制用合适的数学语言描述出来从而发现一些模型。
不过能在把能写的性质几乎都写了的情况下还一点都接近不了正解也是比较神奇的。
upd：
T3 没挂，出题人全家长命百岁。
T4 空间确实炸没了。