爱飞鱼的blog

1.利用题目告诉的结论：1e9范围质数之差小于300 2.一个数不被2-a的任何数整除 等价于他的最小质因子需要大于a 部分细节处理：我的思路是类别用并查集维护，开了一个哈希表去存每个类别对应的根节点是最终floyd的第几个点，in fac…

https://www.acwing.com/problem/content/5367/ 题目如果只需要输出最大值，我都没有问题。每次需要输出方案的时候,我似乎都需要先统计最大值，再重新扫描一遍找所有能够取得最大值的方案，然后在这些方案中找…

换根dp: 换根dp往往需要处理去掉一个子树这样的问题，我们可以使用前后缀和的方法来优化复杂度 题意：一个国家有n个城市，n-1条道路，保证是一棵树，起初所有道路都是破旧的。对于每个点x，求以x为首都的时候修建道路使得成为完美国家的修建方案…

题意：给一个A，B构成的字符串，可以将“AB”翻转成"BA",问最多可以进行多少次翻转？ 实际上在手动模拟以后发现，由于题目限制了每个位置只能翻转一次，所以情况简单了不少。 只要还没过最后一个B，那么最后一个B之前的所有A就会被反转。真正无…

其实是道数论题。 题意可以转化为将树分割为不超过 个连通块，每个连通块颜色不同。若将树分割为 个连通块，则需要删去 条边，故方案数为 。同时，要从 种颜色中选出 中颜色染色，而且是有顺序的，故方案数为 。 综上，总的方案数为： 可以线性求逆…

简述：构建H数组完成对后缀排序。 思想在于calabashboy，实现细节和方法看dxsf。 注意细节：传入字符串0base，内部会修改成1base，传的是引用。值域都在1-n之间

回文串：S=R(S) 回文中心： 回文半径L：回文中心到回文串左右端点的距离，常用二元组来表示一个回文子串. 回文长度和回文半径的关系： P[i] 表示以 i 为回文中心的最大回文半径。

ac自动机维护的是当前状态的最大后缀满足这个后缀是字典树的前缀 Sol：将文本串放在AC 自动机上运行，求出每个前缀匹配到AC 自动机的哪 个节点，将该节点的标记值+1。这里标记的是匹配串，下面标记的是模式串 每个字典串的出现次数等于失配树…

对于一个字符串S，n = |S|，它的Border 树（也叫next 树）共有n+1 个节点：0, 1, 2, . . . , n。 0 是这棵有向树的根。对于其他每个点1 ≤ i ≤ n，父节点为next[i]。