EZEC R13 中文私货（有题解）

# EZEC R13 Chinese Editorial ## Two Permutations 如果 $a+b+2\leq n$，我们可以将中间 $(n-a-b)$ 个元素循环位移一次。 如果 $a+b+1\geq n$，可以证明两个排列是相等的，因此当且仅当 $n=a=b$ 有解。  外星怪马（pixiv id: 89647675） ## Elimination of a Ring 首先，如果给定的环形如 $[a,b,a,b,a,b,\cdots,a,b]$，答案为 $\frac{n}{2}+1$。 然后，我们可以通过归纳证明只要环有三种元素，答案一定为 $n$。 - 如果存在一种元素出现次数 $>1$ 且它两边的数不相同，只需要删去这个数即可。 - 如果存在一种元素出现次数 $=1$，我们只需要删去这个数右边的数即可。 不难发现只要环有三种元素，上述两种情况必定至少满足一种。  重炮（pixiv id: 88790337） ## Set Construction - 做法 A（时间复杂度 $O(\frac{n^3}{w})$） 拓扑排序：初始时第 $i$ 个集合只包含第 $i$ 个点，暴力转移集合之间的关系即可。 - 做法 B（时间复杂度 $O(n^2)$） 转置输入的矩阵并输出。 不难发现所有约束一定形成树状关系，考虑一个元素的贡献即可。  乌拉拉（pixiv id: 89343331） ## Carry Bit 我们先列出不进位加法后的值，即每一位的值可以是 $0,1,2$。 考虑一个极长的进位链一定形如 $0,x_1,x_2,\cdots,x_n,2$，因此如果相邻两位一个进位，另一个不进，那么较高的位只有 $1$ 种方案。 枚举进位的段数即可。  二锅头（pixiv id: 94244450） ## Make It Connected 首先，如果图已经联通，答案为 $0$。 不然，如果图存在一个点度数为 $0$ 或存在一个连通块不是完全图，答案为 $1$。 不然，如果图有超过 $3$ 个连通块，答案为 $2$。 不然，答案为较小连通块的大小。 对于第二步，即找到一个非完全图连通块中的合法操作点有很多方法，这里列举几种： - 方法 A 找到一个度数不是 $S-1$ 的非割点，其中 $S$ 为连通块大小。 - 方法 B 找到所有点中度数最小的点。  可爱铃鹿（pixiv id: 102293234） ## Anti-median 考虑先找出合法排列的充要条件再计数。 首先考虑 $n=3$，即 $a_2$ 要么是最大值，要么是最小值。 然后考虑 $n=5$，假设所有相邻的奇数位大于偶数位，则奇偶数位置分别需要满足单峰和单谷。通过一些归纳可以证明，这个条件已经是充分的了。 然后我们考虑从小到大填数，尝试模拟一个合法排列值域变大的过程：  不难发现我们从 $1$ 所在的点开始，每次扩展都是向两侧扩展 $2$ 的长度，碰到边缘就反弹。 特别地，我们还需要保证任意时刻扩展的两个端点满足 $l\leq r$。 因此我们可以暴力地记 $f_{l,r}$ 为扩展到区间 $[l,r]$ 的方案数，时间复杂度 $O(n^2)$。 接下来是究极人类智慧：我们觉得 $l\leq r$ 这个条件和反弹加在一起不太好处理，我们直接将序列翻转后分别插入头部和尾部，这样就可以解决”反弹“的限制。 然后我们突然发现，此时 $l\leq r$ 的限制居然等价于 $2n\leq l+r\leq 4n-2$！ 考虑一个非 $-1$ 的位置，显然在放到它的轮次，可能的区间只有 $\leq 6$ 个，因此如果存在至少一个 $-1$，我们暴力地对于每层进行转移，时间复杂度是正确的。 尝试形式化地描述上述的“暴力转移”，即初始在 $(0,y)$，要走到 $(x,y)$，不能碰到 $y=y_0$ 和 $y=y_1$，每次可以从 $(a,b)$ 走到 $(a+1,b\pm 1)$。 这是一个经典的反射容斥问题，可以在 $O(\frac{x}{y_1-y_0})$ 的时间复杂度内解决，由于此处 $y_1-y_0$ 显然比 $x$ 大，因此我们认为它可以在 $O(1)$ 的时间复杂度内解决。 最后考虑全部为 $-1$ 的情况，我们引用一条我自己说的话：能写 $O(\text{poly}(n))$ dp，输入一个数，输出一个数的所有题都能整式递推，于是套一个整式递推，时间复杂度 $O(n)$。  帝宝麦昆贴贴（pixiv id: 92336524） ## Centroid Guess 假设我们现在确定了树的重心在 $u$ 到 $v$ 的链上，考虑如何找到它。 设 $u$ 到 $v$ 的链经过的所有点依次为 $c_1,c_2,\dots,c_k$，我们把由链上一点 $c_i$ 出发不经过链上其他点可到达的点的集合称为 $A_i$，显然 $A_1,A_2,\dots,A_k$ 这 $k$ 个集合不重不漏地包含了树上所有的 $n$ 个点。 设集合 $A_i$ 的大小为 $s_i$，链上显然存在恰好一个点 $c_x$ 满足 $\max\{\sum\limits_{i=1}^{x-1}s_i,\sum\limits_{i=x+1}^ks_i\}\le\lfloor\frac{n}{2}\rfloor$，注意到不满足该条件的链上的点一定不是重心，而目前已经确定重心在链上，所以此时 $c_x$ 就是树的重心。 接下来考虑通过 $2n$ 次询问得到树上每个点所属集合，进而求出 $s$。对于一个点 $x$，询问 $dis_{u,x}$ 和 $dis_{v,x}$，容易发现对于同个集合中的点，$dis_{u,x}-dis_{v,x}$ 的值全相同，若 $dis_{u,x}-dis_{v,x}=t_1$，$dis_{u,v}=t_2$，则 $x\in A_{(t_1+t_2)/2+1}$。于是我们求出了树上每个点所属集合，也求出了 $s$，找到了重心。这最多需要消耗 $7.5\cdot10^4\times2=1.5\cdot10^5$ 次询问。 现在问题是找到点对 $u,v$，使得树的重心在 $u$ 到 $v$ 的链上。 我们取一个常数 $M$，使得 $\frac{M(M-1)}{2}\le5\cdot10^4$，然后在树上随机选取 $M$ 个点，并询问两两间距离，这需要消耗 $\frac{M(M-1)}{2}\le5\cdot10^4$ 次询问。 设这 $M$ 个点分别为 $p_1,p_2,\dots,p_M$，我们建出包含 LCA 的以 $p_1$ 为根的虚树。容易发现 $dis_{x,y}+dis_{y,z}=dis_{x,z}$，当且仅当 $y$ 在 $x$ 到 $z$ 的链上。对于一个点 $p_x$，我们可以找到 $p_1$ 到 $p_x$ 的链上的所有点，找到这些点中除自己外与 $p_x$ 最近的点与 $p_x$ 连边，它就是点集中 $p_x$ 的深度最大的祖先。 此时我们求出了不包含 LCA 的以 $p_1$ 为根的虚树，接下来我们将添加 LCA 至虚树中。设包含 LCA 的虚树为 $T$。 我们从 $p_1$ 开始 dfs，设当前节点为 $u$，显然 $u$ 的儿子之间不构成祖先后代关系，我们枚举 $u$ 的儿子 $v$，若一个点 $x$ 满足 $u$ 不在 $x$ 到 $v$ 的链上，则在 $T$ 中 $v$ 与 $x$ 在 $u$ 的同一个子树内的，找到所有在 $T$ 中与 $v$ 在 $u$ 的同一个子树内的点后，容易计算它们 LCA 的深度，并处理出 LCA 到当前虚树所有点的距离，接着断开原来的边，从 LCA 向 $T$ 中与 $v$ 在 $u$ 的同一个子树内的点连边，然后从 $u$ 向 LCA 连边，然后对 $u$ 重复上述过程，直到 $u$ 的儿子中任意两个点都不在 $T$ 中 $u$ 的同一个子树内，然后向目前 $u$ 的儿子 dfs。不难发现，完成 dfs 后，我们就得到了完整的虚树。 仅仅对于原始随机到的 $M$ 个点，我们认为它的点权是 $1$，虚树中其他点点权均为 $0$，我们找到虚树的带权重心（有多个时可任意取其中一个），并以它作为虚树的根，选取它最大的两个子树进行 dfs，每次都走最大的子树，这样得到两个叶子，称其为 $u,v$，原树的重心有极高的几率在 $u$ 到 $v$ 的链上。然后套用之前的算法即可求得重心。两部分总询问次数相加不超过 $2\cdot10^5$ 正确性证明： 虚树重心最大的两个子树大小之和至少为 $2/3$ 的虚树大小。 若原树的重心不在 $u$ 到 $v$ 的链上，那么设虚树的重心在原树重心的子树 $E$ 中，$E$ 中至少包含了 $2/3$ 的我们随机出来的节点，又由于 $E$ 的大小不超过 $\lfloor\frac{n}{2}\rfloor$，所以随机一个点不在 $E$ 中的概率至少为 $\frac{1}{2}$，随机 $M$ 个点，至多有 $1/3$ 的不在 $E$ 中，$E$ 才能包含 $2/3$ 的我们随机出来的节点，也就是，随机 $M$ 个点，每个点超过 $1/2$ 的概率不合法，至多只能有 $1/3$ 的点不合法。只有这样才会使得该算法出错。这个概率不高于 $\sum\limits_{i=0}^{M/3}C_M^i/2^M$，取 $M=316$，约为 $6\cdot10^{-10}$。  寄！（pixiv id: 90978873）