CSP-S 2025 游记

· · 生活·游记

没什么事干，写写游记。

今年是水母中学 OI 最黑暗的一年。

去年 NOIP 之后就没有什么做题的欲望了，能筹集就筹集，基本没怎么做过题。

暑假也没来集训，国庆之后全停也不知道在干嘛，反正能筹集的时间都拿来筹集了，实在抽不了就刷刷红题，入门赛甚至还在排行榜第一页，不愧是我。

和去年一样，CSP 怎么能不 CS？比赛前一周撞上了体艺节，于是在 CS、d5、B 站、学姐和体艺节之间不停切换，一点题都没碰过。

比赛那天上午拿到了手机，那只能打排位了啊。

在本校比赛一点紧张的感觉都没有，今年也没有包袱了，考的怎样都不重要，能进 NOIP 就行。

打开题目之后还是一点做题的欲望都没有，能拿多少分算多少。

T1 第一眼没有什么思路，很快把 dp 的可能性排除了，应该是简单贪心。然后会了，但是思路有点繁琐，随便写写，20 min 写完。

然后过不了样例，又调了大概 15 min 发现多测未清空。老了啊。

T2 感觉不太能做啊，看数据范围感觉跟 2^k 有点关系，就去看 T3 了。

感觉这个 T3 比较能做，思考了 10 min 无果选择先搞 T2。

然后我大胆猜测这个 m 没有什么用啊，那么排序取前 n-1 条边好像就行了。但是我也不知道对不对，那就先写着吧，不对的话应该也能拿点分。

然后就写了一个 \mathcal O(2^kkn\log kn) 的做法，最后一个大样例跑了 1.7 s 左右，我以为这是最大的数据点了，感觉 CCF 的少爷机应该能过就没管它了。

结果赛后有人和我说这不是最大的数据点，出题人你有素质吗，那要挂至少 20pts 了。

做到 T3 只剩下 2h 了，我不会 AC 自动机啊，感觉正解应该是 Trie 树 和 哈希 吧。

一直想不到怎么在 t_i 里面找子串和 s_i 相同，那我只好打暴力了。

那直接枚举要替换的子串，枚举的字串长度一定得是 s_i 出现过的。模拟赛的时候做过和这个差不多的东西，怎么推的我忘了，但是好像枚举的复杂度是根号级别的。

但是我也懒得算这个复杂度，写个指数级别的我也认，虽然不太可能，反正多拿一分都是我赚，就算拿不到又能怎？

然后我是真的太久没做题了，哈希怎么打我都忘了，写了一个 \mathcal O(N\log \text{mod}) 的复杂度的预处理，其中 N=5\times 10^6,\text{mod}=10^9+7。

赛后我发现他妈的这个预处理在洛谷都要跑 1s 了这你受得了吗。

有个 \log \text{mod} 是因为我用快速幂求逆元了但是为什么我要这么求。

当时两个要模的数相减没有加上模数导致有可能有负数一直没有过大样例，我还以为哈希冲突了，写了我从来没有写过的双哈希，然后又调了大概 20 min 才发现这个问题，妈的。

太久没做题了导致今年一堆蠢比错误，我真服了。

第三个大样例跑了大概 2 s，第四个大样例跑了大概一分钟答案好像是对的。我点开一看每个 s_i 的长度都不一样，成功把我做法卡到了复杂度上限。我没话说了怎么出题人对着我卡，good。

T4 感觉完全不可做，AB 性质都是什么玩意，一个都不会。2^n 也不会啊，我只会 n!。那没办法了，尽力了。哦还有个 m=n 是送的。

赛时的估分是 100+100+60+12=272 的。

但是 T2 原来打的不是正解啊，那应该只有 80 pts 了，但是我又把 T3 的代码重写了一遍，在洛谷有 85 pts，但是你妈的在熨斗获得了 0 pts 的好成绩因为预处理已经超时了。把预处理的 \log \text{mod} 优化之后在洛谷就有 90 pts 了，在熨斗 AC 了。这么说这题我的得分在 [0,90] 之间吗。

那我是不是可能连两百分都没有了啊，不过反正今年都退役了，不重要。