A \((\texttt{Easy} \ 1 / 1)\)
答案就是每次可以上下左右走，白点到黑点距离最小值的最大值，BFS 即可。
时间复杂度 \(\mathcal{O}(HW)\)。
B \((\texttt{Easy} \ 2 / 1)\)
发现两维独立，可以分开 dp。正着做不好做，倒过来 dp，设 \(l_i, r_i, u_i, d_i\) 表示第 \(i\) 步开始之前需要在这个范围之内才能保证不出去，转移显然。
时间复杂度 \(\mathcal{O}(n)\)。
C \((\texttt{Easy} \ 3 / 1)\)
一次操作等价于把除去选择的点以外的叶子全部删掉，由此不难联想到直径。发现每次可以使得直径长度 \(-1\) 或 \(-2\)，减到 \(0\) 时先手必胜，直接进行一个 dp 即可。
时间复杂度 \(\mathcal{O}(n)\)。
D \((\texttt{Easy} \ 3 / 3)\)
最暴力的 dp 是设 \(f_{a, b, c, d}\) 表示以 \((a, b)\) 和 \((c, d)\) 为边角的矩形的最小操作次数，直接转移是 \(\mathcal{O}(n^5)\) 的，转移具有决策单调性，可以优化至 \(\mathcal{O}(n^4)\)。
发现答案是 \(\mathcal{O}(\log nm)\) 的，我们不妨交换状态和值，改为设 \(f_{k, i, l, r}\) 表示最大的 \(t\)，使得以 \((i, l)\) 和 \((t, r)\) 为边角的矩形的权值为 \(k\)，转移同样可以用决策单调性优化，时间复杂度 \(\mathcal{O}(n^3 \log nm)\)，可以通过。
E \((\texttt{Easy} \ 4 / 2)\)
不妨设 \(s[1] = \texttt{R}\)，则不存在两段相邻的圆弧都为 \(\texttt{B}\)。
想到这个点后就简单了。考虑 \(\texttt{R}\) 对圆弧的限制：
- 圆弧中 \(\texttt{R}\) 的极大连续段长度必须为奇数。
- 设开头有 \(a\) 个 \(\texttt{R}\)，则圆弧中 \(\texttt{R}\) 的极大连续段长度 \(\le a + [2 \mid a]\)。
- 设 \(s\) 中非开头的一段 \(\texttt{R}\) 的极长连续段长度为 \(b\)，若 \(2 \nmid b\) 则圆弧中 \(\texttt{R}\) 的极大连续段长度 \(\le b\)。
于是使用前缀和优化 dp 即可。枚举第 \(1\) 段弧所在的段的长度，把长度为 \(x\) 的段的初值赋为 \(x\) 即可。
注意 \(s[i] = \texttt{R}\) 的情况需要特判，需要额外的 dp 计算。具体地，考虑链的情况，我们有 \(f_0 = f_1 = 1, f_2 = 3, f_n = f_{n - 1} + f_{n - 2}\)；计算答案的时候枚举 \(s[n]\) 是哪个字符，可以得到答案为 \(f_{n - 1} + f_{n - 3}\)。
F \((\texttt{Medium} \ 5 / 3)\)
用类似于 BFS 的方式加边，即加入一条边时考虑用这条边能够加入哪些边，直接做就是 \(\mathcal{O}(n^3)\) 的了。
有一个人认为这样做下去没有前途，于是去考虑各种性质，但是做不出来，点开题解看到 bitset 就会了，我不说是谁。
具体地，在加入边 \((u, v)\) 时，新增的可以加入的边肯定有一个端点是 \(u\) 或 \(v\)，设另一个端点为 \(w\)，则 \(w\) 需满足：
- \((w, u)\) 和 \((w, v)\) 恰好有一个在 \(G\) 中；
- \(w, u, v\) 在树上是一条路径。
我们分别求出两条限制的 bitset，然后与一下即可。第一条限制是好处理的；对于第二条限制，钦定 \(1\) 为根结点，预处理每个点到根的路径上所有结点组成的 bitset 和每个点子树内所有节点组成的 bitset，再根据 \(u, v\) 是否成祖先关系即可 \(\mathcal{O}(\frac{n}{\omega})\) 地求出所有满足条件的 \(w\)。
时间复杂度 \(\mathcal{O}(\frac{n^3}{\omega})\)。
标签：段长度,复杂度,texttt,Easy,mathcal,AGC033,dp From： https://www.cnblogs.com/Scintilla/p/16811647.html