A. Grid Problem
注意到第二种操作，在结合第一种操作之后，等价于将一个位置的值 $\pm 3$。因此在 $\bmod 3$ 意义下，第一种操作等价于将一个 $2\times 2$ 矩阵的一条对角线 $+1$，另一条对角线 $-1$。因此通过操作能得到的矩阵是满足每一行、每一列的总和都是 $3$ 的倍数的所有矩阵。
假设值域范围是 $[0,k)$，如果 $k$ 是 $3$ 的倍数，那么答案显然是 $k^{hw}3^{-(h+w-1)}$。如果 $k$ 不是 $3$ 的倍数，直接暴力 DP 只能做到 $O(\mathrm{poly}(h,w))$ 的复杂度。
考虑一个 $h+w$ 元多项式 $$ \prod_{i=1}^h\prod_{j=1}^w\sum_{v=0}^{k-1}(x_iy_j)^v $$ 则我们想要的是每个元的次数都是 $3$ 倍数的项的系数之和。
利用单位根反演，我们知道这相当于将每个 $x_i,y_i$ 分别带入 $1,\omega,\omega^w$（$\omega$ 是三次本原单位根）的 $3^{h+w}$ 个式子的平均值。
由于每个位置都是本质相同的，我们可以枚举 $r_0,r_1,r_2$ 分别表示有多少个 $x_i$ 带入了 $1,\omega,\omega^2$，则每一列的贡献就是独立的，因此答案可以表示成 $$ \frac{1}{3^{h+w}}\sum_{r_0+r_1+r_2=h}{h\choose r_1,r_1,r_2}\left(\sum_{i=0}^2f(0,i)^{r_0}f(1,i)^{r_1}f(2,i)^{r_2}\right)^w $$ 其中 $f(i,j)=\sum_{v=0}^{k-1}\omega^{(i+j)v}$。
时间复杂度 $O(h^2\log w+\log k)$。
B. Domain Compression
注意到删掉一个点 $v$ 相当于让通过 $v$ 间接连通的点直接相连。因此最终的图当中存在边 $(u,v)$ 当且仅当 $u,v$ 都没有被删，且存在一条 $u$ 到 $v$ 路径上的点（不包括 $u,v$）都被删掉了。
而因为原图是一棵树，因此只需要计算一下点对距离的分布，即 $f_i$ 表示距离为 $i$ 的点对数量，则答案为 $$ \mathrm{ans}_k=\sum_{i=1}^{n-1}f_i\cdot {n-i-1\choose k-i+1}\cdot k! $$ 最后一次卷积即可。
根据计算点对距离分布的复杂度，总复杂度为 $O(n\log n)$ 或 $O(n\log^2n)$。
C. Staple Stable
如果切完之后每一块最大的高度和宽度分别是 $x$ 和 $y$，则要求 $xy\le s$，需要切的刀数是 $\left\lfloor \frac{h-1}{x}\right\rfloor+\left\lfloor\frac{w-1}{y}\right\rfloor$。
对 $s$ 整除分块，或者枚举 $x,y$ 中的较小值都可以。时间复杂度 $O(\sqrt s)$。
D. Sequence Is Not Subsequence
假设 $s_{n}$ 在答案 $t$ 中的最后一次出现位置是 $t_i$，那么 $t[1:i-1]$ 一定包含了 $s[1:n-1]$ 除本身以外的所有子序列，且不包含 $s[1:n-1]$ 作为子序列。并且如果 $s_{n-1}\ne s_n$，需要在 $t_i$ 之后还有一个 $s_{n-1}$ 才能保证 $s[1:n-1]$ 出现。这样就将问题递归到了 $s[1:n-1]$ 上，重复这个过程直到 $|s|=1$，那么答案就是空串。
根据这个递归过程反过来构造即可，时间复杂度 $O(n)$。注意到这个过程实际上证明了长度最短的 $t$ 是唯一的。
E. Coffee Shops
首先分析一下上界。对于每个 $2\times 2$ 的小矩形，其中的最大值一定不是 sad 的。因此答案不可能超过 $2n-\left\lceil \frac{n}{2}\right\rceil$。
对于奇数 $n$ 来说，上界是可以达到的。只需要将最大的 $\left\lceil\frac{n}{2}\right\rceil$ 个数放在 $a_1,a_3,\ldots,a_n$ 的位置。这样对于 $b_{2k}$ 的位置就自动满足了，所以这些位置用来放接下来最大的一些数。然后容易发现将剩下的数有序放在剩下的空位即可满足条件。
对于偶数来说，上述构造方式只能做到 $\frac{3}{2}n-1$，这时因为最后的空位中放的最大的数是不满足 sad 的条件的。事实上这也就是偶数时真正的上界。如果想要达到 $\frac{3}{2}n$，那么一定是每个 $2\times 2$ 矩形中恰好有一个不 sad。也就是说，这些位置所在的列一定是所有的奇数列或偶数列，行则可以是任意的。确定这些位置后，考虑从大到小填数，首先可以把形如 $a_{2k}$ 和 $a_{2k+2}$ 已经填了的情况对应的 $b_{2k+1}$ 填上。之后发现就没有任何可以填的位置了，所以不可能有解。对照 $n$ 是奇数的情况，我们会发现因为 $a_1$ 和 $a_n$ 是相邻的，所以可以从 $b_1$ 或者 $b_n$ 开始填。
F. Yet Another MST Problem
因为是求最小生成树，所以我们可以将 mex 改写成任意未出现过的非负整数。按照边权从小到大考虑，则每次是将不包含 $x$ 的所有区间合并。维护每个连通块中区间的最小右端点和最大左端点，即可快速找到需要合并的区间。
时间复杂度 $O(n\log n)$。
G. Cyclic Topsort
问题可以转化为，删除原图当中的一个点（对应序列中的第一个点），从前向后拓扑排序，最多能排多少个点。
先把原图中能排的点排完，剩下每个点的入度都大于 $0$。
可以注意到，如果删除 $x,y$ 后可以排序的点有交，则意味着 $x,y$ 一定有一个点删掉之后能间接排到另一个，从而可以排序的点集呈包含关系。不然的话，考虑这删掉 $x,y$ 后拓扑序最靠前的一个公共点，则这个点一定有只能被 $x$ 和只能被 $y$ 删除的入边，矛盾。
因此删掉每个点能排序的点集之间要么不相交，要么包含，形成一个树形结构。接下来有几种做法：
- 可以直接 shuffle 之后，暴力检验每一个点，跳过被之前的点间接访问过的点，因为这些点一定不是最大值。这样每个点期望只会被访问 $O(\log\mathrm{dep})$ 次，其中 $\mathrm{dep}$ 是其在树形结构上的深度。
- 也可以维护一些集合，满足每个集合都存在一个点能到其余所有点。如果一个集合 $S_1$ 无环且所有入边都在集合 $S_2$ 中，则将这两个集合合并。可以用启发式合并实现。
时间复杂度 $O((n+m)\log n)$。
H. Misread Problem
显然有 $\mathrm{cost}(b,a)=\frac12\sum_{i=1}^n |a_i-b_i|$，所以每一个 $b_i$ 的贡献是独立的凸函数 $f_i(x)$。
我们希望找到一组 $b_i$ 满足 $\sum_{i=1}^n b_i=m$ 且 $\sum_{i=1}^n f_i(b_i)$ 最小，只需要按照 $f_i(x)$ 的斜率贪心即可。
时间复杂度 $O(nk\log k)$。
I. troS XEM
最后的序列的每个数都是由原序列的一个区间操作得来的。我们可以猜想，当一个序列长度大于一定值（且是奇数），则能够通过操作得到 $[0,3]$ 中的每种数。事实上这个阈值是 $K=17$。
有了上述结论之后，我们就可以 DP 了。设 $f_{i,j}$ 表示让前 $i$ 个数递增，结尾是 $j$，最少的操作次数。转移时只需要枚举结尾的区间，这个区间长度只需要枚举到 $K$ 即可。转移需要一个辅助数组 $g_{l,r,x}$，表示 $[l,r]$ 能否得到 $x$，其中 $r-l\le K$。由于这个辅助数组的转移需要枚举两个分界点，所以复杂度达到了 $O(nK^3)$。我们再用一个辅助数组表示一个长度为偶数的区间分成两段，能得到哪些数的 pair，可以将复杂度优化到 $O(nK^2)$，但是有巨大的常数。为了优化复杂度，我们把辅助数组的值压位用二进制数表示，然后预处理合并的结果，就能去掉这个巨大的常数。
最后还要注意序列末尾有一段不操作的情况。
时间复杂度 $O(nK^2)$。
J. Yet Another Constructive Problem
假设我们求出所有长度为 $m$ 的子序列的 LIS 最小和最大值，则在最小值和最大值之间每个值都可以取到。这是因为我们可以从 LIS 最小的子序列变到 LIS 最大的子序列，每次替换一个数，则这个变化过程中 LIS 每次至多变化 $\pm 1$，因此所有中间值都可以取到。
上述变化过程可以通过二分优化，时间复杂度 $O(n\log^2n)$。
求 LIS 最大值是简单的，只需尽量选原序列的 LIS，然后不够的用其他数补充。
求 LIS 最小值，可以转化成选尽量少的不相交的下降子序列，其长度和等于 $m$。众所周知，选 $k$ 个子序列的答案等于杨表的前 $k$ 行长度之和，但是杨表的前 $k$ 行并不就是我们想要的子序列。这里构造方式需要参照上述结论的证明，即 RSK 算法。杨表的构造过程相当于对排列进行若干次相邻项的交换，保证每次交换都不改变答案，而最终的排列，即杨表的答案是平凡的。因此只需要反向模拟这一交换过程即可还原出所需的子序列。例如，对于连续的三个数 $a,b,c$，如果 $c< a< b$，则可以交换 $b,c$ 而不改变答案。构造方式是：如果 $b,c$ 属于同一个子序列，则把 $c$ 及其所在子序列后面的部分和 $a$ 所在子序列后面的部分交换。
上述交换过程的复杂度是 $O(n^2)$，因此总复杂度是 $O(n^2)$。
K. Robot Construction
假设原来的高度范围是 $[0,d]$，那么经过高度 $a_i$ 的障碍后，高度的范围仍然形如 $[0,x]$，当 $a_i>d$ 时 $x=d$，当 $a_i\le d$ 时 $x=\max\{a_i-1,d-a_i\}$。注意这里 $x$ 关于 $d$ 是单调的，且因为初始 $d$ 都相同，所以在对右端点扫描线的过程当中，当前的 $d$ 关于左端点一定是单调的，可以直接用线段树维护。时间复杂度 $O((n+q)\log n)$。
