01串
对于相邻的两个段和 \(S_i\) 和 \(S_{i+1}\) 两段之间移动时的差别既删除了 \(i\) 号元素，添加了 \(i+K\) 号元素。如果 \(S_i = S_{i+1}+1\) 那么说明 \(i\) 号元素是 \(1\)，\(i+K\) 号元素是 \(0\)。（删除 \(1\) 添加 \(0\)）,反之如果 \(S_i = S_{i+1}-1\)，那么 \(i\) 号元素是 \(0\)，\(i+K\) 号元素是 \(1\)（删除 \(1\) 添加 \(0\)）。这两种情况都能唯一的确定两个位置。
如果 \(S_i = S_{i+1}\)，那么只能说明 \(i\) 号元素和 \(i+K\) 号元素相等，并不能说明其具体的值。我们对这样的元素之间连边，表示相等关系。
那么在构建的图中，一些点已经被确定，一些点没有被确定，但是通过连边关系也能被确定。通过 BFS 可以求出所有已经确定的点。
接下来，对于前 \(K\) 个元素，我们计算其中还需要补充的 \(1\) 的个数 \(a\) 和尚未确定的位置 \(b\)，答案既是 \(C(b,a)\)。从 \(b\) 中任意选 \(a\) 个填 \(1\) 即可。
翻转匹配
分类讨论
对于 \(|T|=1\) 的情况，只需要判断 \(S\) 中是否有对应字符
对于 \(|T|=2\)，\(T_1 \neq T_2\) 的情况，假设 \(T\) 是 \(01\)，一定是需要把 \(S\) 变成 \(11111\cdots 00000\cdots\)，那么每次操作就需要将一段连续的 \(1\) 移到前面，答案就是连续的 \(1\) 的段的数量 \(-[S_1=1]\)。
对于 \(|T|=2,T_1=T_2\)，假设 \(T\) 是 \(00\)，那么意味着 \(S\) 中不能出现连续的 \(0\)。首先通过 \(0\) 的个数是否超过一半判断有解无解。在有解的情况下，任意两个相邻的 \(0\) 都需要一次操作去破坏掉，计算有多少对相邻的 \(0\) 即可。
对于 \(|T|=3,T_1\neq T_3\)，此时如果 \(T\) 多次在 \(S\) 中出现，相互没有交，并且一次操作只能破坏掉一个位置。此时答案是 \(T\) 在 \(S\) 中的出现次数。
对于 \(|T|=3,T_1 \neq T_2\)，假设 \(T\) 为 \(010\)，那么 \(1\) 在不作为前后缀时，长度不能为 \(1\)。那么一次操作我们可以合并两个长度为 \(1\) 的不作为前后缀的 \(1\) 串。答案是 \(\lceil \frac{段个数}{2} \rceil\)。
对于 \(000\) 的情况，那么不能出现长度大于等于 \(3\) 的 \(0\) 串。首先判断 \(0\) 的个数是否无解(是否大于 \(\lfloor \frac{n}{3} \rfloor + n \bmod 3\))。
对于一次操作，我们相当于从两个连续段中分别扣除 \(a\) 个 \(0\) 和 \(b\) 个 \(0\)，再分别添加 \(b\) 个 \(0\) 和 \(a\) 个 \(0\)（实际上是一个交换的过程）。那么也就是有若干个串允许增加 \(1\) 或者 \(2\) 个 \(0\)，有若干个串需要减少若干个 \(0\)。我们希望步骤尽量少，既尽量一次减少两个 \(0\)。贪心即可。
建筑修缮
称一个数在山谷里，当且仅当在左边和右边都有严格比它大的数。
观察这样一个过程，将所有在山谷里的数的最小值整体 \(+1\)。
每次操作 \((i,j,k)\)，\(h_j\) 带来的代价是固定的，我们需要尽可能最小化 \(h_i,h_k\) 带来的代价。先将这些数中最左边和最右边的数 \(+1\)，然后操作中间的数就可以令 \(h_i\) 和 \(h_k=h_j+1\)，非常划算。为了最小化最左边和最右边的数操作的代价，可以算出先左后右，先右后左的代价。这是一个求一段前缀/后缀中某个数后继的问题，可以选用自己喜欢的数据结构维护。
然而 \(h\) 的值域非常大，令 \(x\) 为目前的山谷里的最小值，\(y\) 为 \(x\) 在所有 \(h_i\) 中的后继，将所有山谷里的最小值从 \(x\) 加到 \(y\) 的过程中，由于需要改变的数的集合不变，可以整体处理，而这个集合只会改变 \(O(n)\) 次，故复杂度是 \(O(n\log n)\) 的。
旅行商问题
当K=1时：
交易员必须时刻不停的获取收益，寻找1开始的最长链即可。
当K=2时：
使用树形dp：
设dp1[u]为从u点出发，停在u的子树内的最大价值。
设dp2[u]为从u点出发，停在u的某个儿子或者u本身的最大价值
设dp3[u]为从点u的某个儿子出发，停在u的子树内的最大价值。
那么我们梳理一下具体的构造方式,其中rev()代表把路径反向,v1,v2,...,vk代表u的儿子
方式1：dp1[u]=u->rev(dp2[v1])->v2->...>vk->dp1[vk]
方式2：dp1[u]=u->dp3[v1]
方式3：dp2[u]=u->rev(dp2[v1])->v2->v3->...->vk-1->vk
方式4：dp3[u]=v1->v2->...->dp2[vk-1]->u->dp3[vk]
方式5：dp3[u]=dp2[v1]->u->rev(dp2[v2])->v3->...->vk-1->dp1[vk]
当K=3时
当K=3，交易员可以获取所有的收益，构造方法是：
u->rev(DFS(v1))->rev(DFS(v2))->...rev(DFS(vk))。这样的方式可以遍历所有的点，只需要构造出对应的路径即可。在dfs的过程中标记是否需要反转路径，该标记决定点u是先插入到vector还是后插入到vector即可。