CSP-S 2025 游记

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

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

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

开考。欸我怎么找不到解压按钮，被硬控 $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$。

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

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

$[100,100]+[80,100]+[60,100]+[20,20]=[260,320]$，感觉到不了大众分啊，去不了 WC 了，悲伤。

赛前真的没有考虑过 CCF 会出卡常题，于是没有复习任何卡常技巧。例如 T3，有一个显然的卡常是把哈希值离散化一下就不需要 unordered_map 了，可是我居然没有本能反应。这说明卡常还不够熟练，菜就多练。

还有出考场后发现一车人会做 T4，我个唐氏啥都不会。要加训 DP 和数数，菜就多练。

UPD：$100+100+100+24=324$，感谢 CCF 的不杀之恩！