CSP 2025 游记

· · 生活·游记

初赛没啥好说的，1h+eps ak 了。

复赛在六中。没有人和我面积/ll

T1 秒了，T2 感觉很典，mst 随便优化一下就是 O(n2^k\alpha(n)) 了，45min 时过了。

T3 咋是字符串，想了一会找到了充要条件，再转化一下就变成了 AC 自动机板子，开 2G 感觉就是给 O(|\Sigma|\sum len) 的。不过 AC 自动机在考纲之内吗？写了发，发现常数有点大，卡了卡常，手造极限大概 0.9s。此时大概 2h。

T4 咋是计数，这我哪会啊。完全想不到容斥，想了一个直接 dp 的做法。大致就是要把前面决定填 k 的贡献放到后面第 k 个没被录用的人那里计算。中间没想清楚浪费了一点时间，最后写完大概 3.5h。

检查了一遍。T3 咋在虚拟机里要跑 1.4s，有点倒闭，但是也卡不动常了。看起来 CCF 机子又升级了，希望能过。没时间对拍，感觉很可能倒闭啊。感觉这场不算难，是不是所有人都 ak 了啊。

出来发现 T4 居然有容斥做法，鲨鱼 20min 秒掉了，太牛了。我咋这么菜/ll

什么叫 T3 可能有 |t_1|\ne |t_2|？那我可能彻底倒闭了。希望不要挂下 WC 线。