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 很简单。降降降。