A
一个 \(R\times C\) 的矩阵 \(A\)，有 \(N\) 个位置已知，第 \(i\) 个为 \(A_{r_i, c_i} = a_i\)。求是否存在一种填写剩下数字的方案，满足每个数字都非负且对于任意 \(i, j (1\le i\le R - 1, 1\le j\le C - 1)\) 都有 \(A_{i, j} + A_{i + 1, j + 1} = A_{i, j + 1} + A_{i + 1, j}\)，不需要构造方案。
\(2\le R, C\le 10^5, \ 1\le N\le 10^5\)
考虑化为 \(A_{i, j + 1} - A_{i, j} = A_{i + 1, j + 1} - A_{i + 1, j}\)，即每行的差分数组都相同，进而表示成 \(A_{i, j} = x_i + y_j\)。
令 \(y'_j = -y_j\)，那么 \(A_{r, c} = a\) 的条件可以表示为 \(x_r - y'_c = a\)，可以用带权并查集维护。
每个位置上的数非负相当于 \(\min x_i \ge \max y'_j\)，相当于对于并查集每个集合中，每个行权都不小于每个列权，这是容易的。
B
有 \(n\) 个位置，每个位置可能有狗或骨头，或者为空。你可以给每条狗指定向左或向右的行走方向，且所有狗的行走速度相同。求最多有多少个骨头至少被一条狗经过，以及达成目标的最小步数。
\(1\le n\le 10^6\)
一条狗特判，两条或以上的狗一定可以经过所有骨头。
考虑二分步数，相当于给每条狗定向并覆盖一段位置。考虑 dp，设 \(f_i\) 表示前 \(i\) 条狗能覆盖最多能覆盖第 \(1\sim f_i\) 个骨头，转移：
-
第 \(i\) 条狗向右。
-
第 \(i\) 条狗向左。
-
第 \(i\) 条狗向左，第 \(i - 1\) 条狗向右。
-
启示：根据不同情况设计不同 DP，莫思维定式。
C
给出 \(n\) 个长度为 \(m\) 的由小写字母组成的字符串 \(s_{1\dots n}\)，构造任意一个字符串 \(ans\) 满足 \(\forall i \in[1, n] , \ \sum\limits_{j = 1} ^ m [ans_j \not = s_{i, j}]\le d\)，或者报告无解。
\(1\le n\le 1000, \ 1\le m\le 2\times 10^4, \ 0\le d\le 6\)
先令 \(ans = s_1\)，在此基础上至多修改 \(d\) 个字符得到最终答案。
考虑爆搜修改 \(ans\)，设当前已经修改了 \(x(0\le x\le d - 1)\) 个字符，设 \(s_i\) 与 \(ans\) 有 \(dif_i\) 个位置上的字符不同，如果 \(dif_i + x > 2d\) 则后续无论如何修改都不合法，可以直接 return。
否则找到任意一个满足 \(d < dif_i\le 2d - x\) 的字符串 \(s_i\)，提取出其所有与 \(ans\) 字符不同的位置，并枚举当前修改的是其中哪个位置上的字符。
理论时间复杂度为 \(\mathcal O(n \cdot (d + 1) \cdot (d + 2) \cdots (2d))\)，但每次可以选择 \(dif_i\) 最小的字符串，远远跑不满。
- 启示：调整法爆搜。
D
一张 \(n\) 个点和 \(m\) 条边的图，满足一条从 任意一个编号比其连向的点都大的点 到 任意一个编号比其连向的点都小的点 的路径长度都被 \(k\) 整除，构造将 \(n\) 个点划分为 \(k\) 个独立集的方案。
\(1\le n, m, k\le 10^6\)
编号小的点连向大的点，这张图就是一张 DAG。从特殊条件出发，考虑从任意一个起点到点 \(u\) 的路径长度 \(\bmod k\) 一定覆盖不了 \(0\sim k - 1\) 所有余数，我们可以令 \(u\) 的颜色 \(d_u\) 为某一个起点到 \(u\) 的路径长度 \(\bmod k\)，这样一定合法。
具体的，用桶存下所有从 \(v\) 连到 \(u\) 的 \(d_v\)，然后找到任意一个 \(d_v\) 满足 \(d_v + 1\) 没有存到桶中，令 \(d_u \gets d_v + 1\)。
- 启示：特殊条件入手；令构造方案契合特殊条件，从而为构造创造条件。