主要思路
这也太他妈毒瘤了吧。
这个题首先肯定是要离线的，在线肯定没发做。事实上，我们可以对这个匹配分为三类：在上升链上、过 LCA 或者是在下降链上。这三者可以分开进行统计。上升链和下降链可以通过对询问字符串正反建 AC 自动机、然后在原树上做 DFS 即可；经过 LCA 的链有点难处理，发现能参与匹配的字符个数是与 \(|\text{询问串}|\) 相关的，所以我们把左右链的两个部分拼起来，然后单独跑 KMP 即可。
代码好长，狗屎一般。
Continue reading →这也太他妈毒瘤了吧。
这个题首先肯定是要离线的，在线肯定没发做。事实上，我们可以对这个匹配分为三类：在上升链上、过 LCA 或者是在下降链上。这三者可以分开进行统计。上升链和下降链可以通过对询问字符串正反建 AC 自动机、然后在原树上做 DFS 即可；经过 LCA 的链有点难处理，发现能参与匹配的字符个数是与 \(|\text{询问串}|\) 相关的，所以我们把左右链的两个部分拼起来，然后单独跑 KMP 即可。
代码好长，狗屎一般。
Continue reading →这道题其实就是考察 KMP 算法中 Next 数组的使用。题意转换过来大致就是：
给定两个 01 串，构造一个长度跟第一个串相同且 1 的个数相同的串，且保证第二个串的出现次数最多，出现可以重叠。
这道题的题意就是求能平铺成原矩阵的最小子矩阵。我们可以使用 KMP 的方法来解决这个问题。首先我们需要找出周期矩阵的横向长度，我们可以用朴素的匹配搞定这个：
这道题要求在一个循环前缀中求出最小周期长度和最大频率。我们可以用 KMP 的 next 数组来解这个问题。我们先来回顾一下 next 数组的含义。\(next[i]\)代表在区间\(str[1,i]\)中前缀后缀的最长公共部分。如果区间长度是\(next[i]\)的倍数，那么其中就有循环节。详细见代码。