蒟蒻 の CSP 2025 游记

· · 生活·游记

CSP-2025游记（总结）

绿勾了一年终于要一雪前耻了！

Day-0

倒是没有感觉特别大的压力啦，不过最后一场模拟赛居然T3爆0！这给我极大的不安感......

晚上精神状态：啊！Manacher我忘了，快复习！！！ 啊！平衡树我不会，赶紧学！！！啊啊啊啊什么啊。

晚上睡觉不知道怎么个事压力一下子就飚上来了，好可怕好可怕，还好听宝宝巴士睡着了。

Day-0.5

早早起床来到机房，结果发现别人全到了，好家伙一个比一个卷 早上也没什么时间的说，随便开电脑翻了翻发了亿点RP++就准备 入场了！！

Day-1

CSP-J

考前心中默念：AK...AK...AK...

拿题一看：666一年比一年水 30min 就做完了还写什么总结....

预估分：100+100+100+100=400pts

实际得分：100+100+100+100=400pts

CSP-S

坏了我们机房全是大佬，压力！！！！！

刚拿T1那一刻直接给我上午打来的自信全干完了，怎么感觉有点小难，瞅了一眼数据范围，发现 n 很大，猜测是贪心做法，随便推了推发现可以从最优策略调整， 20min 打完T1拿到 100pts 。

打完T1想起要先看题的说，先把后 3 题的题目看了一眼，感觉T2很可做（不可做我可以退役了）显然在确认点集的情况下的最优解就是 MST，又发现 k 很小暴力 2^k 枚举点集即可做到 O(2^km\log{m}) ，复杂度太大，显然过不了。但发现 n 较小，于是把一开始的 MST 先保留，再对每个点集跑 Kruskal 可以做到 O(2^kkn\log{n}) ，沿用刚才思路，对于每个子集保留 MST ，做到 O(2^k(k+n\log{n})) 。 不太对劲啊，这好像不太能过的样子，思考5min想到瓶颈在于排序，而每次求出的 MST 都是一个有序序列，如果将点的连边也提前排好序，两个有序序列就可以做到 O(n) 合并，于是简单预处理即可做到 O(2^kn𝛼(n)) . 感觉 1s 还是有点不太行，不过应该能过了，反正大数据只用了 500ms ，没什么大问题，此时过去了1.5h ，拿到 200pts 。

还有时间，T3看上去也比较可做，尝试一下。一开始题目看错了，以为是换了一次还能继续换问方案数，那 s_{i ,1}=s_{i ,2} 不成无限种了？过了一会才发现看错了，原来只能换一次，那就好做了，很容易想到字符串匹配，找到极长的一段不同的子串，现在能换的充要就相当于满足存在一个 s_j 的子串使得 s_{j,1} 的这一段与 t_{i,1} 匹配，s_{j,2} 的这一段与 t_{i,2} 匹配，并满足其他地方都相等，哈希判断可以做到 O(nq) , 拿到 250pts 。容易发现 s_j 的极长不同子串长度也必须相等，因此可以对极长不同子串哈希对相同哈希值单独判断，复杂度降了很多，O(q\times玄学) ，拿到 [250,270]pts ，此时还有 2h 。

然后我就糖了！瞪了半天想什么字典树啊树上差分啊，双字典树怎么匹配啊！！！瞪了 1h 没想出来，换了换思路，诶！既然除中间以外都需要满足相等，那不就是字符串匹配？？？有道理，把中间替换成#，跑 ACAM ，哇我太聪明了，赶紧打了出来，此时还有 30min ，前面数据都过了，大数据也差不多，哇塞！300pts ，保险起见，先打个大数据对拍，怎么错了......欧布！虚空调试20min终于在比赛快结束前发现手残写了个跳到根节点就返回......欧克，极限调出T3，复杂度 O(L_1\sum) ,瓶颈在于...初始化？？？不管了，跑不满，拿到 300pts 。

T4,em...暴力都没来得及打就Over了，早知道打快点，中间不摸鱼还能再拿 20pts 暴力，加容斥+m=n 高达整整 36pts 啊！！！

预估分：100+100+100+0=300pts

正常发挥：100+100+70+36=306pts

超常发挥：100+100+100+36=336pts

实际得分：100+100+100+4=304pts？？？神秘T4我最后一分钟输出了个0给了我4pts？

结果乍一看感觉还不错？但其实蛮有问题的，T3有赌的成分在里面，我赌我能调出来，万一没调出来不仅T3扣 50pts ，T4暴力我也没拿，赛场上千万不要学我，求稳才是最正确的，而且在我调很久都调不出T3的时候应该果断放弃，T4暴力+m=n特别简单，最低得分也可以达到 100+100+50+24=274pts 而且还能留出很多时间，显然是比打T3正解含金量要高得多，此时再想到容斥可以再拿 m=1 的点，+12pts ，打T3性质B，+20pts ，最低得分 306pts 。

所以说暴力是特别重要的！！！！ 特别是CSP，一般都会给特别多部分，一定先拿部分分！

Day-2

赛后才是压力最大的说，于是我在家玩了一整天

题外话

  1. 不是T3T4是不是放反了啊，T4比T3好写多了啊...很自然的一道计数

  2. T234都有点小卡常，T4还好，CCF全开1s真的没问题吗？

  3. 听说一大堆人没判\lvert{t_{i,1}\rvert}\ne\lvert{t_{i,2}}\rvert ? 还好我判了，默哀默哀

upd：合着根本没有 \lvert{t_{i,1}\rvert}\ne\lvert{t_{i,2}}\rvert 啊？