CSP-S 2025 游记

初赛 GESP 速通，~获得 two eggs~。

模拟赛做爽了。有若干次获得中位数的成绩。拜谢机房几乎场场 AK 的大佬。

提前 $3$ 天启程。把板子过了一遍，把平衡树和字符串 SA，SAM 过了一遍。发现 KMP 可以转 AC 自动机，而 AC 自动机前几天某场已打过一次，遂没有写。但是还是会写的。

早上 $8$ 点起来。$10$ 点多到达考点附近。中午吃了牛排。吃完后在马路树阴下睡了接近 $1$ 个小时，睡得很好。

出发前再次阅读了易错提醒。发现唯一要注意的就是要对拍。其它忘了。

常规的带 $4$ 瓶水进入考场。考场电脑画质像那种十几年前的电视一样，复古专版这一块。checker 只有检查准考证号，很奇怪。

和往常一样，发现没有 code::blocks 用。

开题，T1 贪心一下，发现直接带悔是对的。没有细想正确性，发现好像其它的去转最多的那个必然会不优。过大样例了，打算待会儿再对拍。

此时 $3$ 时整左右。

T2 注意到 $k=10$ 一眼状压。朴素复杂度带了个 $m$。经典结论，若干边集的并的生成树树边只会选原边集各自生成树的并。然后优化到 $O(nk2^k\alpha(nk))$ 加上个预处理的 $O(m \log m)$。大样例 $0.9s$，不是很相信能过，但是下一题。

此时大概是 $3$ 点 $40$ 分。

T3 串串题。上来胡了个差分哈希发现假完了。首先特判 t 串对长度不相等的情况。考虑找一些性质，发现一个必要条件是 t 串对中第一个和最后一个不同字符之间的字串对，能替换说明 s 串这一个的字串对恰好相等。

赛时写了个 trie，但是发现写个 map 就可以了。

然后把这一部分用一个特殊字符替换就可以变为多串子串出现次数。直接 AC 自动机。

赛时没有看到 $t_1\ne t_2$，又写了一个 trie 特判这种情况。

大样例过不了。写了个生成程序，发现特判 $s_1=s_2$ 的写错了。原本以为 $s_1=s_2$ 直接转为子串匹配，但是 $t_1$ 和 $t_2$ 都不同匹配也没有用。

然后把等于那部分全部注释掉。

此时已经 $5$ 点半了。

这时候监考老师才说，要在 bat 文件输入四道题名字才能检查格式。学到了。

没有做 T4 的欲望。打了个暴力跑路了。

拍了 T3。没有拍出来。T2 意志不够坚定，敲了个 fread 快读卡到 $0.7s$。拍了 T2 的快读，然后再稍微拍了一下正确性。

T1 没拍，不够时间了。挂了虚拟机测了 CE。

结束。考后在想自己测内存 while(true) 删干净没有。

喝了 $2.5$ 瓶水，比上年 NOIP 喝得少。

遇到了一些同学。稍微聊了几句。发现 ZY_85 不在，一问才知是退役了。那很可惜了。

速速对了一下 T1，过。

高铁上没插座。写不了了，所以写不了题。发现 T2/T3 都出数据了。等下再对。

晚上发现 T2/T3 好像并没有什么问题。

T4 20 pts 也没有问题。

T2 关闭同步流，最慢的点为 $1.02s$。用 fread 的话是 $891ms$。卡。不过只有 $5$ 个点卡满了。我们声称它能过。

总结一下问题。

首先 T1/T2 其实写得还是慢了些，最好是 $3$ 点 $20$ 分之前过完最好。

T1 没有对拍。发现有些问题就是对拍全部在最后写，就算对出来也没有用。 还是得这样，就是每做完一题就要把对拍程序搞好，一边对一边做下一题，这样才会有良好的机动性。

而且对拍也要写得很快才行。这个得平时练了。

T3 讨论的有些多，并且有一个还是讨论错误的。就是认为若 $s_1=s_2$ 那对于询问串的贡献就是其在询问串的出现次数。当时还把询问串不同的地方做了掩码处理（就是用特殊字符覆盖），然后去匹配，但是是错的。当询问串 $t_1=t_2$ 时有这样的贡献，但是 $t_1\ne t_2$ 就没有这样的贡献。但是 $t_1=t_2$ 的情况压根不存在，所以这个讨论完全是没有必要的。最后还是对拍拍出来的告诉我这个问题。

最理想肯定是 $5$ 点整写完并对完前 $3$ 题。其实 $5$ 点半写完已经很好了。

T4 的问题是平时积累不够。还是太懒了。当时就是一眼转移顺序很奇怪的感觉，然后想到 AT_arc207_a [ARC207A] Affinity for Artifacts 。之前还去打了这场比赛，当时苦心钻研的很久的 A 题，最后还是不会。然后就没写了。结果 CSP 考了到相似的。所以平时的题还是要多去补才行。 偷懒是没有用的。

希望不要挂分，谢谢。

11.5 update。好的，没有挂。