CSP 2025 游记

LG_jyc · 2025-11-06 14:08:34 · 生活·游记

省流：S 组 T2 暴力 O(m \log m+2^k m \alpha(m)) 能过。

很好，HN 的复赛场地只有长沙理工大学，一直都是。

上午

T1 先拍个排序上去，发现跑了两秒感觉不对，换成桶再试试，怎么还是不对，加上快读，总算没问题了。欸不对，CCF 不是说了不卡常吗？
T2 一路顺利。
写 T3 的时候脑残了，没想出来，转 T4。
等等 T4 怎么这么水，直接一个计数 DP 拍上去，都不用容斥。
回来写 T3 还是不会，写了个 65 分遗憾立场。

出来发现机房同学怎么都 AK 了。

预期 100+100+65+100 实际 100+100+65+100，第三次参加 CSP 痛失 AK。

下午

T1 直接贪心，等等怎么还要加快读。
T2 没有一眼看出来，没事先别急，先打开电脑玩华容道。
噢终于明白为什么代码跑得这么慢了，这个机子的配置怎么这么菜，打开任务管理器再拖到这个窗口可以直接将 CPU 使用率卡到 70\%，哪怕不开窗口，放两个死循环，可以直接卡到 100\%。
好的回来做 T2，完了怎么还是不会，这样下去不会 AFO 吧，先写了个 O(m \log m+2^k m \alpha(m)) 的暴力，加上特殊性质（理论上）可以拿 72 分。
接下来写 T3，不会写 AC 自动机，但是注意到直接暴力 KMP 时间复杂度肯定爆炸，考虑将 T_1 与 T_2 的最左边的不同位置与最右边的不同位置的区间取出来，如果 \mid S_1 \mid 比这个区间长度还小，这样看上去似乎只是一个常数优化，但是仔细想一想发现是 O(qL_1) 的，可以拿 50 分。
T4 一眼不会，写了个 8 分爆搜。
回来发现 T2 代码居然在样例上面跑了 1.084s，考虑到这个还不是卡满的样例，突然感觉连 72 分都有点悬了。

考试出来发现比我小一岁的一位同学好像都比我还高，完了这样下去不会真的 AFO 吧。

结果一出成绩，为什么 T2 是 100 分！（现在觉得是因为我加上了一个剪枝，当 Kruskal 已经加入了足够的边就退出，然后 CCF 的数据使得 Kruskal 只运行了较少的次数就结束了），但是 T3 只有 30 分。

预期 100+72+50+8=230 实际 100+100+30+8=238，实际居然比预期高！

（突然想到 NOIP2024，我花了将近三小时写了 T1 结果场上就证伪了，大样例都没过，没想到得了 85 分，卡线二等奖）