ヒッチコック

_Mi2uk1_ · 2025-11-02 13:51:00 · 生活·游记

如果你不想看游记的话，可以把标题的歌听一遍。

写在最前

本来也没打好，赛后还被真伤了，呜呜。

Day -?

学 OI 的第五年终于在初赛获得了 90+ 分。

感觉 csps 也差不多该考些简单 ds 题了，复习 ds。

打 zr noip 模拟，在 T2 看到了延迟钦定来计数排列的 trick，于是学习。

10.31

早上到校补了补 zr 的题，看到 jy 妹妹在群里发了 模板 & 脑筋急转弯训练，于是开始了赛前打模板环节。

同学都在打 florr，说起来我已经一年多没玩过这个游戏了，组队刷了一下 jungle，loot 了不少 m血刺，还不错。

中午离开了 xzyz，出发盐城。晚上继续瞎看题打模板，以及在群里疯狂抽搐发电：

篮球不会说谎。于是篮球循环.jpg

也是控到人了。

11.1

体验了久违的 8 小时睡眠，感觉良好

水了水群，没找到 gartic 环节。
中午看到了普及组的题目，怎么那么简单，但是 lmx 17min ak 还是有点震撼。

不免为下午的难度捏了一把汗。

CSP-S

开场速览题目。哦牛批，怎么有字符串。

T1 懒得思考了，选择了没脑子做法，搞了三个优先队列维护，很快过了大样例，此时 14：52。

阅读 T2，把乡村和城市搞混了，成功浪费了 10min。

k 怎么这么小，考虑 2^k 的解法。考虑乡村改造类似于一个把森林拼起来的步骤，而且最后拼成的一定是一棵树，否则一定不优。
那么直接就有了一个 O(2^k(m+nk)\log(m+nk)) 的做法。注意到不在原图的最小生成树上的边一定不会被选择，所以复杂度可以降到 O(m\log m+2^knk\log nk)。

还是有点悬，考虑再提前把选出来的边和每个乡村的出边都排好序，极限会到 O(m\log m+2^knk^2)，但是严重跑不满，考场大样例只跑了 0.3s，奇异搞笑的是小样例跑了 0.5s，期望得分 [80,100]。

此时时间过了一个半小时多，还可以。

简单思考了一下 T3，先无脑打了一个暴力。然后烧烤特殊性质，发现我们关心的其实是 t_1,t_2 中间极长的不同区间，做一次替换一定要把这一段全部替换掉，要维护的有点貌似有点多，先暂跳。

T4 有点来感觉了。可以套路地设 f_{i,j,k} 表示面 i 个人 j 失败 k 待填的方案数。欲推 dp 柿子。 。 。然后突然会 T3 了。由于合法的中间极长的不同区间的替换必须是相同的，所以可以把这一段区间直接用字符串哈希处理掉。

然后考虑剩下的前缀和后缀，则对于一对可以替换的 t,s_i ，s_i 的极长相同前缀必定是 t 的相同前缀的一段后缀；s_i 的极长相同后缀必定是 t 的相同后缀的的一段前缀。所以可以用两个 trie 维护然后上二维数点就可以了。离线一下复杂度就是单 log 的，可以通过。

直接开冲 T3，呃啊，遇到了各种神秘错误，调调调，我草，怎么大样例还是 wa 的。 。 。继续调。 。 。

时间没了，还没调完，怎么办。

最后半小时严肃转战了 T4，结果也没搞完，只有暴力那少得可怜的 8 分。

18：30，屏幕变黑，映照出我叹气的脸。我知道，和 wc 无缘了。

赛后

水群，一车人 ak 了。

也许我真实水平就是这么菜吧。

坐在了回徐州的高速上。耳机里，尖锐的吉他声划过我的耳膜，翻来覆去睡不着，思考又飘回了为什么当初要学 oi 尔尔。 。 。

「先生、人生相談です。

算了，不想了。还有 noip 呢。