题解$Boruvka$算法流程： 先对于每个点，选择在所有与之相连的边中，权值最小的边，并将这条边加入到最小生成树中。显然这样连出来的边会形成一个森林，并且连边后连通块个数至少减半。然后我们将每个连通块再看成一个点，重复以上算法即可。时间复杂度$O(mlogn)$。 例题： 给定一个$n$个节点的完全图，每个节点有个编号$a_i$,节点$i$和节点$j$之间边的权值为$a_i⨁a_j$,求该图的最小生成树的权值和。 从高位往低位贪心。把所有点按当前位为$0$还是$1$分为两类。显然在执行$Bor ...

题解$f(1)=1,f(0)=0$ $f(n)=f(n-1)+f(n-2)$ $f(n)=((\frac {1+{\sqrt 5}} 2 )^n-(\frac {1-{\sqrt 5}} 2 )^n)/ {\sqrt 5}$ 斐波那契数列任意两项和都不相等 斐波那契数列的第$n+2$项代表了集合$，， {1，2，…n }$中所有不包含相邻正整数的子集的个数 $f(n+m)=f(n-1)f(m)+f(n)f(m+1)$ $gcd(f(n),f(m))=f(gcd(n,m))$ $\frac {a_ ...

题解假设最小生成树$T$和$T’$按照权重排序后的边为$(e_0,e_1,…)$和$(e_0’, e_1’,…)$, 引入记号$E_i$和$E_i’$，分别为$T$和$T’$的第$0$到第$i$条边的集合 假设$e_k$和$e_k’$为第一对不是同一条边的位置，假设$e_k$为边$(u, v)$, $e_k’$为$(u’, v’)$，且此时$(u,v)$不在$T’$中 证明第一部分： 在$T’$中必然有一条$u->v$的路径，记为$P’(u,v)$： $P’(u,v)$不可能只包含$E ...

题解给定一个序列，要求实现区间取$min$（即区间内$a_i$更新为$min(a_i,val)$），区间求$max$，区间求$sum$。 做法： 维护区间最大值$mx$，区间严格次大值$sx$，区间最大值出现的次数$cx$，然后进行分类讨论： 　　1、$val>=mx$，明显对区间无影响，退出； 　　2、$sx<val<mx$，此时$mx$会被更改成$val$，而$sx,cx$则不变，对区间和$sum$的贡献为$(mx-val)*cx$；（此处不能使$sx=val$，否则在更新 ...

题解问题为求$\sum_{i=L}^R f(i \oplus x)^2$ 先将区间分成两个前缀的差，现在只需要考虑$[0,R] \oplus x$ 从高到低枚举最高位$w$ 设$x’$表示$x$去掉第$w$位的值 设$x^w$表示只保留$x$的$[0,w-1]$位的值 如果$R<2^w$，递归到更小的$w$进行处理 如过$R\geq 2^w$，那么可以考虑$[0,R]=[0,2^w-1]+[2^w,R]$ $[0,2^w-1]\oplus x$ $=[0,2^w-1] \oplus x^w ...

关于线性基比较经典的四道题目。

关于AC自动机比较经典的九道题目。

回文树能够以O(n)的时间求出字符串中本质不同的回文串个数（最多为n个，证明考虑每次插入一个新的后缀，如果形成的新的最长回文串不是整个串，则一定在前面插入时出现过）和其长度与出现次数。

虚树可以用来解决在树上的多次询问，约束总询问点数的动态规划问题，相较直接BFS的高复杂度，虚树可以将开销降到与单次询问点数相关的时间复杂度之内。

二分答案+差分约束系统。