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 个点,暴力转移集合之间的关系即可。
转置输入的矩阵并输出。
不难发现所有约束一定形成树状关系,考虑一个元素的贡献即可。
乌拉拉(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。
不然,答案为较小连通块的大小。
对于第二步,即找到一个非完全图连通块中的合法操作点有很多方法,这里列举几种:
找到一个度数不是 S-1 的非割点,其中 S 为连通块大小。
找到所有点中度数最小的点。
可爱铃鹿(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)