CSP-S 2025 游记'w'

· · 生活·游记

省流：|t_1|\ne |t_2|？哦还好我判了。

Day -7 ~ -1

疯狂参加神秘的 OIFC 模考，喜提分数最大值 <200，如此水平如何 S 组？

Day -4 之后感觉自己实在太摆了，于是最后几天把 MX 和 luogu 的 S 组膜你赛 vp 了一遍，还去 vp 了 2022 年的洛谷膜你赛。已完成今日T3建议降绿原因记搜可过大学习。

Day 0

摆烂？躺尸！

看了一遍最近一个月的集训笔记，发现自己貌似越训越弱了/kel，然后拼命在群聊里发 rp++ 以增加决心。

Day 1

上午很晚才起，然后说服自己要写点代码，于是把去年 NOIP T4 树上查询补了，我去我怎么第一发挂了之后只调 8 分钟就过了，感觉 rp 大减。

中午吃完午饭 12:40 做地铁前往杭师大仓前，路上遇到一对情侣（？疑似 CSP 考生。地铁上一直在犯郁郁症，幻想自己各种爆炸。

到考场后遇到了 jianglin1 大神。开考前发生了一件很戏剧性的事：我在 2\:25 时申请去上了个厕所，回来发现解压密码报完一半了？！火速开始记忆，坐到位置上时第二遍密码已经报完了前几个字符。由于是分别记了一个模糊的后缀和一个模糊的前缀，第一遍解压密码错了，直接开始慌张，尝试等待第三次报密码。

结果那个老师在话筒里喊：就是人杰地灵这四个字的拼音。bro 那中间的数字呢？要不要大写？我更慌了，打算举手询问，然而因为我座位号是 A-02 在角落里因此无人在意。已经有一百万个人开题了，我还没拿到题面，心态爆炸了。

最后还是 A-03 的老哥给我递了草稿纸，上面写了它记的密码，666 这么复杂我猪脑过载根本记不住。在这里感谢 ZJ 杭师大仓前恕园 16 号楼 402 考场 A-03 座位的老哥，不然我可能要晚个 10min 才拿到题面。 天崩开局，rp 暴增！

大概在 2\:31 的时候开了 T1。三个部门 \le \lfloor n/2\rfloor，注意到无论怎么分至多只有一个部门不合法，那么先贪心然后看谁超了，超了的话再贪心地按照换个部门的代价最小的几个换，这样超了的部门一定会被调整到恰好 n/2，剩下俩部门一定合法，感觉很对，于是开写，十多分钟后过了大样例，优势在我！不过考场里这个时间点键盘声已经掀翻屋顶了，应该是都秒了。

接着开 T2，第一眼通过某种神秘建模然后最小生成树，但是貌似不太可做。往下滑发现 n\le 10^4,k\le 10，猜测是直接枚举开哪些乡村。注意到你开的乡村最后一定会和 1\sim n 个点连通，所以说接下来就要求连通原来的城市和选出的乡村的最小生成树，但是 m\le 10^6 显然过不了一点。这时我想起来之前集训做到过一个题，也是求很多轮最小生成树，但是每轮总是从若干个固定边集里取边。那个题的结论是，每个边集里只有在单独考虑这个边集时，最小生成树上的边是有用的。于是我直接猜，原图的边只有最小生成树上的边有用，这样复杂度直接做就是 O(m\log m+2^knk\log nk)，精细实现貌似可以做到 O(m\log m+2^knk)。快速写了一份代码，调了调后发现能过大样例，我就暂且认为这个结论是对的。

然后开始饭堂：这个瓶颈现在在对 O(nk) 条边排序上，我直接一个个归并，即维护一个 cur 表示当前按边权排好序的边，然后挨个对于 i\in S 把 cur 和连接乡村 i 的所有边（这些边提前排序）归并到一起，我赛时非常坚定的认为这玩意复杂度就是 O(nk) 的。笑点解析：如果这是对的，那么当 k=1 的时候我就发明了 O(n) 排序算法。于是我就写了个我认为的 O(2^knk)，直到出了考场后晚上失眠犯鱼鱼症时 recall 出来这复杂度踏马是 O(2^knk^2) 的。

意志上过了 T2 后才 45 分钟，我去那不是优势真在我了，开始猛攻 T3。哇竟然是串串题，稍微推了推，发现对于一个替换合法可以表示成：它们俩在询问的 s,t 中出现位置相同，并且把这两个串扣掉后 s,t 的前后缀还是一样的。然后发现，修改和询问的一对对串貌似相同前后缀挺有用的。继续头脑风暴，想了很多个 O(nL) 的方法，但是貌似都不是很牛。

思考过程中还去瞄了眼 T4，哇竟然是排列计数，感觉这种题我不太可能切掉，于是决定继续猛攻 T3。仍然考最长相同前后缀这个东西，注意到是不是对于询问串，提出它中间不相同的一段，假设分别为 x,y，那貌似可用的替换一定满足，按照相同的方法提出 x',y'，需要 x=x'\&y=y'？这稍微反证一下显然正确，而这个限制可以变成 x\texttt{\#}y=x'\texttt{\#}y' 就是中间加个特殊字符，那就考虑把所有 x\texttt{\#}y 相同的替换和询问拿出来分成一组组，组间显然不会有贡献，而每个组我们有足足 O(\text{这个组内所有字符串的总长}) 的时间处理！

继续考虑对于一个组内，一个替换的相同前缀和后缀分别为 p,q，一个询问的前后缀为 p',q'，那貌似只需要 p 是 p' 的后缀，q' 是 q 的前缀，这个替换就对询问有贡献。欸？要求一个东西是另一个东西的前缀，一个东西是另一个东西的后缀，这玩意和之前我做过的一道销售基因链很像（赛时只记得是什么什么基因），我做这道题的时候用的是建一棵 Trie，然后遍历这颗 Trie 时动态维护祖先链上所有点挂的字符串插到另一颗 Trie 的结果（当然在 dfn 序上就是矩形数点），这题也可以类似！我们把 p',p 都 reverse 一下那两个串的限制都变成前缀了，把所有替换和询问按照 p,p' 插到一棵 Trie T_1 上，遍历 T_1 时把祖先链上所有点的 q,q' 插到第二颗 Trie T_2，这可以 dfs 过程中，每进入一个点就插入，离开时再撤回插入。那么遇到一个询问再在 T_2 上查一下就能拿到所有答案！对于每个组复杂度为所有 p,q,p',q' 的长度之和（T_1 的结点数是组内所有串的串长之和），所以总复杂度竟然是线性的！（当然若写的不好，会因为删除节点时要清除所有孩子导致复杂度变成 O(L|\Sigma|)，总之还是要精细实现）我记得我推出这个伟大的做法时还剩两个多小时，我要做好整场都疯狂调 T3 的准备。

猛攻！按照 x\texttt{\#}y 分类为了稳我是把这些串插到一个 Trie 上，那么一组一定是这颗 Trie 的一个节点上存的所有串。三颗 Trie，天下无敌！写完 T3 第一版代码时一直过不去样例，为什么明明在一组的串它就没贡献呢？由于询问串的编号我定成 n+i 了，所以有些地方忘了减 n，过小样例后发现大样例挂了一堆？？怎么多这么多？合理猜测是两棵 Trie 没清干净，清干净后怎么还 RE 了？为了保证空间复杂度正确我写了一个空间回收，然后发现我把两棵 Trie 的根都扬了当废弃节点。调完这些就过了第一个大样例。

测第二个大样例发现一直 RE，我觉得没道理，怀疑是字典树深度太深爆栈了。欸怎么开大栈空间来着？我记得是什么什么 stack，坏了我忘了。一个可能的解决办法是手动模拟递归，写个事件堆栈模拟 dfs，但我可能要多开 10^7 个 int，虽然空间有 2Grecall 但是感觉很悬，我就只能赌：是它真的爆栈了。这是一场豪赌，赢下所有，或失去所有！

这个时候还剩 1h 不到，象征性的开了 T4，发现简单状压可以拿一些分，然后 m=1,m=n 貌似是好做的（只不过我只会 m=n）。写完这些暴力后我觉得应当要保守一点，我选择去给 T1 & T2 对拍。T1，T2 都顺利过了排，这个时候只剩 12min 了，我开始请神上身在每个代码开头祈求获得眷顾。赛场上估分 100+100+100+24=324。

出场后遇到了 wuyue__X，很不幸他切完前两题后 T3 坠机了，并且我得知 T2 那个结论是对的。路上又遇到了 jianglin1，哇他竟然 3 个半小时 AK 了，超级大神，简单听了一下 T4 思路发现好像是简单题？赛后补题发现 dp 状态设计完了就做完了，或者直接大力容斥。

赛后主要就在两方面犯郁郁症：T3 究竟是真 RE 还是只爆栈？T2 \bold{O(2^k nk^2)} 会不会挂成勾？

最终得分：100+92+100+24，好消息：T3 只爆栈，中消息：T2 没挂成勾。但是我本地测代码 T2 在 luogu 和 yundou 都能在 1.3s 左右过，怎么 CCF 超级量子评测机在测我 T2 的时候重云了呢？

可能可以去 WC。