CSP-S 2025 游记

· · 生活·游记

9.20

没啥好说的，过了就行。

进考场，诶，怎么是一个巨大体育场？桌子比去年高，但是为啥不让带水？渴死了。（忘说了，syj 怎么回来了，orz）

尽可能慢地做完了所有题，又用 20min 检查了一遍，啥都没检查出来，结果还有一些时间，睡不着，罚坐。

结束之后发现又看错题了，错了 2 个，95.5。

10.20

前几天去游学了，游学回来集体甲流，歇了两天好了。

今天改成线上上课，直接没进 classin 教室卷了一天题（不过物理化学上了）。

结果被语文英语老师发现了，分别通过课代表和家长的方式联系到了我，没关系，我直接说自己发烧，哈哈哈哈哈哈哈。

10.21

继续在家卷，但是感觉今天做的题有点难，效率没有昨天高啊，不过没关系，至少磕出来一个黑。

11.1

前几天忘了写了，转眼就到 11.1 了。

早上看了一些题，复习了一些模板，但都没有写代码。

CSP-S 2025 RP++!

期中终于考完了，来写一下游记。

14:20 到考场，发现怎么是去年 NOIP 的考场？？？键盘拿不上来，难受。

斜对面 @yangyang1000 坐在我去年 NOIP 的位置上。

开场秒 T1，然后发现 CE 了，欸我怎么写了个 #include <bist/stdc++.h> 还四个题都错了？？？改了一下，14:39 交了上去。

T2 看了一下，我怎么只会 80 啊？？？决定先写，有时间再想 100 / 卡常。14:59 过大样例，好像是 0.3 出头，没有交。

T3 第一眼哈希，显然中间有修改的将字符串分成两段。之后简单思考会了一个根号做法，感觉卡不满很能过但不太保险，没写。

继续思考怎么满足这个条件，思考了半天 map 维护哈希值无果，后来忽然想到 trie，然后又想到 AC 自动机，于是抛弃之前的全部想法，会了一个 fail 树上倍增的做法，此时大概 15:50。

写了一会儿，又调了挺长时间，后来才发现 fail_i 不一定小于 i。。。又加了个 dfs，发现了可以 s_{i,1}=s_{i,2}，一遍过所有样例，大样例最慢 0.5s，16:30 交。

开始思考 T4，想了 30min 之后感觉还没什么想法，决定先打暴力。思考一会儿后，发现我会 B 性质，于是开始一个一个打。

之后发现 B 性质可以过 $n\le18$，遂先打 B 性质，发现我的做法是 $O(2^knk)$ 的（是不是很眼熟？），其中 $k=\sum\limits_{i=1}^ns_i$。感觉不太能过，所以优化到了 $O(2^kk^3)$，而且完全跑不满，大概没问题。 打了好久，调了好久，调的过程中发现可以用类似 B 性质的贡献延迟做 A 性质，但时间不多了。大约 17:50，终于过样例了，这样就有 $52$ 分。 只用了 15min 写完了 A 性质，然后发现样例根本过不去，遂在 18:10 放弃并提交 T4，回去给 T2 卡常。 思考了一下，还是不太会，于是只好把 sort 改成归并，没想到竟然快了好多，大样例 0.15s，而且瓶颈在输入，CCF 少爷机应该能过了吧，18:25 提交。 估分 $100+[80,100]+100+52=[332,352]$。 回家之后发现 T3 要判 $|t_{i,1}\ne t_{i,2}|$，那不是寄了？？？ ## 11.5 出分了，我怎么只过了一个题？？？ $100+80+80+56=316$，好像 T3 也被卡常了。 ## 11.6 感觉这次还是又暴露了不少问题吧，虽然确实高联考完才恢复训练，但 T2 T3 两个题都被卡常还是太不应该了。 赛后发现 T2 加个卡时（只用一行代码的小技巧，一定不要忘了）或优化复杂度都可以轻松通过，而 T3 可以通过两种简单方式避免倍增做到线性。 以后正赛中时限紧的题一定要测极限数据，跑不过可以尝试优化复杂度或卡常，多学些卡常技巧！希望以后再也不要被卡常了！ 另外我不久前刚做过 ARC207A，为什么 2h 没做出 T4 呢？可能还是对自己不够自信吧，全国会 A、B 性质不会正解的也没几个人了。 好在这次是 CSP，我还有时间。 最后的不到一个月，成败在此一举。