A. Albiduria [Div.2 Only]
直接 BFS 即可。
B. Blastula [Div.2 Only]
答案即为卡特兰数 $C_n$.
C. Caucasoid
假设串长为 $m$，每一段极长相同字符长度为 $x_i$，那么我们记 $f(m)=m^2- \sum x_i^2 =2n$。
$x_i=1$ 时 $f(m)$ 取到最小值 $m(m-1)$。我们找到最小的 $m$ 使得 $m(m-1)\geq 2n$，考虑构造一个长度为 $m$ 的串。
将 $m(m-1)/2$ 视为 $f(m)/2$ 的初始值，那么对于一个 $x_i=k$，它会使 $f(m)/2$ 减小 $k(k-1)/2$。而我们总共需要减小 $m(m-1)/2-n$。由于 $(m-1)(m-2)/2 < n$，那么这个值最多为 $m-2$。
接下来我们直接贪心，每次取一个尽量大的 $k$。
由于 $k=3$ 时 $k\leq k(k-1)/2$，$k=2$ 时 $k(k-1)/2=1$，并且 $k=2$ 最多出现 $2$ 次，因此 $\sum x_i \leq m$。
时间复杂度 $O(t\sqrt n)$
D. Dialysate
结论: 存在一种最优方案使得每次操作的区域是上一次的子集且颜色与上一次相反.
考虑归纳证明, 记 $S$ 为当前所有操作区域的并, $T$ 为接下来一步的操作区域, 我们有:
$T$ 与 $S$ 有交的情况一定可以转化成 $T$ 被 $S$ 包含的情况.
$T$ 与 $S$ 交集为空时, 可以找一个连接 $S$ 和 $T$ 的集合 $M$ 并操作 $S \cup T \cup M$,并将之前的所有操作连接到更外的层以及外层的连接部分同时操作, 特殊处理最外层和第二层的情况.
$T$ 被 $S$ 包含时, $T$ 落在某个完整区域内时等价于情况二, 否则一定连接若干个同色块, 这些块可以同时处理, 步数一定不会更劣.
知道这个结论就比较好做了, 我们可以枚举最后被修改的区域, 这时答案就是将同色边边权当作 $0$, 异色边边权当作 $1$ 后距离这个点最远的黑色点的距离, 对所有点取最小值即可.
E. Exilarch
问题相当于统计每个 $(p, S)$（$1 ≤ p ≤ p + |S| − 1 ≤ m$），在多少个 $(x, y)$（$1 ≤ x ≤ y ≤ n$）中使得：$∃z ∈ [x, y], \{A_{z,p}, A_{z,p+1}, \cdots, A_{z,p+|S|−1}\} = S$，然后求和。
先考虑 $p = 1$ 时的情况，将矩阵建出一棵 trie，每个结点用 set 保存对应 $S$ 出现的行集合。
每次将 $p$ 加 1，只需将根的所有孩子合并，作为新根。两个行集合合并时直接把小的加入大的。$O(nm \log^2 n)$。
F. Feuillant [Div.1 Only]
不会做
G. Glycoside [Div.1 Only]
不会做
