如果有写的不好的文章欢迎评论，我会在有时间的时候重写一篇更好的。
全是定义和结论，没有证明
LuoguLOJ分析首先注意到学校选择导师和选择派系是等价的。考虑 $k=0$ 的情况。则此时城市选择阵营与学校选择派系独立，可以分开处理。设 $f_{i,j}$ 表示前 $i$ 个城市有 $j$ 个人在蓝阵营的方案数，$g_{i,j}$ 表示前 $i$ 所学校有 $j$ 个人在鸭派系的方案数。转移即为 0/1 背包。最后卷积合并即可。考虑 $k\neq 0$ 的情况。注意到有限制的学校数很...
LuoguLOJ分析先考虑一个贪心。我们把 $d_i$ 从大到小排序，那么每个子树都对应一段区间，我们把儿子按照编号排序，然后把区间依次划分下去即可。这样子只能通过所有 $d_i$ 互不相同的点，原因是在 $d_i$ 相同时可以通过一些交换使得编号小的点的 $d_i$ 变大。考虑修正这个贪心。我们维护 $c_i$ 表示 $\leq d_i$ 的可用的难度的个数，那么节点 $u$ 只能选择 $...
LuoguLOJ分析问题相当于选出恰好 $k+1$ 条点不相交的路径使得权值和最大，这里 $1$ 个点也算一条路径。先考虑一个朴素 DP。设 $dp_{i,j,0/1/2}$ 表示以 $i$ 为根的子树、选了 $j$ 条路径、$i$ 的度数为 $0/1/2$ 的最大权值和，转移讨论各种情况把子树合并进来即可。设 $f(k)$ 为选恰好 $k$ 条点不交路径时的最大权值和，通过打表或者感性理解...
LuoguLOJ分析首先容斥一下，求出三段都不包含 $s_{l..r}$ 的方案数，然后用 ${n-1\choose 2}$ 减掉即为答案。我们先把所有和 $s_{l..r}$ 相等的子串位置都找到，然后分类讨论一下：如果有三个互不相交的串，方案数是 $0$。如果最左边的串和最右边的串相交：考虑 $i$ 的位置：如果 $i\in[1,l_1)$，那么 $j\in(l_m,r_1]$，方案数为...
LuoguUOJ分析考虑对每棵子树计算其 SG 函数值，即为每种删除情况得到的若干棵子树的 SG 函数的异或和的 mex。于是我们要想办法求出每种选择情况得到的 SG 函数异或和的集合。如果选择根节点，得到的就是它的每棵子树，子局面的 SG 函数值即为每棵子树的 SG 函数值的异或和。如果选择了某棵子树中的节点，那么相当于这棵子树的 SG 函数异或和的集合异或上了其它子树 SG 函数值的异或...
LuoguLOJ分析首先把第 $k$ 大转化掉：不妨再设一个 $g_{i,j,k}$ 表示子树 $f_{i,j,k}$ 的和，并设 $G_{i,j}(x)=\sum_k g_{i,j,k}x^k$。答案即为 $\sum_{i=k}^n[x^i](\sum_j G_{1,j})$。看起来这个转移并没有什么可以优化的地方。但是 $F_{i,j}$ 和 $G_{i,j}$ 的最高次项都是 $x^n...
LuoguLOJ分析容易想到一个图论模型，即从每个 A 类串向它所支配的 B 类串连边，从每个 B 类串向以它为前缀的 A 类串连边，并将所有 A 类串的权值设为长度。这样问题变为求最长路，如果有环输出 -1。第一类边可以直接连，但第二类边暴力连显然不行，考虑一些优化。对反串建 SAM，此时 Parent 树上每个点的祖先都是它的前缀，于是我们只需要将树上每个 B 类串对应的节点向子树中所有...
LuoguLOJ分析走的路径应满足起点、终点的度数为奇数、其它点的度数为偶数，这个条件长得很像欧拉回路。我们首先把 $m$ 条关键边连上，然后再在起点、终点间连一条边。这样子会有一些度数为奇数的点，显然相邻的两个间连一条边是最优的。这样子满足了度数限制。但是我们还需要让图连通。我们把所有连通块缩成一个点，然后求最小生成树，那么可以花费最小生成树上边权和的两倍的代价让图连通起来。时间复杂度 $...
Codeforces分析先判掉只有一种数的情况，答案显然为 $0$。再判掉原序列中有两种出现次数都是最多的数的情况，答案显然为 $n$。那么现在出现次数最多的数唯一。找到这个数，设为 $x$，那么有结论：答案段出现次数最多的数一定是 $x$。这是因为如果某一段出现次数最多的数不是 $x$，那么我们可以每次把这一段增长 $1$，根据介值定理，此过程中一定会有 $x$ 的出现次数等于原来最多的出...