CSP-S2025游记

第二次参加 CSP-S。

单项选择。咦这个闭散列法，二次探测是什么？我平时写哈希都是对于每个哈希值都开一个链表/vector。下标？是哈希值吗？就先按这个选吧。

阅读程序。完成的很顺利。You have no egg!

完善程序。做到 T2 时，只剩 15 分钟了。想了想 1，2，3 小题（第2小题不太确定），4和5小题乱蒙了一个选项。

最后得到了 89 分。发现单项选择哈希题错了，完善程序2错了 2，4，5 小题。学习了新的哈希方式，阅读了完善程序二解析。

期待能拿多少分。希望能拿 300 分。

开 T1，快速想出反悔贪心做法。

看看 T2，好像做过 k=2，感觉挺简单。看了一会才发现暴力跑 $2^k$ 次哈希复杂度是错的，还得再想想。发现一个图加一些边的生成树一定不会用到原图的非树边。一条一条加边，加完再断一条边，LCT？我不会。突然发现可以直接用目前可能的边 Kruskal。好像是 $O(2^knk\log k\cdot\alpha(n))$ 的。不知道能过。先把 T1 写完吧。

写完 T1，再看看 T2。发现可以把每一个集合的最小生成树记录下来，每次只要对两个 $O(n)$ 的边集归并，总复杂度为 $O(2^kn\alpha(n))$。写出代码，通过大样例。

看看 T3 和 T4。T3 中要把一个字符串变成另一个字符串。考虑找到 $S_1$ 和 $S_2$，$T_1$ 和 $T_2$ 第一个和最后一个不同位置，取出中间的部分。可以替换当且仅当中间部分相同且 S 公共前缀为 T 公共前缀的后缀，S 公共后缀为 T 公共后缀的前缀。该如何维护“二维前缀”呢？Trie 上哈希？想不到怎么哈希。发现可以构造一个字符串 lcp#mid1#mid2#lcs，能用 S 替换 T 当且仅当 S 对应的串是 T 对应的串的子串。可以用 AC 自动机求解。再看看 T4。$n \le 18$ 是好做的，$n = m$ 也很简单。心里有些急，想尽快写完 T4 部分分，然后去做 T3。想了想其他几档分，都没想出来。打了 24 分。

开始写 T3。剩的时间不多了。我写出一个 AC 自动机。啊啊啊，怎么连样例 1 都过不了？我看了半天，没看出什么问题。我改了半天代码，让代码输出每个节点对应的字符串和 fail 到根的权值和。发现是统计答案时没有对所有前缀的权值和求和，只算了最后一个。赶紧改过来，改完只剩两三分钟了。测了两个小样例，大样例没来得及测。

预估得分：100+100+?+24。

出成绩了。100+80+100+24。

T3 拿了 100 分。很不错。

T2 怎么变成了 80 分？是不是被卡常了？

拿代码一测，原来是 WA。归并的时候只判了一边的边界条件，就以为可以了。

看了看 T3 题解的 Trie 做法。我怎么没想到。

总体还是不错的。和去年相比有很大进步。

明年加油！