CSP-S 2025 游记

w9095 · 2025-11-01 20:22:21 · 生活·游记

上午

把大纲提高组的知识点的板子都看了一遍，然后摆摆摆。

中午去考点的学校吃了午饭，非常好吃。然后在考点学校内随机游走，在荷花池看见了三只乌龟排队晒太阳，最大的一只在前面，中等的一只在中间，还有一只小的在后面，好可爱。

找了把椅子进行了一个觉的睡，感觉良好。

下午

开考。欸我怎么找不到解压按钮，被硬控 5 分钟。

看 T1，好像先贪心全部选最大的然后用优先队列调整做反悔就行了，写一发过了。此时 14:54。

看 T2，没思路，怎么感觉是神秘的分析连通块情况，跳。看 T3，是可爱的串串题！

由省选的经验，这时不要觉得自己稳了，万一 T2 调不出来不就爆炸了？先去厕所冷静一下。回来发现 T2 k\le10，又注意到有一个 k\le5 的部分分，这不是把折半搜索四个字糊我脸上了吗？先想简单搜索，枚举每个新点选不选，暴力加边跑 MST，O(2^k(m+nk)\log (m+nk))。

考虑折半，这玩意是可以拼接的？发现前面一半和后面一半会互相影响，而这个影响会作用到每条边上，很难定量分析。20\min 没有结果。

重新审视眼前的问题，我发现了一个忽略掉的点：原图中只有原 MST 中的边有用，这样就来到了 O(2^knk\log nk)，发现归并可以做到 O(2^knk^2)，想了一会发现用优先队列维护最优决策可以做到 O(2^knk\log k)。尝试通过递推把 k 去掉，发现空间爆了。于是写了 O(2^knk\log k)，大样例 0.72 秒。此时 16:24。

看 T3。观察了一下发现可以去掉 LCP，然后 AC 自动机套哈希可以做到失配树上链查询颜色。把查询离线下来直接 DFS 就做完了！

可是我赛前没复习 AC 自动机欸，万一打不出来怎么办？冥冥之中，一个令我魂牵梦萦的声音问向我。

你真的热爱字符串吗？

我无法拒绝。

种种线索协助着你从一个具体的时刻出发沿时间的河逆流而上，你感到充满了决心。

我提起全身真气，逆转阴阳，化水为冰，重新发明了一遍 AC 自动机。选用 \text{bas}=3319,\text{mod}=13145203319 以纪念一段美好的时光，之后没有遇到阻碍，一气呵成，几乎没有经过调试就通过了大样例。此时 17:32。

但是我发现我的代码在主函数啥都没写的情况下都跑了 0.5 秒，于是大样例喜提 1.1 秒，肉眼观察还没卡满。一时间没想到什么很好的卡常，赶快去写 T4 的暴力了。

看 T4，数数，先把状压 DP 的暴力写了。哇塞有好多好多性质分可以写，反复横跳想一下，一个都不会，爆炸。此时 18:13。

w9095 已停止抵抗！

检查文件与弱智错误，发现 T3 好像没保证 |t_{i,1}|=|t_{i,2}|？阅读了四遍题面，好像真没有。赶快改。此时 18:25。

最后看了一眼 T3 大样例，全是 |t_{i,1}|=|t_{i,2}|，阴险狡诈！