倒序开题记录.md
部分做题记录见 AGC 板刷记录 Part。
AT_arc103_d - Distance Sums
容易发现 $D_i$ 最小的 $i$ 一定是树的重心，且 $D_i$ 最大的 $i$ 一定是树的某个叶子结点。不妨以重心为根进行考虑。
倘若按照 $D_i$ 从小往大考虑，即设 $p_i$ 表示 $D$ 值第 $i$ 小的节点编号，钦定 $p_1$ 为根，$p_2$ 的父节点为 $p_1$ 后，不太好确定 $p_3$ 的父亲是 $p_1$ 还是 $p_2$。那么不妨按照 $D_i$ 从大往小考虑，每次找到还未钦定父亲节点的 $D$ 值最大的节点 $p$，由于钦定了重心为根，所以 $p$ 的子树大小已经由 $D_i > D_p$ 的点确定。此时考虑 $p$ 的父亲节点对应的 $D$ 值，显然 $D_{fa_p} = D_p + 2siz_p - n$，直接找出任意一个合法的 $fa_p$ 连边即可。
最后，由于上述过程中只确定了 $D_i$ 与 $D_{fa_i}$ 的相对大小，而绝对大小仍然未知，因此仍需跑一遍 DFS 计算出重心的 $D$ 值，判断构造是否合法。
[*]AT_arc103_b - Robot Arms
首先容易证明，在题目给定的限制下，若最终能够走到 $(x,y)$，则对于所有的 $(x',y')$ 使得 $(x+y)$ 与 $(x'+y')$ 的奇偶性不同，$(x',y')$ 一定走不到。
值域 $10^9$ 而要求构造出的集合大小 $\le 40$，看起来比较像是 $\log$ 级别的东西，考虑使用 $2$ 的整次幂进行构造。具体而言，先在坐标系中找到集合 $\{1,2\}$ 能够表示出的点，如下表所示，# 代表能够走到，+ 表示坐标原点：
| |
不难发现能够到达的位置是一个以坐标原点为中心的菱形中，$(x+y)$ 为奇数的位置。那么显然 $\{1,2,2^2,\cdots,2^{k}\}$ 就能表示出目标值域范围内的所有 $(x+y)$ 为奇数的位置。特别地，若目标位置的 $(x+y)$ 均为偶数，则可以使用一个额外的长度作为偏移量。
现在考虑如何根据上述集合构造出具体方案。将坐标轴旋转 $45\degree$，$(x,y)$ 变为 $(x+y,x-y)$，LRUD 对应的操作变为 $(+d,+d),(+d,-d),(-d,+d),(-d,-d)$ 中任取一个，此时便可以将 $x$ 坐标与 $y$ 坐标分开考虑，那么问题就转化为构造序列 $a$ 使得 $a_i \in \{-1,1\}$ 且 $\sum_{i=0}^{k} a_i \times 2^{i} = x$。
$x$ 为负数的情况容易转化为 $x$ 为正数，那么考虑 $x$ 非负的情况，先直接令 $a_i$ 为 $x$ 的二进制表示中第 $i$ 位的值，再考虑从小到大对 $a_i=0$ 的位置进行调整。具体而言，若 $a_i=0$ 且 $a_{i-1}=1$，那么调整使得 $a_i=1, a_{i-1}=-1$ 即可，$a_i=0$ 且 $a_{i-1}=-1$ 的情况同理。
[**]AT_arc102_d - Revenge of BBuBBBlesort!
先找必要条件，一次操作必然使得逆序对数 $-3$，所以逆序对数需要为 $3$ 的倍数。
其次，操作后奇数位置的数仍在奇数位置，偶数位置同理。因此需要满足 $p_i - i \equiv 0 \pmod{2}$。
同时，每次操作还会使得要么奇数位置的逆序对数 $-1$，要么偶数位置的逆序对数 $-1$，所以设原排列中奇数、偶数和完整排列中的逆序对数分别为 $s_0,s_1,s$，则需要满足 $s=3\times(s_0+s_1)$。
然后发现上述三个条件与起来就是充分的了，具体证明可以问 tzc_wk。
[*]AT_arc101_d - Robots and Exits
容易知道每个机器人从哪个出口消失，仅与其初始位置到其左、右遇到的第一个出口的距离有关，设这两个距离分别为 $L_i,R_i$，并去掉左边或右边没有出口的机器人（显然这部分机器人不会对答案造成影响）。
将 $(L_i,R_i)$ 看成坐标上的点，那么每次移动就转化为从 $(0,0)$ 开始走，每个时刻选择 $x,y$ 坐标中的一个 $+1$，若先走到 $x=L_i$ 则相当于机器人 $i$ 走左边出口，先走到 $y=R_i$ 则相当于机器人 $i$ 走右边出口。
设计 dp 状态，$dp_i$ 表示以 $(L_i,R_i)$ 为结尾的路线条数，显然有转移 $dp_i = 1+\sum_{L_j 直接 dp 似乎只能做到 $\mathcal O(n^3)$，而且不太容易优化。 考虑容斥，$F(S)$ 表示至少有 $S$ 中的边没有被覆盖的方案数，容易知道将 $S$ 中的边断开后整棵树被分成了若干连通块，每个连通块中的贡献独立。答案即为 $\sum_{S \subseteq E} (-1)^{|S|}F(S)$。 虽不能对每个 $S$ 都求出其对应 $F(S)$，但可以在树形 dp 的过程中计算容斥系数。具体而言，$dp_{u,i}$ 表示 $u$ 的子树中，$u$ 所在连通块大小为 $i$。转移时枚举儿子，考虑 $(u,v)$ 这条边是否强制钦定不覆盖即可，$\mathcal O(n^2)$。 考虑先将题目读对，所求答案不是方案数，而是「出现次数之和」！然后考虑容斥，用「序列 $A$ 的出现次数之和」减去「不存在连续 $K$ 个不同颜色段时序列 $A$ 的出现次数之和」得到答案。 「序列 $A$ 的出现次数之和」显然是 $(N-M+1) \times K^{N-M}$。容斥掉的部分则分为三种情况讨论。 不难发现可以使用多项式哈希来判断两个操作后的数组是否相等。 具体而言，考虑 $suf_i$ 表示操作后缀 $i\cdots n$ 所代表的数组的哈希值，在操作序列最前端添加 计算答案的过程中，只需要使用一个 先依次删去黑色叶子，剩下来的每个结点都必然被经过至少一次。假设新树有 $n$ 个结点。 考虑先构造一个回路再删去一条路径，回路必然需要进行 $2(n-1)$ 次移动，接下来需要将所有翻转后仍为白色的点翻转（这部分称为额外的翻转）。下文中的「黑/白」均表示仅考虑移动操作时每个点的颜色。 考虑如何删去一条路径。假设该条路径上有 $W$ 个白色结点和 $B$ 个黑色结点，首先移动次数会减少 $(W+B-1)$ 次。其次对于每个白色结点，额外的翻转次数减少 $1$，而黑色结点则增加 $1$，该路径对答案的贡献为 $1-2W$。那么设白点权值为 $2$，黑点权值为 $0$，dp 求出树上带权直径即可。 「对于每一个 $p_i$，找到最大的 $j$ 使得 $p_j < p_i$，然后在 $i,j$ 间连边。」 显然每个 $p_i$ 只会连向比它更小的 $p_j$，那么不妨钦定 $p_i=1$ 的位置为根，每个结点的父亲权值一定小于自己。 令 $q$ 表示 $p$ 的逆置换。考虑按照 $q_1,q_2,\cdots,q_n$ 的顺序依次加入每个点，不难发现 $q_i$ 的父亲一定是 $\max_{1\le j\lt i}q_j$，即前缀 $i-1$ 的最大值。进一步地，由于前缀最大值只会递增，所以对于每个结点 $q_i$，其最多只有一个儿子的度数 $>1$，否则无法构造出一个合理的加入结点的顺序。 简单想象一下，整棵树一定构成了一个类似「毛毛虫」的形状，即存在一条链上挂着一些大小为 $1$ 的「触角」，我们称这条链为「躯干」，而「躯干」显然就是树的直径，容易两遍 bfs 求出。 考虑如何构造字典序最小的方案。不妨枚举以「躯干」的哪个端点为根，当加入躯干上的点 $u$ 时，$u$ 的兄弟结点必然已经被加入过了。在加入 $u$ 之前，前缀最大值为 $fa_u$，加入之后则变成了 $u$，因而列出不等式 $p_v < p_{fa_u} < p_u$，其中 $v$ 是 $u$ 的兄弟。字典序最小的答案很容易便能构造出。 最后修改于 2025-06-30 Git 版本:
eedba93AT_arc101_c - Ribbons on Tree
[**]AT_arc100_d - Colorful Sequences
AT_arc099_d - Eating Symbols Hard
<>+- 中的任何一个字母是容易维护的。而考虑计算出子段 $[i,j)$ 所代表的数组的哈希值，即 $suf_i - suf_j \times seed^{d_i - d_j}$，其中 $seed^{d_i-d_j}$ 表示 $[i,j)$ 中的 <> 操作给指针的偏移量，将 < 看作 $-1$，> 看作 $+1$ 后，容易通过后缀和求出。unordered_map 统计哈希值对应的后缀个数即可。复杂度线性。[*]AT_arc098_f - Donation
[**]AT_arc097_d - Monochrome Cat
[**]AT_arc096_d - Sweet Alchemy
[**]AT_arc096_c - Everything on It
AT_arc095_d - Permutation Tree