某菜鸡的 2025 CSP-S 游寄

· · 生活·游记

2025 CSP-S 游寄

博客园链接

总体来说，我前半场的失误都在可接受范围内，后半场因为太贪心，着急，以及学知识学死了三个问题直接爆炸。估分 100 + 100 + 0 + 0 = 200

T1 我做得非常流畅，开考 20 分钟就切了。

T2 我开始没反应过来 MST 后有用的变会变成 O(n) 条，就先跳过了。通读完 T3 T4 后，发现还是 T2 最可做。

后来又yy认为 n=1e5，以为 O(n2^k\alpha(n)) 过不了，卡了一会，不过及时反应过来并且写了这个题。

因为代码范了少量糖市错误，大概在开考 1 小时 50 分钟的时候过了大样例。

前半场范的错，都是可接受的失误，所以写完 T2 我的心态非常好，但接下来的决策可谓是一错到底。

首先我发现之前 T3 读错题了，我之前以为可以进行多次替换，所以觉得这个题不可做，但实则不然。读对题意后我又觉得这题非常非常可做（感觉这个题确实容易给人这样的错觉呀）。我又盲目自信地认为我字符串学的比较好，就想着一定要写 T3 正解。但事实上我只对 SAM 比较熟悉。这就是我范的最大的决策错误。

因为这个题和字符串匹配有关，我就下意识的认为此题可以被 SAM 水掉。于是我先画了大概 15 分钟回忆 SAM 并且打了个板子。这也导致我思维被固化，是学知识学得太死了导致的。

我大概想了 30 分钟，想到了一个可能正确但是复杂度是 O(|L1|+|L2|\log^3n) 的超级麻烦做法，预估可能需要 2~3 小时才能写+调出来，于是放弃了。我有花了大概 10 分钟想了个 O(|L2|+q|L1|) 的做法，大概有 50 分，这就好写多了，但是我估计还是要个 1.5 个小时才能写+调出来。

这时候只有一个小时多一点了，我想着 T4 暴力还没打，必须先想一下 T4，这个决策算是比较正确的了。

开始因为没看到 c_i 可以等于 0，以为性质 A 只需要输出 n! ，浪费了少量时间。我继续思考性质 A 如何做，比较自然地想到了一个 O(2^n\operatorname{poly(n)}) 的 dp 做法，发现可以得 0 分。然后我发现这个做法稍加拓展就不依赖性质 A，于是可以得 20 分。于是我就开始写了。写完了还调了巨久，大概离考试结束 30 分钟的时候调出来了。

我又想到了 A 性质是可以 O(\operatorname{ploy(n)}) dp 做的，具体来说就是把原本记录“每个点是否被选的这一维状态”改成“还剩多少个人的 C 大于当前未录用的人数”即可。但是这个做法其实没有想的非常清楚，并且我觉得我再 T3 投入的沉默成本很高，必须要得点分，于是去写 T3 的 O(|L2|+q|L1|) 的写法。现在复盘的时候发现这是一个非常错误的决策。原因是时间太少导致我有点失去理智了，整个人都非常急。

最后的一点点时间，我当然也没有把 T3 暴力写完。

考试结束的时候，我惊奇的发现我 T4 的暴力交成了 T2 的代码。我当时整个人都懵逼了！然后我光速回忆了一下，想起来我当时是复制了虚拟机里面的代码，然后因为心急，搞忘了虚拟机的剪贴板和外部环境的剪贴板不互通！于是直接复制成了 T2 的代码，导致 20 分暴力直接蒸发掉了！血的教训，警示后人：无论如何都要检查一遍交的代码是否正确。

这就是我后两个小时得到了 0 分的全部过程。最本质的原因是因为我在之前训练赛的时候老是想去冲正解，之后最后不到 5 场比赛我才去想办法打了暴力，导致我在处理暴力分的经验还比不上很多同学，导致痛失了很多分。这次汲取了经验教训，在后期的训练中我会注重暴力分，希望在 NOIP 能取得好成绩。