CSP-2025 游记 - Xiao_Xiao_Yu

· · 生活·游记

大家好，这里是 Xiao_Xiao_Yu（或者你可能听过我的另一个名字叫做 BoredYukolin），大概是敝人的首篇游记吧，说实在的敝人真的不擅长写这种东西，但是也并不打算写给别人看，只是给自己留作纪念，免得日后退役了连一点留痕都没有。

因为已经是年级顶到上限的老人了，选择继续走 OI 的路线只能孤注一掷，至少本场 CSP-S 已经发挥得问心无愧了，或者说有一点不甘但已经看淡了。

T1

贪心是很好想到的，原本打算走自然的路线即在贪心过程中就判断方案是否非法，但敲的过程中感觉到某些 a 相等的情况估计会有玄学的分类讨论，停下来思考一番后发现其实可以先全贪然后反悔一部分，就非常好写了。

然而不知道敝人的脑回路当时是什么状态，维护动态插入和查询最值居然想到的是用 set，然后发现小样例没过，调试了一下发现自己连 set 会去重都没意识到，然后就改成了 multiset，然后就输出正确了，但是发现跑得出奇的慢，这时敝人才终于意识到其实直接用堆就可以了，于是欢快地修改成了 priority_queue 以及相应的成员函数。

然后，敝人从开考 20 分钟，直到结束前 15 分钟的检查环节都没有意识到 priority_queue 是大根堆，原先取 *s.begin() 改成 s.top 后就变成取最大值了。好在最后检查是否有漏掉注释输出时发现小样例莫名奇妙又挂了，遂改正。

T2

看到所有乡镇都能和任意城市修路且花费全都不同的时候以为自己读错题了——然后自己瞎猜了一个题意，而不是重新读，直到看到 k \le 10,n \le 10^4。

注意到这个耐人寻味的数据范围后，很自然冒出了二进制枚举乡镇的想法。但是一算 O(2^kmlogm) 直接跑 MST 炸飞了，是的敝人不会写 Prim，而且确实 T2 也这么简单就不合常理了（虽然 NOI 系列出现这种事也不稀奇），遂开始往一些奇奇怪怪的方向思考，包括但不限于：

然而均无成果，逐渐暴躁，在演草纸上胡算一通发现用这个朴素的复杂度其实就能水 64 分，如果算上性质 A 还能多水 8 分。在当时已经经过的时间看来写这么多已经相当划算了，但是不死心认为自己可以磨出正解，于是先去钻研了一通 T3。

结果是 T3 写了一半发现码量有一点大，因为前车之鉴本着保险的心态扭回去把 T2 老老实实写完。最后总感觉少了点什么，发现这题没有多测而且是求最小代价，于是加了一个卡时骗分，预估分数增加 eps。

事后在 LA 中看到有人说并查集没开到 n+k 的时候心里咯噔了一下，其实写下此文时自己也记不清楚自己会不会挂在同样的地方了，看了一下如果会挂的话最多会挂 32 分，随便吧。

T3

字符串一直是敝人的弱项，除了字符串哈希就不会几个算法，不过看完题目感觉题意至少很好理解，入手点也挺多的。一度觉得这题十分像是要用到 KMP 或者 AC 自动机，但都没有复习，只能从其他的方面硬钻。

盯了一会第一个小样例，不知怎么就发现了一个性质：把 s_1,s_2,t_1,t_2 都按照类似题目中说的拆分成 x+y_1/y_2+z 的形式，其中 x 和 z 是最长公共前后缀，那么一对 s 对于当前询问的 t 可用等价于 y_{s_1}=y_{t_1} \wedge y_{s_2}=y_{t_2}，且 s 的公共前后缀等于 t 中的 y 两边相应长度的子串。

于是爆敲了半天的哈希，中间又扭回去把 T2 写了后再回来时间也还算充裕，也继续写完了，虽然这个思路是最坏情况下 O(qn+L) 的，也就是 50 分，但是大样例都跑过了。

然后就是相信大家都知道的锅了：敝人没有注意到题目并未保证 |t_1|=|t_2| 也就没有判断长度不相等的情形。不过相比一些使用了 string 直接会 RE 炸飞的选手来说，敝人应该算是相对好一些的，因为用字符数组不存在越界的问题，顶多是哈希过程中混入了一部分 '\0'，又因为直接取了 t_1 的长度当成两个串长度，除非忽略 t_2 的多余部分后恰好有非零答案，应该问题都不大。看人品了。

T4

没什么好多说的，一开始以为能写 n \le 18 的部分，剩下输出 n!，但很快发现自己的状压 DP 状态设计不对，而且存在 c_i=0 时直接输出阶乘显然是不对的，于是拿了 8 分跑路。

你知道吗

后记

写于 2025 年 11 月 2 日晚。