A. Interesting Paths

只保留能够被 $1$ 到 $n$ 的路径包含的点和边，则答案为边数 $-$ 点数 $+2$。

注意到每次新加入的边一定是若干条路径，且如果大于一条或路径经过了某个已经经过的点，则可以分多轮依次加入。因此最优解中，每次新加入的边都是一条路径，且除首尾外，经过的点都没有出现过。这样的路径满足边数 $-$ 点数 $=1$，算上最初的 $1$ 和 $n$，答案就是边数 $-$ 点数 $+2$。

时间复杂度 $O(n+m)$。

B. Roars III

考虑固定根的情况，有一个显然的贪心算法：自底向上，每个顶点合并子树的人所在顶点集合，如果该顶点没有人，则将子树内最深的人移至该顶点（实际上是链上的点都往上移一步，但是等价）。

需要支持集合的合并、求最大值、删除最大值。可以使用左偏树维护，可持久化以后自然可以实现换根。换根时不能直接使用顶点的深度了，而是需要在每个点处 $+1$，因此需要维护加法标记。

时间复杂度 $O(n\log n)$。

C. Radars

注意到，所有格子都被覆盖等价于四个角落都被覆盖。枚举四个角分成若干集合的所有方案，然后对每个集合找到一个雷达全部覆盖的最小代价，然后求和，即是该方案的代价。找到所有方案的最小值即是答案。

时间复杂度 $O(n^2)$。

D. Xor Partitions

设 $f(i)$ 表示长度为 $i$ 的前缀的所有划分方案的权值和。则 $$ f(i)=\sum_{j=0}^{i-1}f(j)\cdot (a_{j+1}\oplus \cdots \oplus a_i) $$ 令 $S(i)$ 是 $a_i$ 的前缀异或和，将异或和拆位，令 $g(k,c)$ 表示 $S_i$ 的第 $k$ 位为 $c$ 的 $f(i)$ 之和，即可在 $O(\log A)$ 的时间内转移。

时间复杂度 $O(n\log A)$。

E. Pattern Search II

可以注意到，我们可以找到一个 $S_n$ 使得 $|S_n|=O(|t|)$，使得答案可以在 $S_n$ 中被找到。

这是因为，设 $n$ 是最小的非负整数满足答案能在 $S_n$ 中被找到。如果 $n\ge 2$，$S_n=S_{n-1}S_{n-2}$，因为答案不在 $S_{n-1}$ 或 $S_{n-2}$ 中，所以答案一定是 $S_{n-1}$ 的一个后缀加上 $S_{n-2}$ 的一个前缀。因为 $S_n$ 中没有相邻三个相同的字符，所以答案的长度一定是 $O(|t|)$，而 $S_n=S_{n-1}S_{n-2}=S_{n-2}S_{n-3}S_{n-3}S_{n-4}=S_{n-2}\underline{S_{n-3}S_{n-4}}S_{n-5}S_{n-4}$。如果 $S_{n-4}\ge 3|t|$，则答案可以在 $S_{n-2}$ 中找到，矛盾。因此 $S_{n-4}< 3|t|$，从而 $S_n=O(|t|)$。

枚举 $S_n$，满足答案是 $S_{n-1}$ 的一个后缀加上 $S_{n-2}$ 的一个前缀，枚举 $|t|$ 中的分割点，则需要计算 $S_{n-2}$ 最短的包含子序列 $t[i:]$ 的前缀，后缀同理。这可以用 DP 在 $O(|t|\log |t|)$ 时间内计算。（上述证明只是为了说明 $n=O(\log |t|)$）。

总时间复杂度 $O(|t|\log |t|)$。

F. Waterfall Matrix

这个问题实际上就是网格图 DAG 上的 $L_1$ 保序回归问题。使用分治，则需要解决总规模 $O(n\log n)$ 的如下问题：

• 给定若干个格子，每个格子权值是 $\pm 1$，找一条左下到右上的折线，使得折线左上方的格子权值和最大。

这个问题可以通过扫描线 + 线段树维护 DP 在 $O(n\log n)$ 时间内解决。

总时间复杂度 $O(n\log ^2n)$。

G. Puzzle II

注意在经过 $(c,d),(c,d+1)$ 的操作后，假设 $S$ 从 $c$ 开始的 $k$ 个字符是 $aX$，$T$ 从 $d$ 开始的 $k+1$ 个字符是 $bYc$，则操作后 $S$ 变为 $Xc$，$T$ 变为 $abY$。整体上讲，我们通过两次操作交换了 $S$ 中的 $a$ 和 $T$ 中的 $c$。因此，只需交换两个串中出现较少的字符，即可在不超过 $n$ 次操作后达成目标。

具体的实现中，不妨设 $S$ 中 $\mathtt{B}$ 的出现次数更少，则我们需要找到 $S$ 中的一个 $\mathtt{B}$ 和 $T$ 中的一个 $\mathtt{C}$ 并通过上述操作交换。由于操作还会对其他位置造成影响，不能暴力模拟。我们可以用两个双端队列分别维护 $S$ 中长为 $k$ 和 $T$ 中长为 $k+1$ 的窗口，并只在窗口中进行交换。交换后，移动窗口来找到下一个可以交换的位置。总的移动次数是 $O(n)$ 的。

时间复杂度 $O(n)$。

H. Weather Forecast

二分答案 $x$，令 $b_i=a_i-x$，则要把 $b_i$ 分成 $k$ 段，每段总和大于 $0$。这等价于求 $b_i$ 的前缀和的 LIS（必须包含 $0$ 和 $n$），可以在 $O(n\log n)$ 时间内求解。

总时间复杂度 $O(n\log n\log \epsilon^{-1})$。

I. Mercenaries

因为询问的条件是 $a\cdot S+b\cdot M\ge c$，显然我们只需要保留 $(S,M)$ 的凸包。考虑二分答案，然后改为求一个区间 $a\cdot S+b\cdot M$ 的最大值。我们考虑预处理出对线段树上的每个区间，只考虑区间中的点和边，走到右端点得到的 $(S,M)$ 的凸包。

设从任意点走到右端点的凸包为 $A$，从左端点走到右端点，只考虑边的凸包为 $B$。则有 $$ A=(A_l+B_r)\cup A_r\\ B=B_l+B_r\\ $$ 其中 $+$ 表示闵可夫斯基和，$\cup $ 表示取并。

分析一下凸包的点数，如果我们认为 $\sum r_i=O(n)$ $B$ 的点数显然是 $O(n)$，$A$ 的点数则是 $O(n\log n)$。因此总共 $\log n$ 层，凸包的总点数为 $O(n\log ^2n)$。

要计算区间中 $a\cdot S+b\cdot M$ 的最大值，我们只需要对线段树上定位到的每个结点的 $A,B$ 都求出这个最大值即可。

查询时先二分，再在线段树上的每个结点凸包二分求出最大值，复杂度 $O(\log ^3 n)$。使用线段树二分以及对询问 $(a,b)$ 按极角排序分别可以优化掉一个 $\log n$。

总时间复杂度 $O(n\log^2 n+q\log n)$。

J. Polygon II

无法构成多边形当且仅当存在一条边的长度大于等于其余所有边长的总和。

枚举这条边 $i$，其边长为 $x_i$，则要计算的是 $x_i\ge \sum_{j\ne i}x_j$ 的概率，令 $x_i\gets 2^{a_i}-x_i$ 可以发现这个概率等于 $\sum_{i}x_i\le 2^{a_i}$ 的概率。

注意到 $U(0,2^a)=U(0,1)+DU(0,1)+DU(0,2)+\cdots+DU(0,2^{a-1})$，其中 $DU(x,y)$ 表示在 $x,y$ 两个数中均匀随机的随机变量。

从低位到高位 DP，令 $f(i,j)$ 表示考虑最低 $i$ 位，当前进位为 $j$ 的概率。为方便起见，我们计算概率乘上 $\prod_i 2^{a_i}$。无法构成多边形的概率就是所有 $f(a_i,0)$ 的和。转移是 $f(i,j)\cdot {C_i \choose k}\to f(i+1,\lfloor (j+k)/2 \rfloor)$，其中 $C_i$ 是 $DU(0,2^i)$ 的个数。

DP 的初始值 $f(0,j)$ 是 $n$ 个 $U(0,1)$ 的和的整数部分是 $j$ 的概率，可以用容斥计算 $n$ 维体积。

时间复杂度 $O(n^2A)$。

K. Power Divisions

可以发现，好的区间个数并不多。事实上它们的总数是 $O(n\log n)$。

可以用分治求出所有好的区间（同时说明好的区间并不多）：

• 对于跨过中点的区间，假设左右的总和分别为 $L,R$，且 $L\ge R$，则一定有 $R=2^{\lfloor\log L\rfloor+1}-L$，即每个 $L$ 至多对应一个 $R$。$L< R$ 的情况同理。

枚举较大的一边后，可以用哈希找到另一边的位置。这里如果直接对总和哈希，错误率不会超过 $O(A/P)$。如果对二进制位做集合哈希，即每一位随机权值，错误率不会超过 $O(1/P)$。

找到所有区间后，简单 DP 即可求出方案数。

总时间复杂度 $O(n\log n)$。

L. Chords

在随机数据下，答案并不会特别大。事实上答案是 $O(\sqrt n)$ 级别（类似 LIS，但并不会证）。

设 $f(k,i)$ 为最小的 $j$ 满足 $[i,j)$ 可以选出 $k$ 条不相交的弦，若不存在则为 $+\infty$。答案即为最大的 $k$ 满足 $f(k,1)<+\infty$。

转移有两种：

• 不选择连接 $i$ 的弦，则 $f(k,i)=f(k,i+1)$。
• 选择了弦 $(i,j)$（$i< j$），令 $c$ 为在 $(i,j)$ 中最多的不相交弦数（可以通过 $f$ 求出），则 $f(k,i)=f(k-c-1,j+1)$。

时间复杂度 $O(n\sqrt n)$。实现时可以直接假设 $k< 900$，然后按照 $i$ 的顺序转移，比递增 $k$ 的方法缓存更友好，快非常多。

M. Balance of Permutation

考虑逐位确定，则需要计算给定前缀、balance 等于 $b$ 的排列个数。将 $p_i=j$ 看作 $i$ 连向 $j$ 的一条边，则 balance 就是对于所有 $i$，跨过了 $(i,i+1)$ 的边数的和。可以设 $f(i,j,b)$ 表示确定了前 $i$ 个点内部的连边，还有 $j$ 对边（向左和向右各 $j$ 条）跨过了 $(i,i+1)$，目前的 balance 是 $b$ 的排列个数。转移时考虑每个点的入边和出边是向后还是向前匹配一条边。确定了的 $p_i=j$ 就删除对应点的出边和入边，但是这时经过 $(i,i+1)$ 的向左和向右的边数不再相等，而是差为定值。

每次 DP 复杂度 $O(n^4)$，总时间复杂度 $O(n^6)$。