从 2022-08-25 开始更新。
这篇是总和，包含了 2022 年暑假开始时做的一些比较容易的题，最近的 AGC 部分也在后面，如果只想看相对困难的题，可以移步到 New AT 板刷（已经置顶）。
$\mathbb{ARC \ 146 \ C}$
观察
一眼递推，问题在于 $\Theta(2^n)$ 的复杂度显然不对。
考虑怎么从上一层转移，可以从现在新增的元素里选出一些往上一层合法的集合中加，如果在添加后不合法则情况是上一层的集合存在一个大小为奇数的子集异或值和当前选出的元素相等，继续想，这个子集只可能有一个，因为如果存在两个，则上一层的该集合不合法，即会存在一个大小为偶数且异或和为 $0$ 的子集。
其实还可以发现一个性质，即是说因为上一层的集合每一个大小为奇数的集合都对应着一个唯一一个不能加进去的元素，那么每一新元素都有 $2^i - 2^{i - 1}$ 种选法。
具体推一下，定义 $dp_i$ 为第 $i$ 层的答案，那么可以拿到 $dp_{i - 1}$ 。
得到的转移方程为
边界是 $dp_1 = 1$ 。
回到最开始的问题，复杂度不对，其实打表可以看到在 $i \ge n + 2$ 时，答案不会再次变化。
$\mathbb{ABC \ 256 \ F}$
/kk 因为这道题没看到弱智题 G
可以考虑一个最蠢的 $dp_{t,i,j}$ 表示，前确定了 $t$ 个维度后，距离 $p$ 为 $i$ ，距离 $q$ 为 $j$ 的多维体的总数，可以写出一个 $\Theta(nD^3)$ 的转移方程。
然后比赛时就卡在这里了，，，
如果把代码写出来，估计优化就容易了。
1 | for (int t = 1; t <= n; t++) { |
然后要搞一个奇妙的转化，定义 $s_i = \mid p_i - q_i \mid$ ，把合法的 $(dis1,dis2)$ 分成三类。如下
$(s, 0), (s - 1, 1), (s - 2, 2), (s - 3, 3) \dots (0, s)$ $(s + 1, 1), (s + 2, 2), (s + 3, 3) \dots$ $(1, s + 1), (2, s + 2), (3, s + 3) \dots$那么这个就可以做了，因为这些合法的点均在一条直线上，最终可以优化到 $\Theta(nd^2)$。
$\mathbb{ABC \ 264 \ G}$
居然不会写了😓
对于一个字符串，把转移看成在最后添加一个字符，则贡献只和最后两个字符有关，则可以直接建图跑最长路，顺带 $spfa$ 判环即可。
$\mathbb{ABC \ 232 \ F}$
状压 + 逆序对
不难想到，两个操作可以分开考虑，可以视为首先把 $\{A\}$ 变成 $\{A'\}$ ，其中 $\{A'\}$ 的数字可重集合和 $\{B\}$ 等价。
看到数据范围很小，可以考虑状压，定义 $dp_{sta}$ 表示把 $sta$ 上为 $1$ 的位数上的 $A$ 数字放到 $B$ 的前 $cnt(sta)$ 位上的最小代价。
怎么转移呢，考虑向后填表，对于一个已知的状态 $dp_{sta}$ ，要做的事是将 $a_{j}$ 放到 $b_{cnt(sta) + 1}$ 上，统计 $sta$ 中在 $j$ 之后的 $1$ 的个数为 $tot$，那么转移就是 $dp_{sta \otimes {2^j}} = dp_{sta} + tot \times y + \mid a_j - b_{cnt(sta) + 1} \mid \times x$ 。
$\mathbb{ABC \ 236 \ F}$
线性基
和 $Kruskal$ 很相似。直接构造一个线性基，按代价从小到大依次往里面加。
$\mathbb{ABC \ 237 \ F}$
暴力 $dp$
定义 $dp_{i, a, b, c}$ 为考虑到 $ith$ 位，当前的 $\mathrm{LIS}$ 序列为 $\{a, b, c\}$ 。
转移时，考虑枚举下一位填入 $j$ 并分类讨论，转移与 $\mathrm{LIS}$ 相似。
$\mathbb{ABC \ 239 \ F}$
又一道构造
正向思考长时间无果，考虑什么样的连边会让整个图断掉，即是，存在两个连通块，都剩余 $1$ 的度，结果这个两个块连在了一起，遂与外人间隔。
得到的提示是尽量把度数小的往大的上面连，但是还是有问题，比如 $\{3, 2, 1, 1, 1\}$ ，会先将 $3$ 个 $1$ 往 $3$ 上连，结果是 $2$ 连不上去。考虑一个合并法，度数小的往次小的连，那么维护一个堆就可以解决。
$\mathbb{ABC \ 244 \ F}$
状压
定义 $dp_{sta, u}$ 表示最后停在 $u$ ，状态集合为 $sta$ 的最短路。
转移则是枚举 $u$ 的出边，得到 $v$ ，下一次的状态则是 $dp_{sta \otimes 2^v, v}$ 。发现这个转移是在 $DAG$ 上进行的，那么直接建图跑 $spfa$ 就行了。
$\mathbb{ABC \ 246 \ F}$
状压 + 容斥
怎么这么多状压题。。。
开始想了很久，因为没有看到所有字符串是 abcdefghijklmnopqrstuvwxyz 的子序列。
那么直接考虑整个字符串是由哪几个拼起来的，现在的问题就变成了对于给定的一堆字符串拼成一个长度为 $l$ 的有多少种方案。
额，发现不对。。。先放了。
$\mathbb{ABC \ 247 \ F}$
并查集 + dp
这和原来做的 $cf$ 上的一道题很想，也是关于构造二分图的方案数。
很容易想到二分图，那么每个连通块的方案数乘起来就是总方案数。
考虑怎么求每个连通块的总方案数，问题现在是对于一个二分图，要选择一些边使得每个点都有覆盖，定义 $dp_{i}$ 表示第 $i$ 条边选不选的方案数，则 $dp_{i} = dp_{i - 1} + dp_{i - 2}$ ，边界条件可以手玩得出。
$\mathbb{ABC \ 249 \ F}$
细节
思路很好想，可以发现操作 $1$ 是具有一键抹销功能的，只有最后一个操作 $1$ 和之后的操作 $2$ 构成的操作有影响。
考虑钦定最后一个操作 $1$ ，那么用一个堆维护之后的操作就可以了。
$\mathbb{ABC \ 251 \ F}$
点破
乍一看很高级，是个构造，其实点破之后很简单，操作 $1$ 要求祖先和子孙之间有虚边，操作 $2$ 要求，兄弟间有虚边，那么用 $dfs$ 和 $bfs$ 分别求一次生成树就可以了。
$\mathbb{ABC \ 252 \ F}$
贪心典
合并果子逆向版。
$\mathbb{ABC \ 266 \ F}$
简单期望
定义 $dp_{i}$ 为走到第 $i$ 步的最大期望，转移很简单， $dp_{i} = \sum_{j = 1}^{6}\frac{\max\{j, dp_{i - 1}\}}{6}$ 。
$\mathbb{ABC \ 223 \ E}$
想了好久。。。🤡
其实很简单，但我一开始以为是个贪心，构造了很久都没弄出来。
首先考虑两个矩形的情况怎么做，设面积分别为 $S_1, S_2$，问题转化为在大的平面上划一条线，分成两个部分，能分别放下两个矩形。
如果该直线与 $x$ 轴平行，则 $l = \lceil \frac{S_1}{x} \rceil$ ，换成 $y$ 轴也同理。之后再将其中一个矩形继续划分就可以判定了。
$\mathbb{ABC \ 233 \ F}$
码码码
应该算个原题，一眼线段树，在每个节点上维护当前节点上失配的 左 / 右 括号数，合并就用右儿子的右括号去补全左儿子的左括号，交换操作可以看成单点修改。
$\mathbb{ABC \ 233 \ G}$
marked
题面很漂亮，给定一棵树，问有多少个节点满足：删去这个节点后的图的匹配数等于原树的匹配数。
首先重新想一下图匹配的定义：即是在一张图中，两两没有公共点的边集数。一个结论是匹配数等于点数减去最大独立集。
最大独立集是可以直接树形 dp 不带任何技巧地求出来的，那么考虑删点怎么处理。
首先从已知的数据出发，现在已经得到的是 $u$ 的子树内的最大独立集的大小，这一部分数据还要和 $u$ 的子树外的数据合并。
首先定义出来 $f_{u, 0/1}$ 表是当前点选不选的子树内的最大独立集大小， $g_{u, 0/1}$ 表示在不考虑当前点的子树情况下当前点的父亲选不选的最大独立集大小。
那么简单的换根 dp 就可以解决了。首先记 $sum_1 = \sum_{v \in fa} \max \{ f_{v, 0}, f_{v, 1} \}, sum_2 = \sum_{v \in fa} f_{v,0}$ ，最后的转移方程为
$\mathbb{ABC \ 222 \ E}$
转化
需要一个转化，首先统计每条边出现的次数，记为 $cnt_i$ , 记 $S = \sum_{i = 1}^n cnt_i$ 然后可以类似于一个解方程转化，已知了 $R + B = S, R - B = k$ ，则 $R = \frac{S + k}{2}$ ，这个是一个定值，那么问题就转化为选或不选一些边，使总数和为 $\frac{S + k}{2}$ 。这个就可以简单地用背包 $dp$ 解决。
结果写挂了一发，想了半天没看出错，遂改了一个写法，莫名其妙就过了。
$\mathbb{ABC \ 222 \ F}$
结论
首先观察发现，其实可以建 $n$ 个虚点，建边为 $(i, i + n, d_i)$ ，这样就把额外的点权转化成了只需要考虑边权。
问题就变成了求树上任意一点的最远的点，一个远古结论是这个最远点一定为树的两个端点之一。那么两遍 $dfs$ 就可以解决。
坑点在于题目自身还有一个限制 $\max_{1 \le j \le N, j \not = i} E_{i, j}$ ，也就是说不能连向自己对应的虚点，特判即可。
$\mathbb{ABC \ 217 \ F}$
一个典型的区间 dp
但是我把题读错了。。。想了 $15min^+$ 才感觉不对。
合并的时候注意组合数系数。
$\mathbb{ABC \ 267 \ G}$
第一步就想错了。。。
想不到就是想不到，第一步应该排序。
排序之后考虑不是生成排列，而是一个一个把数插进去，则可以写出式子 $dp[i + 1][j + 1] = dp[i + 1][j + 1] + dp[i][j] * (i - cnt - j) \\ dp[i + 1][j] = dp[i + 1][j] + dp[i][j] * (cnt + j + 1)$ ，其中 $cnt$ 表示当前已经和 $a_i$ 相等的数的个数。
$\mathbb{ABC \ 268 \ F}$
5 min
感觉很能贪心，记 $val_i$ 为第 $i$ 个字符串中所有数字的和， $num_i$ 为第 $i$ 个字符串中的 $X$ 的个数，那么只要 $num_x \times val_y > num_y \times val_x$ 就认定为 $x$ 放在 $y$ 前面会更优。
$\mathbb{AGC \ 058 \ B}$
支配 😍
首先可以想到对于一个 $p_i$ 他能够支配的区域是 $[l, r]$ 使得 $p_j \le p_i, j \in [l, r]$ ，那么很简单的 $dp$ 方程可以写成 $dp_{j} = (dp_{j} + dp_{j - 1})$
$\mathbb{ABC \ 273 \ F}$
又不会区间 dp 了
定义 $dp_{l, r, 0/1}$ 表示走完了 $[l, r]$ 现在处于 $l/r$ 中一个端点，注意其中的 $l, r$ 是离散化后的点，并且表示下标。
一开始觉得要分类讨论，其实不然。
可以把捡锤子，和砸墙看成一种操作。
得到 $dp_{l, r, 0} = \min\{dp_{l + 1, r, 1} + pos_r - pos_l, dp_{l + 1, r, 0} + pos_{l + 1} - pos_{l} \}$
$\mathbb{ABC \ 273 \ G}$
又是一个一个数矩阵问题啊啊
无解直接判行列是否相等就行了。
以为是个组合数学，但思考无果，选择直接 $dp$ 。
定义 $dp_{i, j, k}$ 表示计算到第 $i$ 行，在 $j, k$ 个列上放了 $1, 2$ 的方案数，考虑转移。
$\mathbb{ABC \ 274 \ F}$
直接模拟
有个东西叫做相对位移，所以枚举每条鱼，以它为原点，固定不动，可以轻松地知道每条鱼在 $[0, a]$ 的时间段，那么线段树搞搞就行了，复杂度 $\Theta(n^2 \log n)$ 很可以过。
$\mathbb{ABC \ 274 \ G}$
烂 trick
行列连边二分图的烂 trick ，只不过多了障碍物，对于一段横竖没被阻断的看成一块，重新编号后行列连边就行。跑二分图过不了，网络流就行。
$\mathbb{ABC \ 275 \ F}$
$dp$ 直接上，定义 $dp_{i, j}$ 表示考虑到了第 $i$ 个数，现在总和为 $j$ 的最小代价。 当不删 $i$ 时，$dp_{i, j} = dp_{i - 1, j - a_i}$ 。如果要删 $i$ ，则需要枚举一个左端点 $k$ ，$dp_{i, j} = \min \{ dp_{k,j} \} + 1$ 。 可以做到 $\Theta(nm)$ 直接过。 ### $\mathbb{ABC \ 276 \ G}$BOT CJG 永远不会把顺序无影响的操作问题看成一个可以从左往右直接 dp 的 easy task
开始数数哦，原来给序列做差分可以把每个数的值域变成序列和的值域
看到求合法单调序列个数，想到转化成求其差分序列个数，这是等价的。
定义 $B$ 为 $A$ 的差分序列，则 $\sum b_{i} = M, \forall b_{i}, i \ge 2, b_{i} \mod 3 \equiv 1 / 2$ 。
一个处理同余的手法是把式子写成带余除式，即 $b_i = 3y_i + x_i$，发现对于每个 $b_i$ 均是独立的，等价地得到 $x_i, y_i$ 也是独立的，那么在和的限制下计数就可以了。
$\sum 3y_i + x_i = M$， 移项，改写成 $x, y$ 的互相的限制，即 $\sum y_i \le \lfloor \frac{M - \sum x_i}{3} \rfloor$ 。
这个时候分开计算 $x, y$ 。
$\sum y = N$ 的方案数为 $\binom{N + y - 1}{n - 1}$ 。
对于 $x$ 因为取值固定，枚举个数计算贡献就可以了，注意要把 $x_1$ 单独拎出来。
$\mathbb{ABC \ 279 \ F}$
并查集水题，略。
$\mathbb{ABC \ 279 \ G}$
直接做？
定义一个线性表示答案的 $dp_{i, 1/2}$ ，$dp_{i, 1} = dp_{i - k + 1, 1}, dp_{i, 2} = dp_{i - k + 1, 1} \times C + dp_{i-k+1,2}\times 2$
$\mathbb{ABC \ 280 \ F}$
性质发现
由于这张图的特殊构造，可以尝试发现性质，如果一个连通块中有正环，则答案为 inf ，否则两点间路径唯一，那么钦定一个节点遍历整个连通块，处理距离，两点距离的差即为答案。
$\mathbb{ABC \ 280 \ G}$
如何优化？
两个点之间距离的计算比较复杂，但是发现距离具有平移不变的性质，于是考虑通过每个点与 $(0,0)$ 之间的距离来刻画两点间的距离。
具体过程可以手玩得到，记 $d_1 = x_1 - y_1, d_2 = y_1 - y_2$两点间的距离为 $\max\{\mid d_1 \mid, \mid d_2 \mid, \mid d_1 - d_2 \mid\}$ 。
发现这个东西是三维的，于是可以用一个 $d^3$ 的正方体刻画，那么每次框起来的就是一个可行的点集，考虑去重。
于是开始枚举每一个维度上的最小值，记为 $x_0, y_0, z_0$ ，钦定这些点必须选，如果这些点围起来的点数为 $tot$ ，则总的答案增加 $2^{tot}$ ，直接做是 $\Theta(n^4)$ 的，在统计围起来的点数是可以用双指针优化，最后的复杂度是 $\Theta(n^3)$ 。
$\mathbb{ABC \ 281 \ F}$
经典
比较经典了，首先可以把字典树建出来，然后在字典树上做树形 $dp$ ，具体来说，定义 $dp_u$ 为使用 $u$ 子树内的点构成的数列来计算得到的答案，当只有一个子节点时，可以直接继承，否则选择小的一个加上 $2^i$ 往上算。
$\mathbb{ABC \ 281 \ G}$
Spanning Tree?
图的计数问题要注意一些定理的使用和从生成树的角度思考，看到题目中有对于距离的限制，考虑把每一层分开，使得 $1$ 在最深的一层，那么此时计数就简单了，定义 $dp_{i, j}$ 表示用了前 $i$ 个点，后面的 $j$ 个点分在一层时的方案数，主要到并没有考虑现在是第几层，因为计数的原则只要是问题答案等价且转移后的状态合法就可以了，那么转移就变成了当前层自身连边和向上一层连边，方程是
$$ dp_{i, j} = \sum_{k = 1}^{i - j} dp_{i - j, k} \times \binom{n - 1 - i + j}{j} \times (2^{k} - 1)^j \times 2^{j\times(j - 1)} $$$\mathbb{ABC \ 277 \ G}$
直接去掉
考虑一个最简单的 $dp_{u, j, l}$ 表示走到 $u$ ，步数为 $j$ ，此时等级为 $l$ 的概率，转移是 $dp_{v, j + 1, l + c_v} = dp_{v, j + 1, l + c_v} + dp_{u, j, l} \times \frac{1}{deg_u}$ 。
复杂度是 $\Theta(n^3)$ 的，考虑降维，从这三维对答案的贡献来看，最终统计时，一个点的贡献是 $\sum_{l = 0}^{k} dp_{u, j, l} \times l^2$ ，变量是 $l$ ，即是最后一维，因为 $i, j$ 是特征量，不能去，那么只能把 $l$ 优化掉。在转移过程中 $l$ 的变化只有 $+1$ 的操作，做完之后一个点的贡献变为 $\frac{1}{deg_u} \times \sum_{l = 0}^{k} (l+1)^2$ ，因为系数是统一的，那么直接维护二次的增量就可以了。
$\mathbb{ABC \ 272 \ G}$
就随机
考虑从集合里面抽出来两个元素，则他们两个差有一定概率是这个 $M$ ，这取决于这两个数是不是在这个模意义下相同的集合，很明显，如果 $M$ 满足条件，则 $M$ 的因数也满足，那么就用这个差值和这两个数去掉余数之后的值做差就可以了。
如果全部枚举则检验复杂度是 $\Theta(n^3)$ 的，因为这个东西性质很强，我们每次抽取两个元素，都在满足要求的集合里面的概率最小是 $\frac{1}{4}$ ，那么多随几次就行了。
$\mathbb{ABC \ 271 \ G}$
矩阵 /se
神奇，网上题解都怎么一步到位的。。。
定义第 $t$ 次访问是在 $i$ 点，要转移到下一次时只需要考虑是几点就可以了，但是这里面有个小问题，你不知道中间间隔了多少天，为了方便，记从 $i$ 到 $j$ 没有人访问的概率是 $f_{i, j}$ ，那么从 $i$ 转移到 $j$ 的概率是 $\sum_{n=0}^{\infty}f_{1, 24}^n \times f_{i + 1, j - 1} \times p_i$ ，发现这个是等比求和，则概率是 $\frac{f_{i + 1, j - 1} \times p_i}{1 - f_{1, 24}}$ 。
然后矩阵快速幂去算即可。
$\mathbb{ABC \ 270 \ G}$
整无雨了
考虑翻一次的贡献是 $B_i - A_i$ ，值域很小，直接二进制背包 $dp$ 。
$\mathbb{ABC \ 283 \ G}$
板子题
赚翻了，这个是线性基的板题。
$\mathbb{ABC \ 283 \ E}$
这应该是近几次最难的 E \doge
用和炮兵阵地一样的思路就可以解决了，枚举上一行和这一行的状态直接进行 $dp$ 。
$\mathbb{ABC \ 283 \ F}$
用拆绝对值搞过去的，记录一下最小生成树做法
也很简单，把 $(i, p_i)$ 看成二维平面上的点，距离的定义就是曼哈顿距离，然后求曼哈顿最小生成树，结论是每一个点每四十五度只会连出去一条边。但其实最后的方法都会回到按一维排序，然后另一位用数据结构。
$\mathbb{ABC \ 283 \ Ex}$
类欧！
比较懒，赛时写了个 $G$ 就去补其他题了，所以是口胡 $Ex$ 。
因为答案每一位独立，那就把每一位拆开，对于一个数 $x$ ，二进制下第 $k$ 位是 $1$ ，$2^k \le x \mod 2^{k+1} < 2^{k+1}$ ，$\frac{x+2^k}{2^{k+1}} -\frac{x}{2^{k+1}} = 1$ ，这三个条件是等价的。
那么直接用最下面的形式求解就可以了，复杂度是 $\log n$ 。
$\mathbb{AGC \ 060 \ B}$
拐角
一个比较自然的想法是在经过的路径上全部都赋值为 $0$ , 考虑怎么使这条路径成为唯一的，那么需要注意到拐角处，不能出现一样的数字，否则可以出现一条新的路径，那么每个转角都需要一个新的数字，统计拐角个数即可。
$\mathbb{AGC \ 060 \ C}$
很妙（但是暂时咕掉）
首先需要考察这两个位置的特点，既然题目是以堆为背景，那就把大根堆建出来，$2^a$ 是指的 $a+1$ 层的第一个数， $2^b-1$ 是指的 $b$ 层的最后一个数，所求的就是前一个位置上的数比后一个位置上数小的概率，因为所有的排列数很容易得到，那么对合法的排列计数即可。
考虑怎么去在堆上刻画大小关系，其实就是用拓扑排序，生成排列，满足先后关系，令 $dp_{u, v}$ 表示，在深度为 $u, v$ 的两颗满二叉树上走，先访问到 $2^a$ 的概率。
$\mathbb{AGC \ 035 \ D}$
时空倒流
注意到倒着把数字加入到序列里和正着删数是等价的。
定义 $dp_{l, r, x, y}$ 表示在 $l, r$ 这段区间里面，左边的 $a_l$ 被算了 $x$ 次，右边的 $a_r$ 被算了 $r$ 次的最小代价。
那么转移是 $dp_{l, r, x, y} = \min \sum_{p=l+1}^{r-1} dp_{l, p, x + y, y} + dp_{p, r, x, x + y} + a_{p} \times (x + y)$ 。
$\mathbb{AGC \ 059 \ C}$
从简单情况开始手玩
从 $3$ 个数 $a, b, c$ 开始思考，什么情况下 $(a, c)$ 的询问会无效。
即是说 $(a, c)$ 在询问前就已知了一条链将其联通。对于每一个三元组 $(a, b, c)$ ，如果最后出现的询问是 $(a, c)$ ，要其合法，那么 $b$ 的值不能处在 $a, c$ 的中间。
现在就可以拿到每一个三元环 $(a, b, c)$ 中的关系了，即是说 $a\rightarrow b$ 和 $c\rightarrow b$ 必须同向，于是把边压成点，跑种类并查集求出连通块的个数 $k$ ，最后答案即是 $2^k$ 。
$\mathbb{AGC \ 039 \ E}$
《简单区间 dp》 | 从限制入手
可以描述为 $3$ 个限制条件，不成环，联通， $n$ 组匹配。
考虑从匹配入手，将匹配数作为 $dp$ 的维度，定义 $dp_{l, r}$ 表示 $[l, r]$ 区间里面完成限制的方案数，发现相邻两个区间无法合并，少考虑了匹配数的限制，那么再加上一维 $i$ ，定义 $f_{l, r, i}$ 表示在 $[l, r]$ 区间里满足限制且用 $i$ 向外连边的方案数，类似地，定义 $g_{l, r, i}$ 表示区间外一点 $i$ ，向区间 $[l, r]$ 内连边的方案数。
转移时，先枚举要转移到的区间 $[l, r]$ ，$cnt = \sum g_{l, j, i} \times f_{k, r, i}$ ，注意还要更新 $f_{l, r, i} = \sum_{j + 1, k - 1, i} f_{j, k, i}$ 。
$\mathbb{ARC \ 153 \ E}$
菜是原罪
考虑正向构造是可以直接贪心做的。
对于每一个 $a_i$ ，如果 $a_i$ 小于当前字符串的头部的值，则直接放在开头，否则放结尾。
那么定义 $dp_{l, r}$ 为生成 $[l, r]$ 这个区间的方案数，确切地转移为 $dp_{l, r} = dp_{l + 1, r} \times [a_l \le a_{l + 1}] + dp_{l, r - 1} \times [a_l < a_{r}]$。
至于为什么一个是 $<$ 一个是 $\le$ 原因是当 $a_{l}$ 和 $a_{r}$ 或 $a_{l + 1}$ 相等时会算重。
到此处可以有 $\Theta(n^2)$ 的做法了，其实可以用卷积一类的东西做到 $\Theta(n \log n)$ ，但是不会了。
$\mathbb{ARC \ 154 \ A}$
。
贪心换，小的全放 $A$ ，大的全放在 $B$ 。
$\mathbb{ARC \ 154 \ B}$
基础方法
发现操作等价于把前面 $k$ 个拿出来随便插，那么直接判断后面的是否是 $s$ 的子串就可以了，套二分就可以过了。
$\mathbb{ARC \ 154 \ C}$
不是很理解
直接模拟即可。。。
$\mathbb{ARC \ 154 \ D}$
interesting
这个交互有点意思，我们可以首先把 $1$ 的位置用 $n$ 次问出来。
问出来之后就可以 stable_sort 排序直接过了。
$\mathbb{ARC \ 154 \ E}$
发掘性质！单点！改写！
首先改写这个贡献的式子
$$ f(P) = \sum_{i = 1}^{n} (\sum_{j < i}[Q_i < Q_j] - \sum_{j > i}[Q_i > Q_j]) \times i $$假设我已经拿到了最后的序列，那么根据定义，每个点的贡献是
$$ g(i) = (\sum_{j < i}[Q_i < Q_j] - \sum_{j > i}[Q_i > Q_j]) \times i $$考虑这个贡献用动态的方式呈现，首先这个序列有序，对于一个位置 $i$ ，将他右边的一个数 $j$ 放在前面去，这个位置变成 $i + 1$ ，此时贡献是让 $g(i)+1$ ，反之，放一个左边的到后面去，位置变成 $i - 1$ 贡献 $g(i) - 1$ ，那么可以得到 $g(i)=i(i - Q_i)$ 。
那么此时计算 $Q_i$ 在某个位置上的期望就可以了，很容易发现，这个期望很对称，将 $Q_i$ 放在 $i$ 和放在 $n - i + 1$ 这两个位置上的方案数相同，那么最后位置的期望就是 $\frac{n + 1}{2}$ 。
$\mathbb{ABC \ 287 \ E}$
trie板题
$\mathbb{ABC \ 287 \ F}$
比较经典
定义 $dp_{u, i, 0/1}$ 表示以 $u$ 为根的子树被划分成 $i$ 个块，$u$ 节点本身选不选的方案数，树形 $dp$ 即可。
$\mathbb{ABC \ 287 \ G}$
线段树上二分
rt.
$\mathbb{ARC \ 155 \ B}$
re 导致的 wa
观察这个式子 $f(x) = \mid \mid x - a \mid - b \mid$ 可以拆成 $\min \{ x - (a + b), x - (a - b) \}$ 。
这个形式直接用 set 维护就可以了，结果 upper_bound 找到了 end ，一波 *it 直接 GG。
$\mathbb{ARC \ 155 \ C}$
反复往后跳，双向关系
看到操作使两个序列相等，注意到是否有双向关系。
因为不要求步数，那么构造使得两个序列变成同一个形式就可以了。
首先考察发现只有 ooe 和 eee 这两种形式可以区间改序，并且发现这个可以有传递的可能，什么意思呢。
对于下面这个情况 ooeeeeeeeee 我们可以把最前面的两个 o 反复操作，让 oo 到最后面去，并且可以发现，我们可以把所有的 o 全部转移到后面去，最后的形式大概是 eeeeoeoooooo ，为什么中间要嵌入一个 e 呢，因为我们可以利用这个 e 使得后面的所有的 o 和前面的 e 全部改序。
那么直接模拟这个过程就可以了。
$\mathbb{ARC \ 155 \ F}$
E, F 先咕着，做一些多项式题，这篇题解是我人工翻译的
[1] Double Counting 双重计数
考虑从叶子节点开始，用唯一的方式（如果有的话）来构造出一棵满足条件的树。因此，我们可以对一棵每个节点度为 $D_i$ 的有向有标号树来代替无向树进行计数。
常用的对有标号树计数的方式是双重计数，设 $A$ 是原问题的答案，$B$ 是这棵有根树的数量，其中
- 树根是 $N$ 个节点中任意一个。
- 从节点 $i$ 连出的 $D_i$ 条边用 $1$ 到 $D_i$ 标号。
那么，$B=A \times N \times \prod_{i=1}^{N}D_i!$ 。
[2] Construction of the rooted trees 有根树的构造有根树可以按照一下方法构造，此外对于所有的树，按以下方式都有唯一构造。
- 确定与根相连的节点集合 $S$ 。
- 对于 $S$ 中的节点，从 $D_i$ 中选择一条指向根，并给其他的边选择指向的节点。
- 确定其他边的终点。
考虑在完成了第一步和第二步之后，执行第三步的方式有多少，让我们按节点编号的升序，边的升序来开始考虑，可以选择没有父节点且与当前起点不在一个连通块里的点作为终点。在一开始，有 $n - \mid S \mid$ 个节点没有父节点，所以有 $(n - \mid S \mid - 1)!$ 种方式，特别地，这一步的方案数和上一步无关。
接下来，来计算第二步的方案数。这里有 $\prod_{i \in S} D_i$ 种方式选择指向根的边，对于其他边的终点的方案数，观察可以得到这个方案数等于 $N$ 个节点 $\mid S \mid$ 条边组成森林的方案数。
现在，我们把选出来的 $S$ 忽略掉，从 $N$ 个节点和 $0$ 条边开始，重复以下操作 $\mid S \mid$ 次，形成一个有根森林。将一个节点 $u$ 与另一个在其连通块之外的没有父节点的 $v$ 连接。这里有 $\prod_{i = 1}^{\mid S \mid} N \times (N - i) = N^{\mid S \mid} \times \frac{(N - 1)!}{(N - \mid S \mid - 1)!}$ 来选择 $u$ 和 $v$ ，然后消序得到 $N^{\mid S \mid} \times \frac{(N - 1)!}{\mid S \mid!(N - \mid S \mid - 1)!}$ 种方案。对称地来看，其中一共有 $N^{\mid S \mid} \times \frac{(N - 1)!}{\mid S \mid!(N - \mid S \mid - 1)!} \times \frac{1}{N^C \mid S \mid} = N^{\mid S \mid}(N - \mid S \mid)$ 种方案满足所选出来的父节点集合为 $S$ 。
因此，在第一步钦定了 $S$ 之后，这里有 $N^{\mid S \mid - 1} \times (N - \mid S \mid) !\times \prod_{i \in S} D_i$ 棵满足条件的有根树可以被构造出来。
[3] Using convolution 使用卷积
故而，我们定义 $f(x) = \prod_{i}^{N}(1 + D_ix)$，我们有 $B = \sum_{k = 0}^{N - 1}N^{k - 1} (N - k)[x^k]f(x)$ 。于是就可以用多项式直接做了。
$\mathbb{AGC \ 043 \ D}$
需要手玩，如果画成柱状图大概是
发现分布很有规律，有连续的单调的段，长度 $len \in [1,3]$，并且每段的开头放在一起单调不降，长度为 $2$ 的段数量永远小于长度为 $1$ 的段。
考虑为啥会出现这种情况，对于原序列一段 $A_1, A_2, A_3$，如果 $A_1 > A_2$ 或者 $A_2 > A_3$，那么这三个数会有两个连续被取出；如果 $A_1 > A_2$ 并且 $A_1 > A_3$，这三个数会一起取出。
上述一起取出来的数一定会被扔进一个单调的块里面，因为大小为 $2$ 的块和大小为 $1$ 的块都会成对出现，所以大小为 $2$ 的块的个数一定小于等于大小为 $1$ 的块的个数。
于是定义 $dp_{i, j}$ 表示现在长度为 $i$，大小为 $1$ 的块的个数减大小为 $2$ 的块的个数为 $j$ 的方案数，可以直接转移。
$\mathbb{ARC \ 163 \ C}$
我是肯尼迪，我脑洞非常大。
这题是真抽象，但是我想到了就更抽象。
有个东西叫裂项相消，就是说 $1 + \sum_{i = 2}^{n} \left(-\frac{1}{i} + \frac{1}{i}\right) = 1$，换个写法 $\frac{1}{2} + \sum_{i = 2}^{n - 1} \left(\frac{1}{i} - \frac{1}{i + 1}\right) + \frac{1}{n} = 1$，于是这道题就会做了。
然后这样就会WA，对于 $n = 6$ 会得到如下方案 $2, 6, 12, 20, 6$，出现了两个 $6$。显然不对。
如何避免呢？对于 $n = (i + 1)i$ 的形式，可以先拆一个 $2$ 出来，然后再裂项一下凑出剩下的 $\frac{1}{2}$。
$\mathbb{ARC \ 163 \ D}$
不会竞赛图性质，GG。
现在会了，这里指 将一个竞赛图缩点之后形成的 DAG 是一条单链，证明方式考虑依次加点进图即可。
然后还是不会计数，听说是套路，但是真的不会。
难点在于去计算所有强连通块个数的和。考虑换一种方式去描述强连通块个数？
结合到性质，发现对于一张固定的图，对它缩点，劈开这条单链使其成为两个非空集合的方案数等于强连通个数减一。
更具体地来说，如果缩点后图变成 $scc_1 \to scc_2 \to scc_3 \to \dots \to scc_n$，将其划分成 $A,B$ 两个集合，满足 $A \cup B = scc, A \cap B = \varnothing, \forall u \in A, v \in B, \exists e = u \to v$。
于是达到了切换主体的目的，定义 $dp_{i, j, k}$ 表示考虑了前 $i$ 个点，$\mid A \mid = j$，有 $k$ 条小连大的边，$\Theta(n^4)$ 转移即可。
1 | dp[0][0][0] = 1; |
$\mathbb{ARC \ 164 \ D}$
发现这个东西和括号匹配很像，但是一开始想偏了，想成把 + 看成左括号，把 - 看成右括号了。
其实这样非常不对，比如 +--++-。
正确的想法是要把每个球的移动方向看成左右括号。考虑算贡献，本来这个非常套路，但是当时降智了，以为要去枚举匹配的两个点计算，其实这个贡献非常好拆，一对匹配的点 $(x, y)$ 的贡献为 $y - x$，拆成单点，如果方向往左，贡献为正，方向往右，贡献为负。
因为左边的序列定了，右边的序列也能定，所以枚举左边有多少个 ? 变成了 +，以此来判断当前小球的移动方向，即可计算贡献了。
$\mathbb{ARC \ 159 \ D}$
哈哈，我是傻逼。
首先观察得到性质，如果选了一个区间 $[l_i, r_i]$ 中的 $x$，那么一定会去选 $[x, r_i]$，证明非常显然，但是我没想到。
于是分类讨论即可，记 $dp_i$ 表示以第 $i$ 个区间结尾， LIS 的最大长度。
如果 $r_j < l_i$，$dp_i = \max\{ dp_j \} + (r_i - l_i + 1)$；如果 $r_j \ge l_i$，$dp_{i} = \max\{ dp_j - r_j \} + r_i$。
$\mathbb{ARC \ 159 \ C}$
哈哈，我是傻逼。
比较厉害的一点在于如何把对所有元素的操作通过叠加使其变成对两个元素的操作。
首先做一遍 $1, 2, 3, \dots, n$ 然后再做 $n, n - 1, n - 2, \dots, 1$ 相当于啥都没做，于是在第二次操作时交换相邻两个数，那就实现了一个数加一，一个数减一，这样就能构造答案了。
$\mathbb{AGC \ 001 \ D}$
比较有意思的构造题，值得思考的点在于转换这个问题。
算是积累一个技巧，看到回文的限制注意到可以把对应的两个点之间建立边一类的联系。
这道题就充分体现了这个玩意。因为大条件是 $\sum{a_i} = \sum{b_i} = n$，需要做的是在把 $a$ 这边的限制刻画完之后把 $b$ 拼上去。
然后我来偷两张图（/bx command_block）。
这个构造非常自然，一个是 $a_i$ 为奇数一个是 $a_i$ 为偶数的情况。但是也注意到了如果 $a$ 中出现了大于两个奇数，这个是 Impossible 的。
然后按图模拟即可，注意特判 $m = 1$ 的情况。
$\mathbb{AGC \ 001 \ E}$
我先猜一手，这道题应该从 $a_i, b_i$ 的值域大小出发并转组合意义去做。
注意到 $\binom{a_i + a_j + b_i + b_j}{a_i + a_j}$ 的组合意义是从 $(0, 0)$ 出发走到 $a_i + a_j + b_i + b_j$ 的方案数。
但是这样有点问题，我需要去记录每种情况的 $a_i + a_j + b_i + b_j$ 是多少，相当于这个组合意义并没有起到作用。思考这样做的问题在于组合意义是对于 $(a_i, b_i), (a_j, b_j)$ 这两个点对而言的，复杂度与 $(a_i, b_i), (a_j, b_j)$ 这样的点对数量有关，如果要降复杂度，需要拆单点贡献。
修改一下组合意义，把起点从 $(0, 0)$ 挪到 $(-a_i, -b_i)$ 上去。于是转化为求两两点对之间的路径数，这样复杂度非常对，因为这样做的复杂度与 $a_i, b_i$ 的值域相关，总的复杂度是 $\Theta(ab + n)$，需要注意减去 $i = j$ 的情况后答案应该除以 $2$。
吐了， atcoder 模数居然不是 $998244353$。 /tuu
$\mathbb{AGC \ 001 \ F}$
先放一波我的错误思路。
看起来不是很好处理，先变形一下这个限制？
$i, j$ 能够交换必须满足 $\mid i - j \mid \ge nk, \mid a_i - a_j \mid = n$ 那么 $i$ 和 $j$ 能够换。
发现上面这个转化不是等价的，只是一个必要条件。
怎么办？这说明了从条件出发并不是一个好的方向。那从问题出发，要是字典序最小，不难想到有这样一种方式去交换。
$p1 < p2 < p3$，且 $p1, p2$ 之间距离大于等于 $k$，$p2, p3$ 之间距离小于 $k$，$a_{p2} = a_{p1} + 1 = a_{p3} + 2$。
那么我做swap(p1, p2)后接一个swap(p2, p3)就变成了 $p3, p1, p2$ 这样就非常优秀。
能不能推广？能不能月下无限连？
不能。
问题在于我需要去刻画三个点的关系，并且在不断弱化的我限制，这样是非常不优秀的。
并且值得注意的是在这种有限制的交换关系求方案思路重点一般在限制上，但是我从一开始弱化了这个限制导致不可做。
这道题解法就很牛逼了，题目着重刻画的是下标和值的关系，正解是把这两个玩意儿反过来。这显然不是人类能够想出来的东西，但是也有其合理性。
记反过来之后的排列是 $q$，$i, j$ 能交换的条件是 $i,j$ 相邻，且 $\mid q_i - q_j \mid \ge k$。为什么这样会更好下手？下标相邻这样的限制是非常强的，它是由 $\mid a_i - a_j \mid = 1$ 这个限制转化过来的。这就提示在有对偶（姑且称之为）的两个限制下，尽量把强限制（等于）放在更好刻画的位置（下标），把若限制（偏序关系）放在比较能用某些结构刻画的位置（值域）。
下一步继续用更强的限制刻画偏序关系，当 $\mid q_i - q_j \mid < k$ 时他们的相对顺序不会发生改变，因为交换是相邻的，当存在交换使 $i, j$ 相邻时他们会因为值的限制卡住动不了。
然后对这样的点对 $i \rightarrow j$ 建边。
最后把这个边建回原图，对于 $p_i, p_j$ 如果 $\mid i - j \mid < k$，则要求他们的大小关系不变，如果要求 $p_i < p_j$ 就建边 $i \rightarrow j$。
运用一下拓扑字典序原理解决这个问题，注意不能直接贪心，应该建反图后从大往小贪（典中典）。
然后想了一下发现我剩下的几步还是不会（纯纯废物了）。
考虑 $i$ 能向 $\{ j : \mid i - j \mid < k, p_j < p_i \}$ 这个集合里面的点连边，$i$ 的入度为 $0$ 的充要条件是 $p_i$ 是 $[i - k, i + k]$ 这个区间里面的最大值。那么用一个大根堆去维护目前出度为 $0$ 的点即可，然后用线段树维护区间最大值，在删除 $i$ 时，查看 $[i - k, i), (i, i + k]$ 中最大值编号，如果入度为 $0$ 就塞进大根堆。
$\mathbb{AGC \ 002 \ D}$
忘了整体二分怎么做了，完蛋啦，哈哈。
没啥好说的，直接整体二分拿并查集连连就好，然后我调了 2h+，原因是我是唐，在写可撤销并查集时路径压缩了。🤡
$\mathbb{AGC \ 002 \ F}$
换个方式去刻画题目，考虑到所有颜色都是等价的（把涂白的球记为 $0$），那么题目变成要求第 $i$ 种颜色的球出现在第 $i$ 个白球之后，最后的方案总数乘 $n!$ 即可。发现可以把白球出现这个事件拎出来以此对整个过程分段。定义 $dp_{i, j}$ 表示放了前 $i$ 个白球，前 $j$ 种彩球都放了 $k - 1$ 的方案数。
千万不能把每种彩球分开处理，原因很简单，分开处理后需要记录每种彩球出现了多少个，而这种开销是无法接受的。相反把每种彩球都分在一起可以更有效地去计数。
转移分成两种
- 放一个白球，这样一定合法，方程是 $dp_{i + 1, j} = dp_{i + 1, j} + dp_{i, j}$
- 放一种彩球，满足的要求是 $j + 1 \le i$，注意到要先放一个在最靠前的空位上，于是剩下了 $k - 2$ 个球，有 $\binom{nk - i - (k - 1)j - 1}{k - 2}$ 种放法，于是方程是 $dp_{i, j + 1} = dp_{i, j + 1} + dp_{i, j} \times \binom{nk - i - (k - 1)j - 1}{k - 2}$。
需要特判 $k = 1$。
$\mathbb{AGC \ 003 \ D}$
从考察一个数是否是完全立方数出发，一个数如果是完全立方数，当且仅当它的所有质因子的次数都能被
$3$ 整除。
一个很 naive 的思路是分解每个质因数，按模 $3$ 的余数分类，一个类和恰好另一个类对应乘积是完全立方数。
但是这个数据范围着实分解不了质因数。首先把 $(1, s^{\frac{1}{3}}]$ 内的质数除掉，这样剩下的性质就只能是 $p, p^2, p_1p_2$，注意到 $p^2$ 需要再补上 $p^{3k + 1}$ 才会变成完全立方数，因为已经超过了 $s^{\frac{1}{3}}$，所以补上的一定是 $p$，而 $p_1p_2, p$ 必须补上 $p^2, p_1p_2$ 才行。
于是我们调了一下上界获得了和暴力一样的做法。
$\mathbb{AGC \ 003 \ E}$
神仙东西。
首先去除一堆没用的 $n_i$，得到的序列是严格递增的。这个操作是在干嘛？
是把原序列复制几遍并接上一个前缀，记 $P_i$ 为操作了 $i$ 次之后的序列，$dp_{i, j}$ 表示 $j$ 在 $P_i$ 中出现的次数。
令 $t = \lfloor \frac{n_i}{n_{i - 1}} \rfloor$，那么 $P_i$ 就由 $t$ 个 $P_{i - 1}$ 和 $P_{i - 1}$ 的前 $n_i \mod n_{i - 1}$ 个字符组成，于是先将 $dp_{i, j}$ 初始化为 $dp_{i - 1, j}$。
然后前缀怎么办？？？
现在重新想一下上面的思考是怎么来的，首先淡化 $P_i$ 和 $P_{i - 1}$ 之间的转移。改成 $P_i$ 从 $P_{pre}$ 转移过来。
那么有
$\mathbb{AGC \ 003 \ F}$
你说得对，但是连通块个数等于点数减边数连通块个数等于点数减边数连通块个数等于点数减边数连通块个数等于点数减边数连通块个数等于点数减边数连通块个数等于点数减边数连通块个数等于点数减边数连通块个数等于点数减边数连通块个数等于点数减边数连通块个数等于点数减边数做完了。
没有，注意可以直接矩阵乘法加速。
$\mathbb{AGC \ 004 \ E}$
物理原理，相对移动。
固定机器人不动就变成了挪动出口去救机器人，假设把出口挪动了 $(p_x, p_y)$，那么以 $(x_0, y_0)$ 为左下角到以 $(x_0 + p_x, y_0 + p_y)$ 为右上角的这个矩阵里的所有机器人可以被救。
于是直接 $\Theta(n^4)$ 定义 $dp_{w, s, a, d}$ （含义看键盘可知）暴力转移即可。
$\mathbb{AGC \ 004 \ F}$
大分类讨论题。
非常神了，看到 $m \in [n - 1, n]$，不难想到分成树和基环树的情况讨论。
首先讨论树的情况，每一次都会改变两个点的颜色，一个点必须被改变奇数次，所以当总点数为奇数时直接判无解。
那么偶数时怎么计算最小步数呢？能不能形象一点？改变颜色一类的题目要想到把改变颜色变成移动颜色之类的更好计算的方式。
因为树是二分图，于是把整棵树都黑白染色，现在改变一下操作，变成颜色不同的两个点可以互换颜色，不难发现一个点被操作奇数次的结果是颜色反色。于是把黑色看成有棋子在上面，把白色看成空，操作就是移动棋子，使得每个棋子最终落在一开始没有棋子的地方。
也容易发现当棋子和空白点数不同时是无解的。
对于一个节点 $u$，假设子树内有 $x$ 个棋子，总共点数有 $siz_u$ 个，可以猜想到经过 $u$ 这个节点的棋子数目下界是
$x - (siz_u - x)$ 步，意思是能够内部消化的就内部消化，不能内部消化的都要经过 $u$ 离开这颗子树，于是所有点被经过的次数就是需要移动的总步数（注意一下取绝对值），多单位移动的步数问题可以转化为考虑每一个节点被经过的次数问题。
然后是基环树的情况，次数需要讨论环的奇偶性。
当环是偶环时，先抠出来一条边变成树，是否无解和树的情况一致，考虑多出来的这条边能给我们带来什么？
显然某些情况下直接通过这条边要比在环上绕一大圈更优，于是现在单独考虑这条边要被经过多少次。
把环上的点拉出来为 $p_1, \dots, p_l$，这条边连接了 $p_1, p_l$，记棋子为 $1$，空格为 $-1$，子树和为 $a_i$，如果这条边被经过了 $x$ 次，那么最后的答案是 $\sum_{i \in left} \mid a_i - x \mid + \sum_{i \in right} \mid -a_i - x \mid + \mid -x \mid$。（初一数学问题）。
最后是奇环情况，此时这个环两边的点是同色的，操作一次增加或减少 $2$ 个棋子。
那么断开这条边，只要黑白点数的差是偶数就可以利用这条边调整至有解，于是先调整有解，然后跑树的做法就可以了。
$\mathbb{AGC \ 005 \ D}$
我一眼秒了，然后看题解发现推错了一步，题解是wgy在两年前写的。
第一步先容斥，记 $f(i)$ 表示至少 $i$ 个地方填冲突的方案数，于是得到
考虑怎么算这个 $f(i)$，因为我组合数学撇，所以先建图，建出来 $k$ 条链，相当于在这 $k$ 条链上选出来 $i$ 条边，有一个 $\Theta(n^2)$ 的 dp 可以直接做。
$\mathbb{AGC \ 005 \ E}$
感觉很神奇，趁还没被题解定式思维，先写一下我自己的想法。
可以观察到答案一定是偶数，最后一步一定是 B 去抓住 A，A 不可能自己撞上去，因为他选择停一步会更优。
所以应该是从最后结束或是结束不了的情况入手，分析两个人的策略。
首先排除掉无解的情况，即是 B 永远抓不到 A，利用样例 4，看到这种情况下 A 可以反复横跳，即是说对于 A 树里面直接相连的 $i \rightarrow j \rightarrow k$，如果 B 树中直接连接 $i, j, k$ 的只有 $1$ 条边，那么 A 可以利用这个链一直跳。
那么反过来如果不存在这种情况 B 的策略就应该是一直朝着有 A 的子树里面走，A 跑到离 B 最远的点等死就好了？
看了题解，题解的描述更具体，如果一条红边连接了在蓝树上两个距离大于 $2$ 的点，那么只要 A 跑到了这两个点任意一个，游戏就不会停止。否则就很好想了，此时不存在一条红边连接了蓝树上距离大于 $2$ 的点，根据最先的观察，A 最理想的情况一定是跑到蓝树上离 B 的初始点最远的点然后等 B 来找他。
于是这是一个对于先手的单手游戏了，对于先手一定需要保持在第 $i$ 步走到的节点 $p_i$ 满足 $dis(p_i, B) > i$ 才能保证不被抓住，这样 $\Theta(n)$ 就能做了。
很牛逼啊，为啥最后做法这么简单，因为无解的情况自带性质，如果有解那么必定使无解的条件不成立。提示是从无解情况出发，用无解的性质当条件做题。
$\mathbb{AGC \ 005 \ F}$
这是什么套路？我完全不会。
看起来很 dp，所以用湘妹儿思考法我来切换主体。
考虑一个点 $u$ 对询问 $i$ 能造成啥贡献？
枚举块的大小得到下面的式子
哈哈，我就会这个 $\Theta(n^2)$ 的暴力。😓😓😓
哈哈，切换主体之后换不回来了。
重新定义 $f$ 把 $f_i$ 的下标改成连通块大小。
然后把 $siz$ 相同的子树视为一个整体。记子树大小为 $i$ 的子树个数为 $cnt_i$，改写上面的式子
$$ \begin{aligned} f_i &= n \binom{n}{i} - \sum_{siz = 1}^{n} cnt_{siz} \binom{siz}{i} \\ &= n \binom{n}{i} - \sum_{siz = 1}^{n} \frac{cnt_{siz} siz!}{i!(siz - i)!} \\ &= n \binom{n}{i} - \frac{1}{i!} \sum_{siz = 1}^{n} cnt_{siz} \cdot \frac{siz!}{(siz - i)!} \\ \end{aligned} $$记 $F = \sum cnt_{siz} siz!, G = \sum \frac{1}{(siz - i)!}$ 反转一下 $G$ 的下标
发后面一坨是具有 juanable 的性质。
现在写完了，我觉得说得对，没什么困难的地方。
👆扯淡。那为啥我做不来。
$\mathbb{AGC \ 006 \ C}$
真聪明，置换快速幂。😓
这个期望一眼吧。。。
难点在于需要很快找到换了 $k$ 次之后的位置，然后发现这个映射和次幂有着相同优美的性质。
于是可以 $\Theta(n \log k)$ 做了。
$\mathbb{AGC \ 006 \ E}$
这个东西是？魔方？？？不让我求步数那我是不是真的可以当魔方做？
🤮 好复杂，先放了。
$\mathbb{AGC \ 006 \ F}$
既视感过于强烈以至于我觉得这就是道傻逼题。
没有手玩能力的我什么时候才会做这种题？？？😭
《手玩一下》发现可以三染色。
为什么想不到从链开始入手为什么想不到从链开始入手为什么想不到从链开始入手为什么想不到从链开始入手为什么想不到从链开始入手为什么想不到从链开始入手为什么想不到从链开始入手为什么想不到从链开始入手？
当 $x + 1 \equiv y \pmod 3$ 时 $x,y$ 之间会有连边，于是三染色，如果染色失败，就说明这张图会变成任意两点之间会有连边，贡献是 $2^{siz}$。
如果只有两种颜色，那啥也干不了。
否则记每种颜色点数为 $c_0, c_1, c_2$ 贡献是 $c_0c_1 + c_1c_2 + c_0c_2$。
$\mathbb{AGC \ 007 \ E}$
首先二分答案出 $mid$，转成判定问题，判定能不能使所有叶子之间的路径权值都小于 $mid$。
结合到题目给出的树的特定的形态思考路径有哪些性质？对于 $u, v$ 是兄弟节点，在访问了其中一个之后一定会马上访问另一个，因为每条边只能经过两次，更进一步地，发现这是在模拟深搜的过程。
考虑把 $dfn$ 序拉出来，记 $dfn$ 的反序列为 $p$，只保留叶子的信息为 $p_1 \rightarrow p_2 \rightarrow \dots \rightarrow p_k$。
在二分出 $mid$ 的情况下这个序列合法当且仅当 $\forall i \in [1, k), \mathrm{dist}(p_i, p_{i + 1}) \le mid$，考察这个序列的生成方式，如果叶子节点存在兄弟节点，那么这一对将会连续加入序列，否则单独加进去。那么对于以 $u$ 为根的子树内一定会存在一条跨过左右子树的路径，思考这条路径怎么去计算，令 $son_0, son_1$ 分别为 $u$ 的两个儿子，$leaf_0, leaf_1$ 分别为左子树内最后访问的叶子节点和右子树里最先访问的叶子节点，那么这条路径 $l = \mathrm{dist}(leaf_0, son_0) + \mathrm{dist}(son_0, u) + \mathrm{dist}(u, son_1) + \mathrm{dist}(son_1, leaf_1)$。拆一下，中间的 $\mathrm{dist}(son_0, u) + \mathrm{dist}(u, son_1)$ 是定值，所以决定这条路径的是 $\mathrm{dist}(leaf_0, son_0) + \mathrm{dist}(son_1, leaf_1)$，所以现在可以有一个初步的状态为 $dp_{u, l, r}$ 表示对于以 $u$ 为根的子树内第一个访问到 $l$，最后一个访问到 $r$ 的过程中路径的最大值，转一下
然后写成判定形式
$$ \begin{aligned} dp_{u, l, r} = dp_{son_0, l, k_1} \& dp_{son_1, k_2, r} \& [\mathrm{dist}(u, k_1) + \mathrm{dist}(u, k_2) \le mid] \end{aligned} $$发现这个状态很蠢。怎么优化？？？不会了。
问题在哪里？在于我的状态后两维记录的是叶子节点的编号，导致我很难看出关键之处，换一下把叶子节点编号直接改成到该叶子节点的距离。
$$ \begin{aligned} dp_{u, l, r} = dp_{son_0, l, k_1} \& dp_{son_1, k_2, r} \& [ k_1+ k_2 \le mid] \end{aligned} $$突破口在状态本身，减少状态数的最直接方法是去掉不必要的状态。也就是说如果存在 $l_1 < l_2, r_1 < r_2$，那么对于 $dp_{u, l_1, r_1}$ 来说 $dp_{u, l_2, r_2}$ 这个状态是没有意义的。
这部就有单调性了吗，对于 $l$ 升序排，那么对应的 $r$ 必定是降序。对于 $dp_{x, l, r}$ 来说在另一棵子树内能和它合并的状态一定是一个前缀，直接双指针就能做到 $\Theta(n \log^2n)$，状态数不难分析得到。
$\mathbb{AGC \ 007 \ F}$
拿到这种题完全没有思路。。。开始不了啊。。。
注意可以从特殊情况开始思考，首先判掉 $S = T$。
算是长脑子，记住这种生成序列一类的题可以从被生成序列和原序列之间（点对点、区间对区间）的关系入手。
这题最重要的性质在于将被生成元素和原元素之间连边后所有的边都不相交，且一定是一个字符对应一个区间，这是由这道题特殊的生成方式决定的，重点在于要动手多玩。
得到一个初步的策略，对于一个点，先尽量往右走，走到需要被覆盖的左端点处，然后一路复制下来，最后一步覆盖掉整个区间。
说得非常抽象，具体操作？
看了一圈题解感觉抽象。放个代码。
1 | int up = n - 1, down = n - 1; |
$\mathbb{AGC \ 007 \ D}$
n 只小熊，我好害怕被小熊打手板😭，，，
首先观察到一点，假设之前给了 $i$ 号位上的小熊一颗糖，在走到 $j$ 之后回头到 $i$ 如果能够捡起金币，那么再往 $j$ 的途中所有的小熊给出的金币都能收集到。所以他的路线应该是走过去折回来走过去折回来一直到终点，所有点要么经过一次要么经过三次。然后我会 $\Theta(n^2)$ 大力 dp 了。定义 $dp_i$ 表示 $[1, i]$ 中的所有金币都被捡起到达 $x_i$ 的最小时间，那么枚举上一次的转移点 $j$ 则 $dp_{i} = \min\{dp_{j} + cal(j + 1, i)\}$，其中 $cal(j + 1, i)$ 表示搞定 $(j, i]$ 中间这一段小熊的耗时。我搞定很多小熊的耗时。耗时为 $x_i - x_{j + 1} + \max \{ 2(x_i - x_{j + 1}), T \}$。然后我不会了。愚蠢啊啊啊！$x_i - x_{j + 1}$ 全部加起来就是 $E$，所以可以忽略，去掉这一坨看起来更厉害。$dp_{i} = \min \{ dp_j + \max \{ 2(x_i - x_{j + 1}), T \}$，里面有 $\max$ 看起来很不舒服，拆一下。要分类讨论。
- $2(x_i - x_{j + 1}) > T$
- 则转移是 $dp_{i} = \min \{ dp_j + 2(x_i - x_{j + 1}) \}$
- $2(x_i - x_{j + 1}) < T$
- 则转移是 $dp_{i} = \min \{ dp_j + T \}$
转移是一次的啊啊啊啊啊啊，这个范围直接线段树就行了，更牛逼的能单调队列做到 $\Theta(n)$。
$\mathbb{AGC \ 008 \ E}$
既视感过强。
很明显可以先连边看看性质。注意到 $a$ 是序列而非排列，不能直接往 $a_i$ 连边，那就连 $p_i \rightarrow i$？考虑 $p_{p_i}$ 是个啥，应该连 $p_{p_i} \rightarrow p_i$ 还是 $p_{p_i} \rightarrow i$。
显然保留 $p_{p_i} \rightarrow p_i$ 更好，这是一个置换环，考虑单看这一堆环能不能发现些性质。
$a_i$ 要么选 $p_i$ 要么选 $p_{p_i}$，在图上相当于选一条边的两个端点。
蚌埠住了。我要反向计数。
不会做了。破大放，我来看题解。
我是定势思维小丑，能不能学会分类讨论？
思路是观察图的形态，分类讨论。
又臭又长，不做了。
$\mathbb{AGC \ 008 \ F}$
没有模数？
这次学乖了，我从不合法状态开始思考。🤔
什么情况下两个点 $(u, d_u), (v, d_b)$ 染色情况会相同？首先这两个点的染色区域一定能互相覆盖，考虑到 $lca$ 处交汇，则还应该满足 $d_u - \mathrm{dist}(lca, u) = d_v - \mathrm{dist}(lca, v)$，这个条件满足了这两个点染到 $lca$ 后继续往上延申或者向 $lca$ 的其他子树染色的长度相同。
现在还需要解决从 $lca$ 到 $u, v$ 路径上所有点子树内的染色情况，一眼看出来这些子树一定被完全染色。这里就有点小问题，怎么知道这些子树里距离 $u$ 最远的点？记 $\mathrm{dep}(u)$ 表示以 $u$ 为根的子树深度的最大值，对于从 $u$ 到 $lca$ 这条路径上的子树内距离 $u$ 最远的点可以被刻画为 $dep_{u} - dep_{x} + \mathrm{maxdep}(x) - dep_{x}$。记 $f(x) = \max \{ \mathrm{maxdep}(y) - 2dep_{y} \}, y \in subtree(x)$，于是可以算出来一个点涂满这棵子树的耗时，记为 $t_{(lca, u)}$。
于是直接枚举 $lca$ 去计算不合法的点对数即可？具体一点，对于 $lca$，在其子树内深度相同的点 $v, dep_v = k$ 来说，能产生的不同涂色方案的贡献是 $\sum_{v} t_{(lca, v)}$，发现还是会重。🤬
怎么弄？对于 $(u, d)$ 同构的二元组，按 $u$ 这一维计算不优秀，于是按 $d$ 来算，只统计 $d$ 最小时的答案，这样就对了。
看了一圈题解，什么鬼玩意，大家的思考方式都一样是吧。。。😓
$\mathbb{AGC \ 009 \ D}$
这题意好神奇。这是要求？给定树的点分治层数最小值？
对，就是这个，我会求上界，是 $\log$。😄
这 dp 不了了吧。考虑怎么去贪？对这个很不熟，完全不会。😭
以 $u$ 为中心合并一些等级为 $k$ 的子树然后把 $u$ 赋为 $k + 1$，现在的目标是最小化最大权值。对于每棵子树，记录哪些权值到根的路径上没有更大的权值（记为“出现”）。合并子树的时候看一下同时有两个出现的最大权值 $k$ 是多少，然后当前点取 $k + 1$，空间随便开。
$\mathbb{AGC \ 009 \ E}$
注意到它保证了 $n + m - 1$ 能被 $k - 1$ 整除。这是啥啊？？？🤔
好的，一点不会，我去看题解了。
这个是人类解法？？？要是下次再看到这种东西我还不会我就吃💩。
转成 $n$ 个叶子节点的 $k$ 叉树，其中 $n$ 个上写着 $0$，$m$ 个上写着 $1$，非叶子节点上写着它的 $k$ 个儿子的节点的权值的平均值，发现最后的权值只和所有标上 $1$ 的叶子节点的深度有关。
如果一个标上 $1$ 的叶子节点的深度为 $d$，那么到最后它会被除 $d$ 次，每次都除以 $k$，所以贡献是 $(\frac{1}{k})^d$，总的贡献是 $\sum_{i = 1}^{m} (\frac{1}{k})^{d_i}$。
所以现在只要能构造出合法的 $k$ 叉树就可以了，怎么保证合法？如果所有的叶子节点上都是 $1$，那么根节点也是 $1$，所以只要满足 $\sum_{i = 1}^{m + n} (\frac{1}{k})^{d_i} = 1$ 即可，注意这里的 $d$ 是针对所有叶子节点（不管上面是否是 $0/1$）。
然后就可以转换问题了，变成有多少个 $val$ 满足能被写成 $\sum_{i = 1}^{m}{(\frac{1}{k})^{x_i}}$，且 $1 - val$ 能被写成 $\sum_{i = 1}^{n}(\frac{1}{k})^{y_i}$。
这里记 $h = (n + m - 1) / (k - 1)$ 即树的高度（我这下懂了题目里面的条件是在干嘛了），但是直接去枚举每一层的 $1$ 的个数会算重，因为一层里面的 $k$ 个 $1$ 会等价于上一层的一个 $1$。
于是去枚举进行了多少次把一层的 $k$ 个 $1$ 换成上一层的 $1$ 个 $1$ 的操作，记为 $X$。
注意到此时的树高变成了 $h - X$，$1$ 的个数少掉了 $k - 1$ 个，所以此时保证每一层的 $1$ 的个数不超过 $k - 1$ 就行了，根据先前的思考可以知道最后的答案是一个由 $m - k + 1$ 个 $1$ 拼出来的 $k$ 进制数。于是 $\Theta(n^2)$ 计算即可。
$\mathbb{AGC \ 010 \ D}$
从最后的状态开始想，形式大概是一堆相同的数 $x$ 外带一个 $x + 1$，现在不管谁对 $x + 1$ 操作一下，剩下的那个人就输了。
感觉这个除以公倍数的操作很难受，
$\mathbb{AGC \ 010 \ E}$
思考了 5min 想起来了上周我的做法。
这种东西正着一般不好入手，反着想，如果两个数不互质，那么他们的相对顺序就不会改变。
然后数据范围是 $2000$ 可以直接 $\Theta(n^2)$ 把这样的数对拎出来，这样的关系是有传递性的，考虑直接建边。最后连出来的图由多个 DAG 组成。
存在博弈的限制，先手为了使字典序小，在放置原始数列的时候会让每个 DAG 上的点从小往大排列，对于后手，跑拓扑排序时用优先队列维护即可。
$\mathbb{AGC \ 010 \ F}$
连猜带做蒙过去一个做法，但是想了很久不知道怎么证明。
1 | inline bool dfs(int u, int fath) { |
比较直觉，如果当前点周围存在一个比他的石子数少并且会使先手失败的点，那么我先占据这个点，在操作后往这个会失败的点挪，如果后手不往回挪，他就输掉，如果他往回挪我就和他反复横跳，因为这时一定是他先耗完。非常对，等我把证明看懂了回来补一下。
$\mathbb{AGC \ 012 \ D}$
比较显然的是这个交换的性质是有传递性的。
但是这样只能有一个 $\Theta(n^2)$ 的做法。
往往这种时候一些比较容易的观察可以成为突破口。从不合法的状态入手看看？
颜色不同时，如果一种颜色中最小的球都无法移动，那么这种颜色就被 fix 了，可以直接去掉；颜色相同时，如果某个球和同色最小的球都无法交换，或者与其他颜色中最小的球无法交换，那么这个球就被 fix 了，可以直接去掉。
剩下的球都可以随便移动，组合数算算即可。
$\mathbb{AGC \ 012 \ C}$
构造题创思我。
先放前 $100$ 位为 $1 \to 100$，现在就变成构造后面一段使得后面一段的上升子序列数为 $n$。
然后考虑从大往小放数字，放在前面增加 $1$ 个，放在后面增加一倍，做一个二进制拆分就好了。
$\mathbb{AGC \ 013 \ D}$
这道题点出了数形结合的重要性。
虽然不画图也能做，但是画图能做到秒杀。
首先发现球的总数不变，一个显然的想法是定义 $dp_{i, j}$ 表示进行了 $i$ 次操作，现在手头有 $j$ 个白球。
转移非常 ez，分四种情况，按拿出的顺序为 白白，黑黑，白黑，黑白 分类。
问题在于会算重，如果把白球个数画成折线图大概是这样。
在上述的计算过程中，绿色蓝色和红色代表了三种不同的方案，然后这三条线对于的拿出球的序列是一致的，不难想到钦定白球在计算过程中降到 $0$，只统计这一部分的答案。
于是状态多一维表示白球的个数是否降至过 $0$，但是这样的转移不优美。记没有去重的方案数为 $f_{n, m}$，那么最后的答案是 $f_{n, m} - f_{n - 1, m}$。
非常奇妙，其实很好想，因为 $f_{n, m}$ 比 $f_{n - 1, m}$ 多出来的部分即是需要统计的经过了 $0$ 的折线条数，代码也很 ez。
$\mathbb{AGC \ 014 \ D}$
题面写得比较绕，意思是问最后能不能存在有白点使得没有黑点和它相连。
树上问题，从叶子开始思考？套路化地找出后手输掉的情况。存在 $u$ 与它相连的有两个叶子节点 $v_1, v_2$，先手先涂掉 $u$，后手必须去涂 $v_1$ 或者 $v_2$，否则先手可以在下一步就涂掉叶子获胜，而在此时后手涂掉了 $v_1$ 或 $v_2$，先手涂掉剩下的那个就可以获胜。这是先手必胜的情况，启示很大，我们直接从这样的情况开始思考，每次都删除叶节点和父节点，如果过程中出现了孤立的节点则先手获胜。
$\mathbb{AGC \ 015 \ D}$
手玩！
很多性质必须搞，硬搞，感受搞题时的那股劲。
首先干掉 $l, r$ 的相同的前缀，因为这一段不管怎么弄都不会变，现在我们最高的不同位在 $r$ 上是 $1$，在 $l$ 上是 $0$，然后引入一个数 $z$，形式是和 $l, r$ 有着相同的前缀，并且在 $l, r$ 最高位不同时该位为 $1$，后面的低位上全是 $0$。
于是把 $[l, r)$ 拆成 $[l, z)$ 和 $[z, r)$。
容易看出 $[l, r)$ 中的数互相计算的范围还是在 $[l, r)$ 中，考虑 $[z, r)$ 怎么算范围？
其实也比较容易看出来，找到 $r$ 中最高不同位下的第一个一，令 $p$ 为 $r$ 从最高不同位往下第一个一后面全部替换成一的值，这就是上限。跨区间的范围是 $[l | z, z | (z - 1)]$。
$\mathbb{AGC \ 015 \ E}$
脑动模拟一下这个过程，一个黑点往右移动然后碰到了一个白点，然后使它成为黑点，它也开始能染色其他点。这是一个连锁反应，似乎很像是 DAG 上拓扑排序，但是不一样，这道题只需要前面任何一个点是黑点就可以了。
首先假设我已经拿到了这张图，如果能做我就思考把这张图建出来，否则需要另择其道了。
想了一想，发现这张图很大？
对于一个点 $u$，考虑将能和它相遇的点按相遇的时间排序，如果 $u$ 能被染色，要么它自己本身是黑点，要么存在一个点 $v$ 在与 $u$ 相遇之前就是黑点。
于是我们把每对能相遇的点和相遇时间写成三元组 $(u, v, t)$，并按 $t$ 排序，这个感觉不是很好，把它放在坐标系里面，如果 $(x_1, v_1)$ 和 $(x_2, v_2)$ 能相遇，并且是 $x_2$ 超过 $x_1$ 的话，则有 $x_2 < x_1$, $v_2 > v_1$，我们需要按时间排序，那么 $t = \frac{x_1 - x_2}{v_2 - v_1}$，但是这样看起来不爽，令 $t' = \frac{x_1 - x_2}{v_1 - v_2}$，于是 $t$ 的正序转化为 $t'$ 的逆序，斜率越小越先相遇。这就变成了一张图，每个点和它左上角区域的点都有连边。所以有一个很厉害的性质，对于 $(x, v)$ 是黑点，它左上角、右下角、左下角的所有点都能黑。于是题目转化为了，给定一堆点，选择其中一些能够以覆盖左上角、右下角、左下角的方式覆盖所有点。
怎么弄呢，把右上角抠出来，只要选出来集合中的点的右上角区域的交越过了所有点的最右端和最高端即可。于是我们直接去计算不合法的方案数即可，去钦定最右点和最高点记为 $(x_1, y_1)$ 和 $(x_2, y_2)$，在 $(x_1, y_2)$ 范围内的点随便选，于是经典套路，排一维序，另一位用数据结构维护。
于是对 $x$ 轴排序，依次加入点，当前点一定是我们的最右点，对于每个不合法高度（在更右的点中比该高度还要高）维护该高度以内有多少点即可，需要离散化。
似乎是全网唯一解，因为我这个复杂度不太牛。
update: 哈哈，和洛谷第一篇题解前面的步骤一样的，但是他发现这个具有可二分性，于是上了 dp，我做的确实有点小丑了。
$\mathbb{AGC \ 016 \ D}$
看起来好困难。把其中一个变成整个序列的异或未免过于抽象。
让我来手玩一下，“把其中一个变成”换一下“把其中异或上其他所有值”。
假设第一次操作了 $x_2$ 变成 $\bigotimes_{i = 1}^{n} x_i$，第二次操作 $x_1$ 就应该是变成 $\bigotimes_{i = 1}^{n} x_i \bigotimes x_1 \bigotimes_{i = 3}^{n}x_i = x_2$。那如果我再操作一次 $x_2$ 呢？$\bigotimes_{i = 1}^{n} x_i \bigotimes x_2 \bigotimes_{i = 3}^{n}x_i = x_1$。
有点牛啊，我这样就可以在三步以内做到交换两个位置了，所以现在的问题是要使得 $A, B$ 两个序列元素相同。
直觉是我找到 $A$ 中和 $B$ 不相同的元素，那么一定有整个序列异或出来能补上一个没有的元素，于是反复操作即可，反之无解。
然后发现更牛逼的东西是我可以直接建一个虚的 $n + 1$ 号位，这一位就放最开始的异或和，所以现在的操作就变成了每次拿一个位置跟 $n + 1$ 换。
然后不是很会建这个图，题解的建图比较厉害。
从 $b_i$ 向 $a_i$ 连边，相同数值对于一个点，然后尝试从 $\bigotimes_{i = 1}^{n} x_i$ 开始遍历每一条边，如果图是一个包含 $all$ 的连通块，则一定可以找到一条欧拉路径（不一定是回路）覆盖所有边。如果图不连通或 $all$ 是孤立点，则答案就是边数再加上连通块数再减去 $1$ （如果 $all$ 是孤立点就不用减 $1$）。
$\mathbb{AGC \ 017 \ C}$
？？？你确定这个是蓝题？？？
总之这个性质很难。看了兔队的博客大概有点懂了。
在数轴每个位置上挂一根绳子，对于每个点 $A_i = k$，那就在 $k$ 这个位置上加 $1$ 的长度，挂完之后往左拉直，如果能覆盖完 $[0, n]$，那就没问题，否则需要改变的次数是没有被覆盖的位置个数。
$\mathbb{AGC \ 018 \ D}$
感觉和之前的一道题很像啊。这里指 $\mathbb{AGC \ 007 \ G}$。
不一样的点在于这里是哈密顿路径不需要回到起点，那么我是不是需要去找一条哈密顿回路然后删一条边？
直觉告诉我需要找最长的回路然后去掉最短的边。感觉很对？
思考无果，去看题解，发现结论猜对了，但是不会构造。
首先证明这个结论，以只有一个重心的情况为例。如果一条哈密顿回路，使得重心的每条邻边被经过的次数都取到了最大值，那么可以发现其他每条边被经过的次数也取到了最大值，也就是说这条哈密顿回路一定是最长的哈密顿回路。
那么，一条不是最长的哈密顿回路，至少有一条重心的邻边被经过的次数没有取到最大值，也就是说它至少比最长的哈密顿回路少了这条边的边权的两倍——那就比我们找到的哈密顿路径短了，再去掉一条边只会更短，所以我们找到的哈密顿路径一定是最优的。
然后这个证明里有一个《经典结论》：取重心外一点做起点，以重心做终点，存在遍历整个图的方案使得步步跨过重心。
那么唯一一条不会被统计进去的边就是起点到重心，于是计算这条边的最小值就好了。
$\mathbb{AGC \ 018 \ E}$
看起来非常组合数学，往容斥方面想想？
给了三个矩形，我猜复杂度和中间那个矩形的边长有关，应该是要去枚举。
那我就来枚举从 $X_3 \to X_4$ 这个范围。
尝试失败。做过这题的 ly 给我讲这题是要用组合意义，继续尝试。
我先想想如何确定唯一路径，直接枚举每个矩形里面的三个点显然不对，手玩一会发现具体在中间这个矩形里怎么走和在这个矩形里面走的步数有比较强联系，再搞一搞，发现我只需要知道进入这个矩形的入口和离开这个矩形的出口我就能计算了。
不能一对一枚举出入口，但是发现出入口有很强的对称性，考虑单独拉出来然后拼一下，首先不考虑出入口怎么拼，先去计算一下在知道出入口时到另外两个矩阵的方案数，这个玩意儿也是对称的，来画个图理解一下。
我现在在左下角，我要走到右上角蓝色区域，我的方案数是？
我来想想固定左下角 $(1, 1)$，右上角在矩形内 $(n, m)$ 我随便走的方案数，推推式子，枚举停下来的那个点。
$\mathbb{AGC \ 019 \ D}$
首先判是否有解，只要 $B$ 里面有一个 $1$，那不论怎样都能有解。
考虑构造最小方案，不难想到枚举 $A$ 中哪一位和 $B$ 对齐。
一个显然的观察，当操作 $1,2$ 的次数固定之后整个序列的答案就定下来了，于是只需要去考虑计算两个固定序列的答案即可。
继续观察，显然在最优方案中A的移动是分为两段：先一堆左移，再一堆右移（或者倒过来），因为我们把它看成B的左右移，那么可以修改的位置就是每次移动之后所有1的位置的并集，而重复到一种移动状态显然不会让集合元素增加。
拆开每个点，贡献是独立计算的，可以 $\Theta(n^2)$ 计算。
$\mathbb{AGC \ 019 \ C}$
被诈骗了一小会。
发现在喷泉处转弯会减小路径长度，于是把 $(x_1, y_1)$ 和 $(x_2, y_2)$ 之间的所有喷泉拎出来按 $x$ 排序然后求 LIS 就可以了。
$\mathbb{AGC \ 034 \ E}$
😓怎么还会有人把这题加强到 $n\le 1e6$ 并出到模拟赛啊？@C2022dongjie
不难想到枚举根，于是只要这些棋子在移动过程中能够内部消耗掉就好了。
有两种移动方式，一种是同时向 $lca$ 移动，一种是互相靠近，显然同时向 $lca$ 会更优秀。定义 $dis_u$ 表示 $u$ 子树内的所有棋子移动到当前遍历到的点需要的步数，$f_u$ 表示解决 $u$ 子树内所有棋子需要的步数。
注意到转移要分类讨论，定义 $son_u$ 表示 $u$ 子节点里 $dis$ 最大的子节点。当 $dis_{son_u} \le dis_u - dis_{son_u}$ 说明此时子树内可以全都消耗完，否则会剩下一些，按此转移即可。
以 $u$ 为根合法当且仅当 $\frac{dis_u}{2} = f_u$，取最小即可。
牛逼一点可以换根做到 $\Theta(n)$，但是写出来依托答辩。
$\mathbb{ARC \ 102 \ D}$
我真是太牛了，结论猜对了。
赛时大概手动模拟了 30+ 组数据，然后想到了逆序对，结合大样例猜出了正确解法。
思考这样一个过程，当可以对序列中连续三个数 $a, b, c$ 进行一次操作时，交换 $a, c$ 的结果是总的逆序对减少 $3$，而对于下标奇数，下标偶数的逆序对总和减少 $1$，这是一个必要条件。
发现这个是充分的，于是用这个做判据直接过掉。
$\mathbb{AGC \ 044 \ E}$
lydd 一下就给我讲懂了！😍
首先观察到当我走到了最大 $a_i$ 处一定会直接停下不继续走，因为没必要继续去消耗。
所以先重构一下这个序列，在最大的 $a_i$ 处断开，并在 $0$ 处放一个最大值。于是转换成在序列上面走。
写一下式子
发现这里有个 $b_i$ 非常不爽，考虑把它干掉。
定义 $c_i = 2(b_i + c_{i - 1}) - c_{i - 2}$，$f_i=E_i-c_i$，$g_i = a_i - c_i$。
得到 $f_i = \max\{\frac{f_{i - 1} + f_{i + 1}}{2}, g_i\}$。
这样直接凸包就可以维护了。
$\mathbb{AGC \ 021 \ B}$
非常降智。想到了中垂线，但是没想到去处理面积有限的情况。🤬
《众所周知》的是，一个有限的面积在无限的面积中选到的概率是 $0$。
所以求出凸包之后，凸包之间的点都可以忽略了。
凸包上的点用余弦反算角度然后看占比即可。