博客补档中
CF1558D Top-Notch Insertions
TAGS：组合数学，平衡树，线段树
考虑做完插入排序后会得到一个下标的排列 $P$。那么对于 $A_{p_i}$ 我们会得到一个连不等式，其中如果 $p_i>p_{i+1}$，连接 $A_{p_i}$ 和 $A_{p_{i+1}}$ 的便是小于号，否则是小于等于号。那么问题难度在于算出小于号个数。
平衡树：维护所有前方是小于号的下标集合，则每次需要做的事情是查询一个下标是否存在，插入一个下标，给一段后缀下标整体 $+1$，这都是可以用平衡树简单维护的。
简单做法：将整个过程倒过来，每次相当于是查询一个下标的后继，将这个后继计入答案，然后删掉这个下标。可以用线段树/树状数组维护。
NOIP2020 微信步数
TAGS：推式子，自然数等幂和
考虑每一步的贡献，则比较自然的暴力思路是枚举在走第 $i$ 步之前走了完整的 $t$ 轮，计算出满足能走完这 $t$ 轮 + $i$ 步的点数，相当于是利用了 $x=\sum\limits_{i=1} [x\geq i]$。（特殊讨论走了完整 $0$ 轮的情况）
然后大概会发现贡献关于 $t$ 的形式是一个 $\prod (a_k+t*b_k)$ 的形式，我们将其记为多项式 $F(x)$，所求即是 $\sum\limits_{t=1}^{lim} F(t)$。只需要将其每一项系数算出，再做自然数等幂和就行了。
NOIP2017 列队
TAGS：平衡树，线段树
通过观察可以发现将每一行的前 $m-1$ 个看成一个整体，最后一列看成一个整体来考虑。以行举例，需要实现的功能是弹出中间的某个数，并 push_back 一个数。因为最开始的编号是连续的，可以直接拿平衡树维护连续段，因为每次操作最多产生 $O(1)$ 个新的连续段，连续段总数是 $\mathcal O(Q)$ 的。
非平衡树做法：用 std::vector 来储存 push_back 进来的数，用一颗支持”动态删点“的线段树来查找第 $k$ 大的下标即可。
AGC038F Two Permutations
TAGS：网络流
先将问题转化为最小化 $A_i=B_i$ 的 $i$ 的个数。
因为 $P,Q$ 也是排列，可以将问题抽象为对于每个置换环的决策：每个数是选择自己，还是选择后继，记前一种决策为 $0$，后一种决策为 $1$。如此，对于某个 $P$ 的置换 $x$，$Q$ 的置换 $y$，可以讨论他们的相同元素，来得到一些形如“同时 $0$ 决策会有花费 $1$，同时 $1$ 决策会有花费 $1$，某个置换决策 $0/1$ 会有花费 $1$ “的限制。可以发现这里就已经跟文理分科的模型很像了。主要思路是考虑最小割会让每一条增广路上至少有一条边被割掉，用这个来限制得到花费。
CF1584D Strange LCS
TAGS：状压 DP
直接设 $f(c,S)$ 表示当前最后一位字符是 $c$，$S$ 状压每个序列目前是在 $c$ 的第一次出现还是第二次出现位置，直接转移即可。
CF1584C Game with Stones
TAGS：线段树，差分
考虑一次修改操作 $(i,i+1)$ 对于差分数组的影响：$d_i\rightarrow d_i-1$，$d_{i+2} \rightarrow d_{i+2}+1$。注意到修改的两个位置的奇偶性是相同的，那么可以分别考虑奇数下标和偶数下标。我们最终的目标是将差分数组的每一项都变成 $0$，显然有一个策略是每次贪心的修改靠左的位置，因此可以得到一个序列是合法的充要条件：做差分后，奇数位置和偶数位置的差分数组前缀和每个位置都 $\geq 0$，且最后一位差分数组的前缀和是 $0$。考虑从右到左扫描，用线段树维护差分数组的分维前缀和，线段树二分找到最后一个 $\geq 0$ 的位置，然后统计 $0$ 的个数。
NOIP2021模拟测试三十八 A
TAGS：贪心，DP
首先注意到将一个区间插入一个流水线中不会使得答案更优。并且如果两个区间 $x,y$ 有 $y$ 包含 $x$，则将 $y$ 插入 $x$ 所在的区间中不会使得答案变化。这启发我们先将所有可以包含某个区间的区间拿出来，单独考虑那些两两无包含关系的区间。
在区间两两无包含关系的时候，将所有区间按照左端点排序，则每个流水线取的一定是连续一段的区间，证明可以考虑交换扰动。可以 $\mathcal O(n^3)$ DP 解决。然后枚举那些被取出来的区间有多少个是单独成一条流水线的即可。
感觉要做出这题的关键，是要先意识到最优解的形态。要想到这点，可以从发现区间两两无包含时是简单贪心+DP这点出发。
NOIP2021模拟测试三十八 B
TAGS：DP，AC 自动机
发现特殊性质：字符集大小为 $2$。也就是说只有 $n+1$ 个模式串，全部插入 AC 自动机后做个简单 DP 就行了。
考场上有点梦游，一直在调一个序列 DP，完全没意识到没用到 01 串的性质，属实是呆鸡。
NOIP2021模拟测试三十八 C
TAGS：DP
考场上的设计的状态 $f(l,r)$ 表示恰好以 $l,r$ 为左右端点的回文子序列个数，然后发现要优化转移需要 KD-tree，自闭了。
实际上只要把状态定义改为这个区间内的所有回文子序列，每次考虑由 $f(l,r-1)$ 变化过来，就能直接做了。
以后转移优化遇到瓶颈的时候要记得尝试修改状态定义。
NOIP2021模拟测试三十七 丛林宝藏
TAGS：DP，值域分块平衡复杂度，差分
首先你需要知道一个支持插入，查询子集和的算法：考虑将值域分块，设 $f(x,y)$ 表示二进制表示下前 $\frac{w}{2}$ 位是 $x$，后 $\frac{w}{2}$ 位是 $y$ 的子集的数的权值和。修改时枚举第二维，查询时枚举第一位。这样子便平衡了修改和查询的复杂度。
考虑对于每个结点计算以当前节点为起点往子树里走的所有方案权值和，设 $f(x)$ 表示方案数，$g(x)$ 表示方案权值和。注意到，如果是朴素的做这个过程，每个点算答案时需要子树内所有合法信息，但是回溯到父亲后往下一个兄弟走时需要将这些信息暂时撤销，或者说是“隔离”，比较不好处理。注意到因为是权值和，所有信息都满足可减性，因此只要在 dfs 过程中将每个点的子树内的合法信息累和，记录 dfs 进入一个结点的时的信息与离开它时的信息，两者相减即可得到子树内的信息。
CF809D Hitchhiking in the Baltic States
TAGS：DP，DP 优化，平衡树
显然可以写出 $\mathcal O(n^2)$ 的 DP：$f(i,j)$ 表示迭代到第 $i$ 位，$\mathrm{LIS}=j$ 的最小结尾数字。因为是要求的严格递增子序列，$f(i,*)$ 也是严格递增的。
观察转移相当于是将一段区间平移并加 $1$，用平衡树维护即可，注意讨论一下边界情况。
CF1103D Professional layer
TAGS：DP，DP 优化
显然只有 $gcd$ 以及 $gcd$ 的质因子是需要考虑的，$gcd$ 的质因个数 $m$ 至多是 $11$，那么很容易能得到一个 $\mathcal O(n\cdot 3^m\cdot m^2)$ 的暴力状压 DP，考虑优化。
首先，每一个数的作用相当于是覆盖一个质因子子集。我们可以注意到，对于一个质因子子集，在所有能够覆盖它的数中，只有花费前 $m$ 小的才是可能被用上的。
然后有一个很神仙的性质：对于每个数只保留其在 $gcd$ 中出现过的质因子后，至多有 $M=14000$ 个不相同的数。那么我们在最外层枚举这 $M$ 个数，然后算出其能覆盖的质因子集合，保留前 $m$ 小的花费，然后直接做 $\mathcal O(m\cdot n\cdot 3^m)$ 的 DP 转移。还需要进一步的优化，在这个过程之前先预处理出每个子集能够覆盖它的数中花费前 $m$ 小的，在 DP 转移第二层枚举子集的时候发现当前决策的花费用在当前子集上绝对不优的时候，就不要再去枚举这个子集的超集了。这样子 DP 部分的复杂度就是 $\mathcal O(m^2\cdot 3^m)$。其他杂七杂八的部分复杂度大概是 $\mathcal O(M\cdot 2^m \cdot m^2)$。
JOISC2017Day3 幽深府邸
TAGS：势能分析，暴力优化
考虑对于每个点计算出其能走到的极大区间 $[l_i,r_i]$ 后即可 $\mathcal O(1)$ 回答询问。
考虑暴力计算 $[l_i,r_i]$ 的过程，即每次交替的尝试拓展左端点和右端点到目前的极远端点。注意到，如果某一次左端点扩展到了位置 $j$，则可以直接将 $l$ 移动至 $l_j$，那么一次暴力移动一格 $l$ 的过程可以认为消耗了这个位置的势能，因此总共的移动量是 $\mathcal O(n)$ 的，剩下的问题是需要优化拓展右端点的过程。
JOISC2018Day3 比太郎的聚会
TAGS：根号分治，归并
询问点数有总规模限制。我们所熟知的解决这类问题的算法一般有虚树，数据分治，本题中无法刻画出良好的静态树结构，因此考虑根号分治。
对于 $qtot\geq T$ 的询问，直接做 $\mathcal O(n+m)$ 的 DP。
对于 $qtot<T$ 的询问，我们考虑对于每个点 $x$ 预处理出能够到达 $x$ 的点中距离前 $T$ 小的点。具体实现可以在拓扑排序的时候用归并 $\mathcal O(T)$ 来做单次合并。
注意如果你每次归并的不是两个数组而是 $deg$ 个数组，归并的复杂度会多出一个 $\log$。
ZR联赛集训Day16 字符串
TAGS：SAM
把反串 SAM 搞出来后，可以很方便的比较两个串的字典序。考虑如何快速计算 SAM 上某个结点所代表的串中是否存在合法答案。显然只需要一个支持查询“相邻 endpos 之差第 $k$ 大”的数据结构，可以用各种手段解决。
ZR联赛集训Day16 交叉路
TAGS：LGV，手动消元
根据 LGV 引理，答案行列式 M 有 $M(i,j)=\binom{a_i+j}{j}$，做若干次初等列变换后可以得到 $M(i,j)=\binom{a_i+1}{j}$。然后将每一列的公因数 $\frac{1}{j!}$ 提出来就会得到一个下降幂行列式，显然是等价于范德蒙德行列式的。注意到值域较小，做一次减法卷积即可算出范德蒙德行列式的结果。
ZR联赛集训Day16 中位数
TAGS：DP，性质
用调整法很容易说明如有解，则存在一种方案使得每个 $a$ 都等于限制它的小于等于 $3$ 个 $b$ 中的某个。那么在状态里压一下前两个 $a$ 选的是啥就能直接 DP 了。记忆化搜索会比较好实现。
ZR联赛集训Day16 最小团
TAGS：Heap
注意到是要求第 $k$ 小，以及点值非负，则可以用类似 Dijkstra 的方法来扩展团。注意要缩减边数。
ZR联赛集训Day15 大清扫
TAGS：DP，分治
考虑用 CDQ 分治优化 $\mathcal O(n^4)$ DP。
ZR联赛集训Day15 水管工
TAGS：结论，DP
考虑另外一个问题：在最开始在每条树边上放置两根可以区分的水管，在每个点处自由匹配与其相连的边上的水管（每个点的匹配情况独立）。注意到在求出一种基本方案后，会有 $2^{n-1}$ 种方法来交换每条树边上的水管编号。再进一步观察，对于两条相同的水管对应的路径上的边，如果将这些边上的水管编号交换将会得到一种一样的匹配方案，因此一种放置水管的方案将会对应 $2^{n-1-c}$ 种不同的匹配方案，那么现在只需求出匹配方案即可。显然答案是只与每个点的度数相关的，设 $f(i,j)$ 表示目前有 $i$ 个点对以及 $j$ 个被破坏的点对（仅剩一个独立点）的匹配方案，在转移的时候优先考虑最靠后的独立点，或者点对中最靠后点的匹配方案。可以发现以这样子的策略转移每一时刻的独立点个数是不会超过 $2$ 的。
清华集训2014 主旋律
TAGS：状压 DP，容斥
设 $f(S)$ 表示导出子图 $S$ 不是强连通图的方案数，容斥有：$f(S)=\sum\limits_{T\subset S,T\neq\emptyset} \sum\limits_{k\geq1} (-1)^{k+1}\cdot g_k(T)\cdot2^{E(T,S-T)}\cdot2^{E(S-T,S-T)}$，其中 $g_k(T)$ 表示将点集 $T$ 划分成 $k$ 个 SCC 的方案数，然后设 $dp(S)=2^{E(S,S)}-f(S),G(S)=\sum\limits_{k\geq 1}(-1)^{k+1}\cdot g_k(S)$，则会有转移式：$G(S)=dp(S)-\sum\limits_{T\subsetneqq S,T\neq \emptyset} G(T)\cdot dp(S-T)$。复杂度 $\mathcal O(3^n+m)$。
NOIP2021模拟测试三十五 拆分
TAGS：多项式
题目大意：求 $x^n^p$，$n\leq 10^7,p,m\leq 10^3$。
先用斯特林数把 $\sum\limits_{i} i^m x^i$ 拆开：
$$
\sum\limits_{i} i^m x^i&=&\sum\limits{k} \begin{Bmatrix}m\k\end{Bmatrix} \sum x^i i^{\underline k} \
&=& \sum k\begin{Bmatrix} m \ k\end{Bmatrix}F_k(x) \
$$
根据有限微积分，$(i+1)^{\underline k}-i^{\underline k}=ki^{\underline {k-1}}$，我们将 $F_k(x)$ 的系数错项相减得到 $F_k(x)=\frac{kx}{1-x} F_{k-1}(x)$，已知 $F_0(x)=\frac{1}{1-x}$，因此 $F_k(x)=k!\frac{x^k}{(1-x)^{k+1}}$。
代回原式得到 $\sum \begin{Bmatrix}m\i\end{Bmatrix}i!\frac{x^i}{(1-x)^{i+1}}$，发现可以提取一个 $\frac{1}{(1-x)^{m+1}}$ 的公因数出来，得到 $\frac{1}{(1-x)^{m+1}} \sum \begin{Bmatrix} m\i \end{Bmatrix} i! x^i (1-x)^{m-i}$，设和式中的内容为 $G(x)$，显然可以发现 $G(x)$ 的最高次数是 $m$。因此求出前 $m$ 个 $i^mx^i$，与 $\frac{1}{(1-x)^{m+1}}$ 做 $\mathcal O(m^2)$ 的卷积即可得到 $G(x)$。
现在答案相当于是要求 $[x^n] \frac{G^p(x)}{(1-x)^{(m+1)p}}$。$G^p(x)$ 的系数可以多项式 ln + 多项式 EXP 计算 $\mathcal O(mk \log {mk})$ 计算，而 $\frac{1}{(1-x)^{(m+1)p}}$ 的特定项系数，相当于是插板法，因此暴力卷积即可。总复杂度 $\mathcal O(n+mk \log {mk})$。
CF1158F Density of subarrays
TAGS：DP，数据分治
考虑往选出子序列右端加数的过程，假如当前密度为 $p$，则所有长度为 $p+1$ 的前 $p$ 个字符都能被凑出来，缺少的是最后一个字符。因此在某个时刻密度变为 $p$ 后，不停的加数直到 $c$ 种数都被加入后密度会变成 $p+1$。
有了这个性质我们可以写出一个 DP：$f(i,j)$ 表示当前子序列长度为 $j$ 且正好以 $i$ 结尾的个数，转移的时候需要枚举第 $i-1$ 个字符的位置，那么还需要计算 $g(l,r)$ 表示在 $[l,r]$ 中选出一个有 $c$ 种数字且最右方数字恰好出现一次的方案数。怎么算 $g(l,r)$？固定 $l$，枚举 $r$ 递推即可。注意到根据最上面的性质，子序列的密度不会超过 $\frac{n}{c}$，因此这个 DP 的复杂度是 $\mathcal O(\frac{n^3}{c})$ 的。这启发我们对于 $c$ 较小的数据采取其他的算法。
可以采用状压 DP，设 $f(i,j,S)$ 表示迭代到 $i$ 密度为 $j$ 且用于 $j+1$ 的元素集合是 $c$ 的子序列数。这个算法复杂度是 $\mathcal O(\frac{n^2 2^c}{c})$ 的，分析可知阈值 $c$ 取 $\log_2 n$ 最优。
CF1142D Foreigner
TAGS：DP
可以注意到在一个排名为 $k$ 的数后面接上一个数字 $c$ 所产生新的数字 $k’$ 的排名是：$\sum\limits_{i=1}^{k-1} (i \bmod 11)+c+10$，这启发我们可以只关心模 $11$ 意义下的排名，记 $f(i,j)$ 表示迭代到第 $i$ 位后排名模 $11$ 余 $j$ 的数的个数。
21 ZR联赛集训Day14 字符串
TAGS：分治，DP，随机数据的性质
考虑有一个 $\mathcal O(nm^2\log n)$ 的分治 DP：分治区间 $[l,r]$ 时计算所有 $i_1\in[l,mid],i_m\in(mid,r]$ 的序列。那么只需要枚举在左边区间匹配了多少位，然后做两遍 DP 即可。
注意到数据随机，也就是说在暴力 DP 时每迭代到新的一位时，期望只有 $\frac{m}{|\sum|}$ 个 DP 数组中的位置被修改。
21 ZR联赛集训Day13 都
TAGS：位运算，DP，线性基
首先考虑枚举 AND 和 $x$。如果 $x$ 非 $0$，选出数的总数必须是奇数。考虑将所有是 $x$ 超集的数拿出来，将 $x$ 的 $1$ 数位删掉，从这些数中选出奇数个异或和为 $0$ 即是一组合法的方案，可以 DP 或者线性基解决。比较棘手的是 $x=0$ 的情况，考虑刚刚那个过程中算出来的选出偶数个数的方案，一定会满足真实异或和为 $0$，AND 和是 $x$ 的超集，那么再套个 IFMT 即可。
21 ZR联赛集训Day13 很
TAGS：状压 DP，矩阵树定理
翻译一下合法导出子图的定义：最多存在一个简单环。
先考虑一个环都没有全是树的情况。考虑给“所有联通块大小的乘积”编一个组合意义：从每个连通块选出一条边连到一个虚点造出一整棵大树的方案数，那么直接在最开始给每个点都连一条向虚点的边，生成树个数即是答案。
然后考虑存在一个环的情况，只需要枚举这个环上的点，然后将其缩成一个点，再跑树的部分即可。为了处理环的方案数，使用状压 DP，在最外层枚举一个环的起点，设 $f(i,S)$ 表示目前走到了环上的点 $i$，已经走过了 $S$ 中的点集，转移枚举 $i$ 的后继即可。注意此时一个环会被计算 $2\times size$ 次，需要除掉。
21 ZR联赛集训Day13 简
TAGS：状压 DP，优化状态
首先如果 $\prod a_i\geq x$，所有的排列都一定是好的。把整除 $1$ 的函数都拉出来单独考虑贡献，则剩下的整除函数最多只有 $13$ 个。考虑状压 DP $f(S,i)$ 表示已经选了 $S$ 集合中的整除函数，目前值为 $i$ 的方案数。转移考虑枚举下一个选择使用的函数。对于取模函数，我们可以注意到在某一次使用了一个函数将 $i$ 变为 $i’$ 后，所有 $(i’,+\infty)$ 的取模函数都不会对值有任何影响了，因此可以将这部分取模函数直接用组合数来分配位置，所以扩展 $f(S,i)$ 的定义为此时所有 $(i,+\infty)$ 的取模函数已经被分配完位置了。
21 ZR联赛集训Day13 单
TAGS：数据结构
题目可以转化为最开始有一个上三角全是 $1$ 的矩形 B，做 $2n$ 个矩形乘法，然后多次查询矩形和。
首先考虑离线扫描线扫描行，同时维护每一列的前缀和，那么查询就可以变为两次区间求和。
考虑在没有乘法的时候，扫描到第 $i$ 行时要对 $[i,n]$ 做一个区间加 $1$ 操作。把乘法操作差分后可以抽象为下面这个模型：
维护一个序列，序列上的每个位置有一个权重 $v_i$，每次做区间加法的时候每个位置的实际修改量需要乘上权重 $v$，需要支持区间权重乘法修改，还有区间求和。
为了支持维护上面的模型，建出一棵线段树，永久化维护乘法标记，以及子树内的乘法权重之和，子树之和。
上面的模型拓展性极强，往后遇到形如“矩形乘法，矩形求和”的题目都可以考虑使用上面的维护方法。
ARC058D Iroha Loves Strings
TAGS：DP，exkmp
我们有暴力 $\mathcal O(nk^2)$ DP：设 $f(i,j)$ 表示考虑前 $i$ 个串凑出来的长度为 $j$ 的字典序最小的串。考虑优化暴力。
考虑两个状态 $f(i,j),f(i,k)$，如果用 $[i+1,n]$ 的串能拼出长度为 $k-i,k-j$ 的串且 $f(i,j),f(i,k)$ 两者中某个串字典序较小且不是较大串的前缀，则较大串是一个无用状态。借助这条性质，我们可以将 $f(i,*)$ 中的无用状态删去，最终留下的有效状态所呈的形态应该是一些两两有前缀包含关系的串，因此只需要记录最长的母串以及每个合法状态的长度。
做第 $i$ 轮转移的时候，从小到大枚举 $j$，并同时维护一个存放合法状态的单调栈。算出 $f(i,j)$ 后，可以根据其与栈顶的字典序比较关系与长度比较关系决定是否弹栈以及是否入栈。
最后需要解决的问题是转移过程中的字典序比较。在计算 $f(i,j)$ 时，相当于是要比较第 $i-1$ 轮的母串的某个后缀与第 $i$ 个串的字典序。在维护单调栈时，比较的两个串一定都是第 $i-1$ 轮母船的某个前缀或者是某个前缀接上第 $i$ 个串，这显然都是可以 exkmp 的。
复杂度为 $\mathcal O(nk+\sum len_i)$。
NOIP2021模拟测试三十三 WTP的野心
TAGS：FWT，SG 函数
显然策略是要尽量多选 $\sum p_i$ 大的点。从大到小枚举 $x$，考虑每个 $\sum p_i=x$ 的点，只需要考虑其连边连向的总和大一点的点。如果其连边的点都没有出现在已选集合中则可以选，否则不能选。可以发现这个过程非常像有向图博弈，那么所有必败态的点就是最大独立集中的点。我们知道可以用 SG 函数来描述有向图博弈，又因为每一位独立可以做 Nim 和，用 FWT 加速异或卷积即可。
NOIP2021模拟测试三十二 四十分
TAGS：结论
3 个关键结论：
- $\forall i<j<k, i\oplus k>j\oplus k$，可以类比后缀排序。
- $|i-j|\leq i\oplus j$，比较显然，可以借此得到答案的下界。
- $\exist k<2|i-j|,(i+k)\oplus (j+k)=|i-j|$，证明考虑从低位开始补。
因此就可以直接做了。
NOIP2021模拟测试三十二 要被卡
TAGS：图论，DP，观察
考虑对于两个黑点 $(x_1,y_1),(x_2,y_2),x_1<x_2$，如果 $|y1-y2|=1$ 则连一条有向边。则需要求出最小不相交路径覆盖。
要证明一个路径覆盖能对应一种方案是非常简单的。
我们知道最小不相交路径覆盖的暴力做法是将每个点拆成一个入点与一个出点，算二分图最大匹配。考虑转化为求二分图最大独立集。
因为一条边相邻的两个点的纵坐标奇偶性不同，可以将原图划分成两个不相干的部分分别算最大独立集合。将每一列的点按纵坐标排序后，其连出去的边一定都是形如一段前缀或一段后缀的形式。因此可以得知独立集中点的选取也是形如一段前缀或一段后缀，直接 DP 即可。
21 ZR联赛集训Day10 人生经验
TAGS：DP 套 DP
先考虑使用 DP 判定一个串是否合法。设 $g(i,a,b)$ 表示是否存在一种消除方案，使得在前 $2i$ 个字符的后面补字符 $0$ 最终将得到字符 $a$，在前 $2i$ 个字符的后面补字符 $1$ 最终将得到字符 $b$。转移的时候进行刷表，则需要枚举第 $2i+1$ 个字符在合并过程中是先参与前面 $2i$ 个字符的合并还是先参与后面两个字符的合并。
考虑计数问题，DP 套 DP 即可。设 $f(i,a,b,c,d)$ 表示前 $2i$ 个字符填出 $g(i)$ 数组取值情况为 $a,b,c,d$ 的方案数。
AGC001D Arrays and Palindrome
TAGS：构造
实际上是要造出一个连通块。
考虑 $m=1$ 的简单情况，造一个 $n-1,1$ 的 $b$ 数组即可。这启发我们在普适情况将边平移。
可以发现，如果只是简单的像上面一样将边平移，显然不会有任何浪费的边，但是这样子可能会有边数不够的情况。我们需要保证 $a$ 数组与 $b$ 数组中的奇数个数总数不超过 $2$，因此将 $a$ 排列成奇数块在两端的情景后再平移得到 $b$ 即可。
21 ZR联赛集训Day8 拼接
TAGS：SAM，DP
考虑以这样一种方式将一个串唯一的映射：对于 $s_i$ 的子串 $t_i$，无法将 $t_i$ 的最后一个字符删除，留给后面的子串匹配。
转化为在 SAM 上走的问题。在第 $i$ 个 SAM 上的某个结点时，可以决策走一条转移边或者跳到下一个第 $i+1$ 个 SAM 的开始结点。
考虑要保证映射的唯一性，如果在某个 SAM 结点时有一条字符为 $c$ 的转移边且没有选择走这条转移边而是来到下一个 SAM 的话，以后在 SAM 的开始结点时都不能走字符为 $c$ 的转移边。
需要采用哈希表或者 std::unordered_map。
CF1566E Buds Re-hanging
TAGS：思维
减少叶子数的手段是将 Bud 结点移到一个叶子的儿子中。可以发现 Buds 是一个非常有用的战略资源，我们考虑将所有的 Buds 先移到根结点的儿子中，然后此时至少 $tot-1$ 个 Buds