CSP-S 2025 总结

· · 生活·游记

CSP-S 2025 总结

赛前

由于广播明确要求不允许打代码，只允许测试键盘鼠标，安装环境。只好照做。

赛时

先打了缺省源，发现 T3 空间限制 2G ，感觉不一般，其他正常。然后开始看 T1 。

用了这么长的时间有很大一部分原因是因为电脑过于垃圾，本地编译 $3s$ ，运行 $3s$ ，这让本来十分容易的打表变得十分浪费时间。 $T2$ 看到 $k\le10$ ，第一反应直接 $2^k$ 暴力枚举。 发现 $m\le10^6$ ，但是实际上只有生成树上的边才有用，于是转换为 $m\le10^4$ 。 由于这才是 $T2$ ，感觉直接跑 $MST$ 应该能过了，算了一下复杂度，$O(2^kkn\log(kn))$ ，还真过不去，考虑看一眼后面的题再说。 看完题后，回来看 $T2$ ，思考方向仍然是考虑那些便是没有用的，毕竟 $k\le10$ 不太可能不是暴力枚举。 发现可以先跑所有边的 $MST$ ，然后每次删去一些点，变成了若干连通块，然后在这基础上跑 $MST$ ，感觉很对，总复杂度是 $O(m\log m+kn\log(kn)+2^kkn\alpha)$ 的，感觉可过。 于是开打，然后跑大样例，感觉不慢，这时大概过了 $1.5h$ 。 中间干了一件非常愚蠢的事情，测大样例发现一直测不出来，然后发现我 $T2$ 代码竟然保存在 $C$ 盘，$T1$ 和大样例保存在 $D$ 盘。 这是因为我打 $T1$ 缺省源时不小心保存到了 $C$ 盘，然后手动把原先在 $C$ 盘的 $T1$ 给复制到了 D 盘（也就是说 $C$ 盘中还有一个只有缺省源的 $T1$ 代码），并且是双击文件打开，而不是在 $DEV$ 中打开（如果是在 $DEV$ 中打开是会直接改路径的，而双击打开不会），于是之后 $T2$ 新建文件时就在 $C$ 盘。 然后我把代码全部移动到 $D$ 盘，电脑提醒我要不要替换，我还思考了一会儿，以为是替换 $.in$ 和 $.out$ ，刚替换完就想起来还要替换 $T1$ 代码。于是 $T1$ 代码就没了。 然后又花了 $20$ 分钟重打加调过了 $T1$ ，中间还因为多测没清空浪费了一段时间。 然后又发现 $T2$ 大样例不满，然后随了一组满数据，发现 $2s$ ，但是考虑到本地编译 $3s$ ，运行 $3s$ 的速度，就先扔下不管了。 开 $T3$ 。 先疑惑为什么计数问题没有取模，后来才发现原来只能替换一次，答案不会超过 $n$ 。 感觉可以先想想 $O(nq)$ 做法，即每次枚举每一个去检查是否合法。 先思考判一下平凡情况，发现有一个重要性质，考虑把 $n$ 组串转化为 $A+B+C$ 的形式，$A$ 是前缀相等的最长串，$C$ 同理。 考虑如果 $B$ 与询问串中的 $B$ 不相等就不合法，这显然是一个必要条件，还需要满足 $A$，$C$ 的相等关系。 这个必要条件显然可以 $Hash$ 一下，然后感觉有了 $O(nq)$ 做法。 之后就一直在想有没有一种字符串算法，可以去快速判断有多少个串满足 $A$，$C$ 的相等关系。 先想 $ACAM$ ，这玩意很像多模式匹配，但是发现不一定匹配到越过 $B$ 的位置，可能在 $A$ 前面会有 $A+C$ 这样的结构，直接寄了。 然后开始想两边建 $trie$ ，有点像二维数点，但是不太会将树上转化到二维平面上做。 开始疯狂想 $Hash$ ，发现不会。 中间又想了十几分钟 $T4$ ，感觉只会指数级暴力，没啥前途，果断放弃，暴力也没打。 只剩 $1h$ 了，只好打 $O(nq)$ 暴力了。 $B$ 性质应该是好做的，但是过于难判，不想打。 首先发现原来询问串长度不一定相等，有这种样例，读题时没发现，不过特判一下就好。 中间不知道在干嘛调了很久，一会临时变量没清空，一会发现二维数组开成一维了。 然后在比赛快结束时调过了。 交代码时，不断交调出一点小问题的代码，交了有 $3\sim4$ 次。 打了 $250$ 分。 还有就是赛场里特别热，连脱两件上衣，仍然觉得热。 旁边有一个小孩，好像是身体不舒服，这我能理解，但是他一直说话，一直叫老师，非常烦人。 ### 赛后 $T2$ 感觉会被卡常，忘记了可以稍微剪剪枝，就是当前答案已经大于等于之前答案，直接减掉。 现在只能看评测机了。 $T3$ 发现完全可以在 $B$ 处加一个特殊字符，然后直接跑 $ACAM$ 就行，感觉能过，赛时没想到。 然后我没有把 $n,q\le10^4$ 分进去 $O(nq)$ 的代码里，分到一个乱搞里了，不知道会不会挂。 $upd$：$T2$ $80$ 分，不加剪枝在洛谷官方数据跑了 $1.25s$ ，加上后跑了 $0.544s$ ，后悔没加。 所以 $CCF$ 评测机升级了什么啊！ $T3$ 没挂。