CSP 2025 游记

笔试 AK 了，很有实力。

怎么学校的运动会在 CSP 前两天举行啊，彻底怒了。

在 bs 的一机房，是 Windows11。

只参加 S 组。

T1 10min 就会了，比较简单。

T2 首先发现最小生成树可以边加边边做。然后用归并排序就可以做到 $O(n2^k)$。

T3 花了 1h 才想到可以把最长的前后缀去掉，然后剩下的得一样。相当于 x+'#'+y+'#'+y'+'#'+z 做匹配。赛时忘记 ACAM 怎么写的，所以枚举 x 的长度，然后 y 的部分可以建立 Trie 树，询问时使用二分找到第一个有值的祖先即可（需要用哈希表）。时间复杂度 $O(L\log L)$，主要看哈希表的常数了。

T4 设 $f_{i,j,k}$ 表示前 $i$ 天中，有 $j$ 个人没选上，有 $k$ 个位置满足耐心度小于等于 $j$。注意我的状态不考虑耐心度大于 $j$ 的位置，这些位置显然可以在最后计算。

转移是简单的，但是 $s_i=0$ 的转移写错了，所以只有 32 分。

预计 100+100+100+32，不是很差，但是 T3 有概率挂分啊，只有寄希望于 CCF 神机了。

出来一问怎么 AK 一车，这下很爆炸了。

赛后发现 T4 且只有一个转移系数写错了，并且时间复杂度可以被分析到 $O(n^3)$，改改就过了。痛失 S 组 AK/ll。

赛后发现 100+100+80+32=312，T3 的死因如下：

就这样了。