CSP-S 2025 游记

2huk · 2025-11-01 21:36:19 · 生活·游记

初赛神秘原因挂到了 85，甚至没考过初二选手。

复赛。

开始先看一遍题。T1 感觉不难，可能是神秘贪心；T2 咋是图论；T3 怎么是字符串，2048 MB 肯定是 Trie 相关的东西；T4 应该跟我没啥关系。

此时基本有一个最终分数的定位：T3 这种字符串+Trie 应该是我的强项，如果 T3 能过 T2 也问题不大。于是此时的我非常有信心。

开题。发现 T1 没秒掉。但是我们坚信 CSP-S T1 不可能太过神秘，同时发现这个形式和 AT_joigsc2022_c 有点像，于是直接考虑贪心，让答案达到上界再调整。然后就顺理成章想出了正解。证明不太会但感性理解挺对的，管他呢，小心假设大样例求证。

然后所有样例一遍过了。不太放心，又写了个 n^3 的 dp 用来对拍。拍了一会没挂，基本放心了。此时过去半个小时。

T2 模拟了一下小样例，发现一开始读错题了，没分清「乡镇」和「城市」。读懂题后尝试概括这个模型：n 个点，若干条正常边，边有边权，还有一些特殊边，要求选择若干条边使得原图联通，且边权和最小。

哎这不严格难于最小生成树吗。正解是个啥呢？好像不太会，先看部分分吧。

发现有六十多部分分是极其容易的，所以正解应该快了。时间还早先不着急写代码。

想了一会，发现 m 是假的，可以缩到 \mathcal O(n) 级别。然后跑暴力，应该就有 \mathcal O(2^kn \log n) 的做法了。好像问题不大。

然后发现排序的 \log 是愚蠢的，可以直接归并。那复杂度是 \mathcal O(2^k nk^2)，但是根本跑不满。写写试试。

事实上这时候有点慌，因为好像一点这个题的性质都没用到。但好好分析一下复杂度是能过的，于是抱着试试看的心理开始写。反正如果跑不过去最大的点也能拿到很高的暴力分。

差不多一个半小时的时候调过了。极限数据 2.1s 左右，没什么地方可以卡常，没办法先放弃吧。这个代码直接交应该有 80，也挺不错。

T3。简单分析了一下，得到关键性质：把 LCP 和 LCS 去掉后，相同的字符串构成等价类，每个等价类中分别处理就好。

一个等价类中还需要满足前缀和后缀的关系，怎么感觉这么熟悉……P9196？所以是不是直接离线二维数点就对？

想了想这肯定对。直接开写。

基本上边写边调，写完后很快过了样例一二，但样例三寄了。此时还剩四十分钟左右。赛时死磕一道题是兵家大忌，于是先放一放 T3 开 T4。

发现朴素状压 DP 就有 20 分，而且挺好写。想+写用了不超过 15min，过掉了 n=10 的样例。

回到 T3。把样例三输出了一下，发现错误的情况都是因为 s_{i,1}=s_{i,2}。随便加了个特判就过了。

好！样例全过而且跑得飞快！测个极限数据……2s？？？？

不是哥们，我复杂度 \mathcal O(L|\Sigma|+(n+q) \log n) 显然是能过的，你 CCF 给大数据结构题 1s 时限是何意味？？？

还剩二十分钟，做 T4 应该性价比不高，不如给 T2,T3 卡常。

没有反转。我发现 T3 只把所有串放到 Trie 上就用了 1.2s，可能正解常数更小吧。

按最保守估计能有 100+80+70+20=270，跟去年差不多，很是不满意。

等待 CCF 的水数据和少爷机的奇迹吧——如果存在。

好的我们来复盘一下比赛结束到出分前。说实话这种内耗是毫无意义的，但写都写了就放游记里吧。

• 刚出考场：T2,T3 极限数据都 >2s，肯定没戏，预计 100+80+70+20；
• 出考场 15min：诶不对我 T4 没取模。100+80+70+8；
• 上大巴车：CCF 机子大更新？？说不定 100+100+100+8！！
• 回家看洛谷：我靠 T3 怎么不保证 t 长度相同/jk 那我求最长公共后缀不就越界了了，100+100+0+8。
• 诶等会怎么有个帖子说 string 的长度是历史最大值，那说不定有戏，100+100+?+8。
• 第二天云斗有批量评测：WTF 100+100+100+12，好像 T3 不容易被卡。赢！
• 洛谷更新了 T2 数据：为啥洛谷时限是 CCF 两秒，CCF 机子这么快吗？那不稳了！
• MX/HT 都有了民间数据，都 >= 308，问题应该不大了。
• 洛谷加强了 T3 数据：仍然能过，赢！
• 发现 T3 无论是构造让我 WA 还是 RE 的数据都是容易的（|t_1|\ne|t_2|），保留一丝幻想，T3 挂 eps 分是可以允许的。100+100+[100-eps,100]+8。
• 坏了怎么小图灵和 ACGO 的 T2 真 TLE 了，感觉要逝。100+[80,100]+[100-eps,100]+8。
• 让 AI 算了一下，T2 洛谷评测机 1.36s，在 Ultra 9 285k 下能跑进 1s，又放心了。100+100+[100-eps,100]+8。
• 群里有人说 T3 出题人给每个点都放了一个 |t_1| < |t_2| 和 |t_1| > |t_2| 的点，真假不知道，万一真的就真爆了。100+100+?+8。
• 11.5 晚上，csp 报名网站因为神秘 bug 导致可以提前看分了。最终：

行吧反正我 T2 复杂度多个 k。希望能进 WC 吧。