Atcoder 试题泛做
难度我自己评了一个分 \(1 \sim 10\) 标黑了的是没有看题解的，蓝了的是瞄了一眼题解的，橙了的是一部分看题解的，红色是基本不会 全部贺题解的。
AGC037C - Numbers on a Circle \(* 3\)
正难则反，考虑倒序操作即 \(b \to a\) 的最小操作次数。
发现 \(a \to b\) 的过程中不能出现非正整数，每次能操作的位置一定满足 \(b_i > b_{i - 1} + b_{i + 1}\)，并且由于左右两边不能操作，我们可以直接将 \(b_i\) 操作到 \(< \max(b_{i - 1}, b_{i + 1})\) 为止，当然不能小于 \(a_i\)
发现在 \(b_i < \max(b_{i - 1}, b_{i + 1}), b_i > a_i\) 之前，\(i - 1, i + 1\) 都不能操作，则 \(b_i\) 仅有这一个操作可选，因此我们先不断进行这个操作直到停下为止都是不劣的。
此时我们发现经过这样一次操作后，要么 \(b_i = a_i\) 以后再也不能操作，要么 \(b_i\) 至少减半，后者可以考虑类似辗转相除法复杂度的证明。
因此我们只需要每次找到一个这样的 \(b_i\) 暴力操作即可，不难发现可以直接取最大值，用堆维护，复杂度 \(\mathcal{O}(n \log n \log b_i)\).
AGC034E - Complete Compress \(* 5\)
枚举最后停在了哪个节点 \(rt\)，以 \(rt\) 为根考虑将所有棋子移到根上的最优解。
首先有一点观察：
- 选择互为祖先关系的两点是不优的。
假设 \(u\) 为 \(v\) 的祖先，\(u, v\) 之间进行了一次操作，由于 \(u\) 也要往根走，那么 \(u\) 被提上去的一步就可以和 \(u, v\) 这次操作调整成一次，这样显然更优。
以下记 \(d_u\) 为子树内棋子到 \(u\) 的距离和，\(c_u\) 为子树内棋子数量，二者可以简单地线性求出。
因此注意到每次操作必然使得 \(d_{rt} - 2\) 因此如果可以将所有点移动到 \(rt\) 上，那么最优答案一定是 \(\frac{d_{rt}}{2}\) 于是只用判定合法性。
观察最后的答案，发现一定是 \(rt\) 的每个子树内部匹配了一些，然后子树之间匹配了一些，子树之间的匹配只关心每个子树的深度和。
由于每次操作使得 \(d_{rt} - 2\)，则每个子树内最后可以保留下来的深度和一定是一个区间，我们只需要求出其最小值。
令 \(f_u\) 为以 \(u\) 为根的子树内部匹配能达到的最小深度和，原问题合法当且仅当 \(f_{rt} = 0\).
于是可以将每个子树 \(v\) 缩成一个点，点权为其自身能达到的一个深度和 \(w_v\)（\(f_{v} + c_v\le w_v \le d_v + c_v\)），给每个点选择一个合适的 \(w\) 使得最后能两两消剩的数最少。
当 \(w\) 确定的时候这是一个经典问题，记 \(mx = \max\limits_{u \to v} w_v, res = \sum\limits_{u \to v} w_v\)，则：
- 若 \(2mx > sum\) 则 \(f_u = mx - (sum - mx)\)
- 否则 \(f_u = sum \bmod 2\)
显然二者都是两种情况分别的下界，可以通过每次选取最大和次大构造得出。
考虑回原问题，记 \(l_i, r_i\) 为每个点可以选取的深度和区间，记 \(l_t = \max\limits_{u \to v} l_v\)，按照 \(l_t\) 和其他区间关系分类讨论：
- 若 \(l_t > \max\limits_{u \to v, v \ne t} r_v\) 则其他所有儿子都选择上界，\(t\) 选择下界最优。
- 否则 \(t\) 选择下界，存在一个儿子和 \(t\) 选的一样，其余都选下界，可以达到 \(f_u = d_u \bmod 2\) 这个下界。
于是直接树形 \(\rm dp\) 即可，复杂度 \(\mathcal{O}(n ^ 2)\)，当然也可以换根 \(\rm dp\) 做到 \(\mathcal{O}(n)\).
AGC036C - GP 2 \(* 4\)
考虑序列 \(x\) 合法的充要条件：
\[\begin{cases} \sum\limits_{i = 1} ^ n x_i = 3m \\ \max\limits_{i = 1} ^ n x_i \le 2m \\ \sum\limits_{i = 1} ^ n (x_i \bmod 2) \le m \end{cases} \]首先上述三个条件的必要性是显然的，考虑充分性。
归纳证明，每次一定可以找到序列当中最大值 \(mx\)，若 \(mx = 2m\) 则找到序列里任意其他一个数 \(x\) 将 \(mx - 2, x - 1\) 即可归纳到一个满足上述充要条件的情况。
若 \(mx = 2m - 1\) 且存在另一个 \(se = 2m - 1\) 那么将 \(mx - 2, se - 1\) 奇数个数减 \(1\)，最大值依然满足要求。
否则若剩下所有数均为偶数，分 \(m\) 是否 \(\ge 3\) 考虑，\(\ge\) 的情况可以任选，\(< 3\) 的情况枚举法不存在非法情况。
否则只要任取一个奇数 \(-1\) 另一个数随意 \(-2\) 即可，若全为偶数显然 \(m \ge 2\).
此时通过观察可以发现，第二条和第三条不合法不会同时出现，于是只用考虑分别减去两个不合法的情况即可。
- \(\max x_i > 2m\)
这样的 \(x_i\) 只有一个，枚举然后插板法即可。
- \(\sum\limits_{i = 1} ^ n (x_i \bmod 2) > m\)
枚举奇数的个数，所有数是偶数情况将所有数 \(/2\) 后插板法。
复杂度 \(\mathcal{O}(n)\).
AGC040C - Neither AB nor BA \(* 4\)
见过类似的套路，然后以为没用，是我 naive 了。
首先这种删除指定串的题目如果不好分析，那么一般要考虑将删除串转化成一个便于观察的形式。
在本题当中，考虑将所有奇数位上的 \(A, B\) 翻转，这样问题转化成每次不能删 AA, BB 并且构成双射。
对于不能删 AA, BB 串合法的充要条件就比较显然了：A 或 B 的数量均不超过 \(\frac{n}{2}\) 即可，这个显然可以容斥计算，复杂度 \(\mathcal{O}(n)\).
AGC033D - Complexity \(* 4\)
首先可以发现题目求的这个东西就是一种类似于 kdt 平面切割的最小深度，因此答案存在上界 \(\log_2 n + \log_1 m\).
暴力显然是令 \(f_{a, b, c, d}\) 为左上角 \((a, b)\) 右下角 \((c, d)\) 的切割最小深度，瓶颈在状态。
由于答案很小，于是考虑状态换值（不知道为什么老是想不到 qwq），注意到往一个子矩形旁加上一行或一列答案一定不减，于是往一个方向一直扩展答案不降。
于是令 \(f_{t, i, j, k}\) 为固定左上角为 \((i, k)\) 左下角为 \((j, k)\) 最小深度不超过 \(t\) 的右边界，只要能 \(\mathcal{O}(1)\) 转移即可通过。
转移有两种，横着切割和竖着切割，竖着切割有转移：
\[f_{t, i, j, k} = f_{t - 1, i, j, f_{t - 1, i, j, k} + 1} \]横着切割有转移：
\[f_{t, i, j, k} = \max\limits_{i \le l < j} \{\min(f_{t - 1, i, l, k}, f_{t - 1, l + 1, j, k})\} \]注意到 \(f_{t - 1, i, l, k}\) 随 \(l\) 递增不降，\(f_{t - 1, l + 1, j, k}\) 随 \(l\) 不深，因此其一定是一个关于 \(l\) 的单谷函数，最优决策点是二者差值最小（注意有两个位置）的位置，因此已经可以做到 \(\mathcal{O}(\log n)\) 转移。
注意到固定 \(i, k\) 随 \(j\) 增大有决策单调性，于是可以直接双指针解决，复杂度 \(\mathcal{O}(n ^ 2m \log n)\).
AGC055B - ABC Supremacy \(* 5\)
之前做的题，就是 AGC040C 那题做法第一步我见过的地方，放在一起总结下好了。
首先还是将指定串转化一下，将每个位置上的字符变为 \(s_i' = (s_i - i) \bmod 3\)，这样问题转化为将连续的三个相同字符转化成三个相同的另一种字符。
发现这样一个性质：XXXR -> RRRR -> RXXX 也就是连续三个相同的字符可以任意在字符串中间穿梭。
由于本题操作可逆，因此只需判定两串是否均能到达一个公共串即可。
由于两个连续块是完全等价的，因此我们可以考虑将两个串内尽可能多地删掉连续块，剩下部分相对位置不能改变因此必须完全相等。
于此同时，发现删除连续块的顺序是不会影响结果的，可以证明交换相邻两个删除的连通块最后得到的结果相同。
因此我们只需要用一个栈来维护当前剩下的字符，每加入一个字符就直接判断栈顶 \(3\) 个元素能不能删，能删则删，最后比较 \(s, t\) 剩下的字符是否完全相等即可，复杂度 \(\mathcal{O}(n)\).
不会写 html 贺个基本颜色语法在这里。
\(* x\)
\(* x\)
\(* x\)
\(* x\)