士力架不会哈希 || CSP-S 2025 游记

· · 生活·游记

推荐在 cnblog 看，因为洛谷不会实时更新喵！同时欢迎来 cnblog 来和我贴贴。

注意到 cz 发话「但是游记中不应包含暴戾语言（包括但不限于“唐”）」，所以以下的「tang」将用「🍬」代替。

似乎没什么非常非常特别的事情发生，虽然并没有打的很好，但起码也过了 AB，有了 200pts 保底，所以也不算很差。

唯一的也是很严重的缺点就是，C 明明是个串串题却没想到哈希，很不应该。因为哈希尽管不一定能过掉，但也能拿到相当可观的分数了。

NOIP 加油。/fendou

贴贴区

@ImposterAnYu 贴贴 /qq。可怜，摸摸安雨姐姐喵 /kel，安雨姐姐 NOIP 加油呀qwq
@Synthesize 贴贴 /qq。 你分数不挺高的嘛，已经吊打我啦qwq
@Lemansky 贴贴 /qq。怎么没怎么学还和我差不多分，不过中考加油喵！
@Vsinger_洛天依 贴贴 /qq。姐姐可爱呐！同样 NOIP 加油呀！
@jrzhr 贴贴 /qq。你明年才高一呀喵。
@Mortidesperatslav 贴贴 /qq。奶猫太强了吊打我了。/ll
@Dream_poetry 贴贴 /qq。面积成功（1/1）
@HeYilin 贴贴 /qq。拿了我徽章拍了合照就跑了、
@_ImposterX_ 贴贴 /qq。意外的面积。
@qifan_maker 贴贴 /qq。MC 服务器挺好玩的（
@tyr_04 贴贴 /qq。
@Kaf_yoU 贴贴 /qq。

Day -3

开坑。

模拟赛 +1

无事发生。

Day -2

上午下午都打模拟赛 /tuu

然后上午模拟赛有 0 个大样例，下午有 2 个大样例。。不过下午比赛超级水，应该是信心赛了，原谅了。

在线求助如何进入决心商店。

【考虑到要投全站推荐，图就不放了，不过可以去 cnblog 看】

/se

Day -1

上午随便补了补昨天的模拟赛。

11:58 出发，据说是教练特意选的时间（

下午到了之后，打了打 tarjan 板子，这个是怎么都记不住的。不过即使记住了也要打一遍点双边双板子，因为你猜 SPJ 的 AC 信息是啥。

然后吃饭！和以前不一样的，这次终于不是盒饭了，而是蓝海的喜宴，这个真的吃爽了 w

试机

晚上试机。

可以面到 @Dream_poetry 和 @HeYilin 喵！开心喵！

然后 dp 说要带个同学过来帮我们拍照，于是意外地面到了 @_ImposterX_，幸亏多带了一个徽章（

嗯，dp 问我了一些事，然后放出来似乎不太好，就不放了吧 ww

::::info[合照]

::::

然后试机的时候，可能是 rp 比较充足，随机到了一个软凳子带靠背的机房，当时还以为这次都是这样的来着，出来后听同机房大神 @yuanyifan6 抱怨凳子不合适，才知道原来是我们考场专属。

抽到了合适的椅子，赢，但是似乎会 rp--（？

晚上回来直接睡了。

Day 0

早饭是自助，还是不错的。

上午随机写题，写了 P4555、CF1326D2、P3674。

然后水了会儿群。

这样。

正式比赛

总之是到了下午开始比赛了。

先在监考老师还没说不能动键盘的时候敲了个缺省源。

14:30 准时发解压密码，发现压缩包有两层，不知道为什么。

至今仍然记得密码是 Ren4Jie5Di4Ling5%，翻译过来是「人杰地灵」，不知道什么意思。

花了 20min 读题。怎么有串串题，是 Manacher 被加入导致的吗，不过这也不是 Mnancher 题啊。

顺序开吧。A 开始以为是 dp，但是发现复杂度太高了根本过不去，思考 10min+ 之后发现可以直接反悔贪心呀，写写写，与 15:20 左右过掉了所有大样例。

100pts 到手了能晋级了，已经赢麻了。

开 B，嗯这个 k 这么小大概率是要 O(2^k) 枚举的，然后似乎再能乘上一个 n 就没了。但是 MST 复杂度里无论是否排序都要带个 m 的呀？这咋办？

难道要用 Prim？可是我 Prim 都忘完了呀 /jk

于是花了 10min 来尝试发明 Prim，然后没有发明出来因为无论怎么样发现复杂度里面都带个 m，于是放弃了。

（赛后发现我是正确的，Prim 的复杂度是 O(n \log n {\color{#66CCFF}{} + m})。

忽然（真的是忽然想到的，不知道咋想到的）想到跑一遍 MST 就可以只留下 n-1 条有效边了呀！那我先对初始图跑一遍 MST 复杂度里是不是就不用带 m 了！

真的。然后就得到了 2^k 个 O(nk) 条边的图，都跑一遍 MST 最终复杂度是 O(2^k nk \log (nk)) 的，达到了恐怖的 2e9，1s 完全过不了。

考虑优化。先是发现排序是多余的，因为可以直接先对每个关键点的 n 条边排个序，然后写个 dfs，归并地合并两个排好序的边集，就可以把 log 换成 \alpha 了。

不过这样还是 >1e8，但是也不怎么会进一步优化了，于是开写。

最开始想二进制枚举，但是为了省点常数，选择了可以继承状态（边集）的 dfs 写法。

代码有点长，写了我 30min 才过掉了所有大样例。

然后构造一个极限数据，只有连向 n 的边的边权为 10^9，剩下的都 < 10^9，这样应该就可以卡满了，一测发现跑了 1.2s+，就算改成纯随机也有 1.1s+，虽然 CCF 少爷机吧但是还是担心呀……毕竟明确给了这个做法的部分分，那大概率会被卡掉的。

不会优化了，想先开 C，但是在又测了一遍大样例的时候，忽然想到上面那个优化还能继续用啊！dfs 过程中每次跑一遍都可以得到 O(n) 条有效边，那每次 MST 复杂度不就是严格 O(n \alpha(n)) 的了吗！哦还有个 2 的常数，不过问题不大。

写写写，不出意外没过样例，瞪了 20min 发现【忘了哪里】犯🍬了，改了就过了，一测极限数据跑了 900ms+，感觉已经很稳了。

开 C，这是什么？似乎可以 ACAM？诶不过似乎要在两棵 ACAM 上同时跑匹配，如果直接计数的话复杂度是 O(L_1 L_2) 的，如果最后在 fail 树上拓扑排序的话复杂度是 O(q L_1 + L_2) 的，这都过不了啊……不过 q=1 倒是有 50pts 的部分分（包含暴力），似乎可以写写？不过好像非常难写，而且此时只剩 1h 多一点了，感觉不一定能写出来。。

想 C 的期间吃了个士力架，不过似乎并没有起到任何作用。士力架不会哈希。

然后经过长达 >1min 的 battle，决定直接去打暴力 KMP，这样复杂度是 O(L_1 L_2) 的，能有 25pts，写写写……

……喜提忘了 KMP 怎么写了（）于是又花了 10min+ 发明了 KMP，小样例过了，没给这一部分的大样例。发现怎么随便搓个数据就 T 掉了，哦两个串需要分别 KMP，改了就过了，造了几组也没什么问题。

但是只剩下 30min 了，感觉 C 的性质 A 可做，然后先把 D 的 8pts 暴力打了，回来打 C 的性质 A，但是已经没时间了，而且做法也不是那种很一眼的，最后拼拼凑凑写出来一个错完了的做法，样例过不了一点，注意到有一坨 0 于是写了个不可以总司令就没有然后了。

最后 10min，又拼了拼 C 的性质 A，不过没拼出来，查了一遍文件就交了。

估分：100 + 100 + 25 + 8 = 233

暴力没打满！暴力没打满！暴力没打满！暴力没打满！暴力没打满！

遗憾离场。/ll

哦好像并没有非常遗憾，问了问同考场的同学，似乎都没有过掉 AB。

然后我对 AB 的预计难度是黄绿。

出考场教练跟我说 C 是哈希。？草！

教练不让互相说估分，起到了一定的作用，车上一路无话。

晚饭有饮料了好评。

晚上复盘。写写写 A 过掉了，BCD 都没数据于是有理由不写去水群了。悲报：一会儿 B 数据就有了，然后我还没写完，于是只能回去写了，然后死活调不出来了（

从教练口中得知同机房大神在没学过反悔贪心的情况下，用反悔贪心过掉了 A，还是太超标了，估计他早学一年就足以吊打我了。/ll

笑点解析：考场上开 B 到过 B 大概用了 1h 多一点；赛后直接写 B 到调出来用了得有 1.5h。这就是状态的差别吗。

然后一交 B，怎么 RE 了一个点 /jk，不过问题不是很大，嗯，只有 4pts，不过这是民间数据啊万一官方数据卡这个不就寄了（，关键是我甚至不知道哪里 RE 了。。

CD 依然没有数据，不写了！

期间水群的时候，发现某群里部分群 u 心情不怎么好，于是和安雨姐姐贴贴了一会儿qaq，@ImposterAnYu 贴贴喵！

现在属于是通宵也没人管了，放飞自我，考的好不好的明天再说。注意到 @qifan_maker 有个 MC 服务器，于是拉舍友 @Cookie_King 和 @largestbug 一起去玩，然后两个群 u 也来了，一直玩到 2:20 左右。

然后他们都睡觉去了，然后我看了眼洛谷，发现 D 有数据了，云斗 ABCD 都有了，于是把 CD 写掉了，一测 D 稳稳的 8pts，但是 C 挂完了，云斗只有 10pts /jk，甚至在复盘的过程中发现了一个🍬氏错误，把 i \ge r-1 写成 i \ge l 了！虽然加上了也只能多 5pts 吧。。

感觉要寄。

睡了。

Day 1

起床，并没有想象中的那么困，吃完早饭后写了会儿游记，就要返程了。

车上惊奇地发现并没有很困，于是去玩小岛时光了，虽然有点降智但是是真的可爱喵 ww

不过一会儿还是困了，然后睡了一觉就到了。

回家。发现不少 OJ 都有数据了，于是测了测，发现我的 C 得分似乎是个随机数。

哦对了洛谷是数据挂了，修了之后我是没有 RE 的。

洛谷：100 + 100 + 30 + 8 = 238 信友队：100 + 100 + 25 + 8 = 233 云斗：100 + 100 + 10 + 8 = 218 核桃：100 + 100 + 10 + 8 = 218 梦熊：100 + 100 + 0 + 8 = 208

怎么 5 个 OJ 测出来 4 个分啊喂（

然后翻了翻犇犇和 QQ 群，又从教练口中得知同机房大神 @QiMingFFF C 写了个神必哈希得到了相当可观的分数，甚至梦熊数据拿到了 96pts。。

草不是，才发现 C 有一大坨哈希做法，我考场上都在想啥啊（

串串题还是做少了，哈希这么好的东西怎么就没想起来呢。怎么就没想起来呢。怎么就没想起来呢。/fn

又去看了看题解区发现 ACAM 是完全可做的，把限制变换一下形式就是 ACAM 板子了，草我真糖丸了。。

怎么说呢。串串题做的还是太少了，就基本上没做过，唯一做过的几个还是当时 MX 云智课上讲的例题……

要恶补串串了。/fendou

诶怎么有 20120712 个人没有注意到 |t_1| \ne |t_2|，我注意到了但是注意到了也不会做的说（）

## Day 2 补题。 C 赛时少了一点很重要的观察，就是在对所有模式串也记录掉公共前缀 / 后缀之后，问题就会简单很多了。 ACAM 做法是[这样的](https://www.luogu.com.cn/article/5n06yvwp)，有一个很神人的映射，到底是怎么想到的啊。。 **民间数据**：有了这个之后直接跑匹配的复杂度可以被卡到 $O(L_1 L_2)$，不过大多数情况是不会被卡的，能拿到 [85pts](https://www.luogu.com.cn/record/245096297)，然后结合 $O(qL_1 + L_2)$ 的在 fail 树上拓扑排序做法，可以拼出来一个根号分治，那么复杂度就是类似于 $O(L_1 ( \sqrt {L_2} + \sqrt q))$ 的东西了，取 $B = 2300$ 过掉了，最大点 [1.24s](https://www.luogu.com.cn/record/245100214)。然后又试了试，发现 $B = 6000$ 快到起飞，最大点只用了 [1.04s](https://www.luogu.com.cn/record/245135560)，在 xyd、[MX](https://www.mxoj.net/submission/detail?answerId=374619&contestId=541) 上也过掉了，不过[云斗](https://www.yundouxueyuan.com/record/690892fe94e4fc6ce93f4a6b)、[核桃](https://htoj.com.cn/cpp/oj/problem/detail?pid=22550016844928&cid=22553048423936&tab=3&submitId=28220939)会 TLE 85pts。 然后正经做法，是 trie + 二维数点。说实话以前 ZR 模拟赛遇到过这个 trick 来着（[Day 1 T3](https://zhengruioi.com/problem/3379)），但是因为题解没看懂没补，有点后悔了。/ll ## Day 4 出分。甚至是从申诉才能查到的。CCF 神力。 **100 + 100 + 5 + 8 = 213** 还是被卡了。唉。。 然后 D cout<<0 能有 4pts，忘记写了属于是。 有人发现 C 官方数据根本不存在 $|t_1| \ne |t_2|$ 的情况，这么逆天？ 然后 B 卡掉了 $O(2^k nk \log (nk))$ 没卡掉 $O(2^k m)$ 甚至都没卡掉 $O(2^k m \log m)$，这什么神必数据。 逛了逛犇犇，发现 100 + 80 + 25 + 8 = 213 似乎是一个大众分，我过了 B 挂了 C 正好匹配到大众分是吧（） 和云斗数据正好一个分，那是不是排名也会差不多了，rk210 应该能有个 1=，不过勾 7 不怎么可能就是了。 笑点解析：2023 S 橙蓝蓝蓝 140pts 能有 rk210，2025 S 黄蓝紫紫 213pts 依然 rk210，人类进化不带我是吧。 ## Day 13 出分数线了。SD 131 1=，60 2=，30 3=，赢！