爱飞鱼的blog

给出两个字符串 和 ，若 的区间 子串与 完全相同，则称 在 中出现了，其出现位置为 。 现在请你求出 在 中所有出现的位置。 定义一个字符串 的 border 为 的一个非 本身的子串 ，满足 既是 的前缀，又是 的后缀。 对于 ，你还需…

思路： 我们都知道gcd(a,b)=gcd(a,b-a) 对于多个数组而言，gcd(a,b,c,d)=gcd(a,b-a,c-b,d-c) 所以gcd(a+x,b+x,c+x,d+x)=gcd(a+x,b-a,c-b,d-c) 这就是gcd…

给你一个个节点的树，求一个的排列 ，使得最大。 求这样的排列的个数。答案对取模。 有一个n个节点的树（编号1~n）。树上的每一个边都是正值。 我们定义两点之间的距离为这两点最短路径边的权值之和。

由于准备校赛，时间比较不够用，自己写的总结和题解，就没发，现在补一下。

算法作用：(考虑1base)求文本串 T 的每一个后缀与模式串 M 的最长公共前缀长度。核心数组z[i]就表示 模板： 1.传的是0base串，函数内部会处理。 2.其次一般来说前面是模式串，间隔一个$分隔符后是文本串。这样就是可以知道文本…

小美定义一个数组的权值为：数组中任选两个数的异或之和。例如，数组[2,1,3]的权值为：(2 xor 1)+(2 xor 3)+(1 xor 3)=3+1+2=6。 小美拿到了一个数组，她想知道该数组的所有连续子数组的权值和是多少？答案对取…

距离 - OI Wiki (oi-wiki.org)已经说的比较清晰，提取要点和结论便于复习使用。 曼哈顿距离： 切比雪夫距离： 切比雪夫距离在计算的时候需要取max，往往不是很好优化，对于一个点，计算其他点到该的距离的复杂度为O(n)