根根又号号

· · 生活·游记

DAY-?

被 nfls 信心赛击杀。

xxx 问我要不要复习 AC 自动机。

AC机就是trie+KMP

:不打算复

:困困难难

伏笔说是。考完被编了。

DAY-1

进考场，开题。看到串了。吐吐吐。

发现 t1 是个反悔贪心，不能放进最大一定能放进次大，写写写，挂了，改改改，过了。到 15:05。

看 t2 发现显然保留 n-1 条边枚举城市化的城市每次跑一遍最小生成树就好了吧，发现有 80，写写写，写完跑了。发现大概 1.5h。

t3 看错题了，愤怒思考 10min 替换多次，困难。跳去 t4 了。

t4 看完题写完暴搜。

重新看 t3 发现题读错了。写暴力，t_1 跟每个 s_1 跑一遍 kmp 然后再用 hash 判断一下前缀后缀 t_1,t_2 是否相等以及替换这段的 t_2 是否等于 s_2，改改改发现过了。

写完暴力尝试性质，发现 A 性质的 q=1，猜测复杂度是 O(qL_1) 的做法，想想想，不会。

然后忽然发现 len>\sqrt{L_1} 的 s 二元组数量不会大于 \sqrt{L_1}，而小于 \sqrt{L_1} 的直接暴力枚举替换的子串。

于是根号分治，写写写，改改改，大样例大 1，无敌暴怒。最终输输输。交了暴力。

100 + 80 + 25 + 8 = 213 (?)

堪比去年 noip 被 t2 击杀。

赛后继续调根号分治调调调，发现哈希写错了，改改改过了。卡卡卡，把 |t_1|\ne |t_2| 判掉。改的子串 t_1:[l,r] 显然 l 只能在 [1,|LCP(t_1,t_2)|+1] 中，r 在 [|t_1|-s,|t_1|] 其中 s 是最长公共后缀长度。枚举部分貌似就从 q\cdot L_2\cdot B 优化到了 \frac{L_2}{B}\cdot L_1。

所以两部分最差都是 L_2\sqrt{L_1}。并且多数情况下都跑得及其不满。考场上调出来是不是能有一车分啊。哭哭哭。

然后改改改，大样例跑出了 5s，但是过了 luogu、熨斗自测（？）。气笑了。

但是如果 t_1=t_2 还是会被卡成原来的复杂度，不过这种情况就是 AC 自动机模板了。

蠢蠢蠢。怎么都觉得 T1 很简单。降降降。