A 待补

B

枚举当前算哪种颜色以及 ban 掉哪种颜色。

以算颜色 \(1\) 为例：设 ban 掉颜色 \(2\) 形成的连通块是 \(p_1,p_2, \dots,p_x\)，ban 掉颜色 \(3\) 形成的连通块是 \(q_1,q_2,\dots,q_y\)。

建立一张二分图，左部 \(x\) 个点，右部 \(y\) 个点。对于一个颜色为 \(1\) 的点，将左部包含它的连向右部包含它的。于是问题转化成了给定一张二分图，问最少选多少条边，才能使得二分图中所有点都有边覆盖它。保证没有孤立点。

显然答案就是二分图点数减去最大匹配，构造方案也比较简单。

C 待补

某 CF 题（交互题 \(1\)）

题意：有两个 uint32_t 范围以内的整数 \(x,y\)，你可以选定两个非负整数 \(u,v\) 并询问 \(x \operatorname{xor} u\) 和 \(y \operatorname{xor} v\) 的大小关系。你需要在不超过 \(65\) 次询问内找到 \(x,y\)。

首先发现 \(65=2\times 32+1\)。先询问一次 \(x,y\) 的大小关系，如果 \(x=y\) 就很好做了，否则不妨设 \(x<y\)。

从高到低处理，对于每一位，询问 \(x\) 取反这一位与 \(y\) 的大小关系，以及 \(y\) 取反这一位与 \(x\) 的大小关系。显然有四种可能，分类讨论一下就行了。

交互题 \(2\)

题意：有 \(n\) 台机器，每台是好机器或坏机器，每次可以询问两台机器让它们互相检查，好机器一定会说真话，坏机器有可能说假话，要用不超过 \(2n\) 次询问问出每台机器的好坏。保证好机器个数大于坏机器个数。

考虑一个经典问题：给你 \(n\) 个数，定义众数为出现次数超过一半的数，只允许把所有数扫一遍，\(\mathcal O(1)\) 内存，求众数。

维护两个变量，记录当前众数以及出现次数。如果新扫描到的数等于当前众数，次数加一；如果不等于就减一。当次数为 \(0\) 时，把当前众数置为新的数。

这是因为众数出现次数一定 \(> \dfrac{n}{2}\)，因此让它和其他数抵消就行了。

回到这道题：可以发现如果返回的两个结果不全是“好”，那么这两台机器里一定有一台坏机器，于是让它们抵消即可。

最后，一定剩下一些好机器，选其中一台 check 其他机器即可。

交互题 \(3\)

题意：有一张竞赛图，每次可以询问一条边的方向，要找到一条包含 \(n\) 个点的链。

考虑对 \(n\) 归纳，当 \(n=1\) 时显然是对的。

否则，假设已经找到了一条长为 \((n-1)\) 的链，如果新点到链尾有边，直接加到链尾即可；如果链头到新点右边，那么插入到链头前面；否则，一定可以在中间找到形如 \(x\to n \to (x+1)\) 的路径，其中 \(x\) 是链上的某个点，\(x+1\) 是链上 \(x\) 的后继。具体地，每次询问 \(n\) 与当前二分的中点 \(mid\) 的边方向，如果指向 \(n\) 就递归到 \([l,mid]\)，如果指向 \(mid\) 就递归到 \([mid,r]\)。

感觉这个二分好像还有点细节。。。

交互题 \(4\)

题意：有一棵二叉树，其节点编号为中序遍历的 dfn。你每次可以询问两个点 \(u,v\)，并得知 \(u\) 是否是 \(v\) 的祖先节点。用不超过 \(2n\) 次询问还原整棵树。

考虑类似笛卡尔树建树的过程：按点的编号从小到大确定点的位置，每次这个点都一定在树的右链上。于是考虑维护从根节点到最右节点的链，每次询问栈顶是否是新加入的点的祖先，如果不是就弹出。每次在新弹出的点与上次被弹出的点之间连向右的边，新加入的点确定位置后向最后一个被弹出的点连向左的边。所有操作完成后在栈中元素之间依次连向右的边。

如果不理解可以画棵二叉树模拟一下。

通信题 \(1\)

题意：程序 A 输入一棵 \(n\) 个点的无标号有根树，规定每个点的儿子顺序，输出一个 \(128\) 位 \(01\) 串。程序 B 需要根据 \(01\) 串还原树。\(n\le 70\)。

可以发现 \(70\) 个点的无标号有根树与卡塔兰数 \(Cat_{69}\) 一一对应，因为可以把进入某个子树看作左括号，出某个子树看作右括号。

\(Cat_{69}\) 正好小于 \(2^{128}\)，于是用 dp 求出字典序第 \(k\) 大的合法括号序列是什么，以及某个括号序列是第几大的就行了。

通信题 \(2\)

题意：程序 A 输入一个 \(10^{18}\) 范围内的非负整数，输出一棵点数不超过 \(100\) 的无标号无根树，程序 B 输入这棵树，输出原数。

考虑怎么样让这棵树表示一个数：我们组成一条长为 \(20\) 的链，并用一些点标志这条链的头尾。再在链上的每个点上挂 \(0\sim 3\) 个点，这样至多 \(4\) 个点就可以组成 \(3\) 个 bit。于是这样能表示的数就是 \(0\sim 8^{20}-1\)，大于 \(10^{18}\)。

通信题 \(3\)

题意：程序 A 输入一张 \(n\) 个点的有标号的无向简单图，输出一张 \((n+12)\) 个点的无标号无向简单图。程序 B 输入无标号图，还原有标号图。\(n\le 1000\)。

多出来 \(12\) 个点是干啥的？我们把其中的 \(10\) 个点向原图中的点连边，第 \(i\) 个点向所有标号二进制第 \(i\) 位为 \(1\) 的点连边。剩下的两个点中，一个点向原图中的所有点以及那 \(10\) 个点连边，剩下那个没被连边的点用来向那 \(10\) 个点连边，以标识那 \(10\) 个点。

可以发现 \(n\) 略小于 \(1024\)，所以表示最高位的点的度数一定小于表示最低位的点的度数。于是就可以区分出高低位了。

通信题 \(4\) 待补

题意：程序 A 和 B 各会输入一个 \({1,2,\dots,n}\) 的子集。程序 A 可以向交互库输出一个 \(1\dots n\) 的排列，然后向程序 B 提供两个 bit 的信息。程序 B 也可以向交互库输出一个 \(1\dots n\) 的排列，此时交互库会向程序 B 返回两个排列复合起来是不是只有一个轮换（只能询问一次）。最后程序 B 需要判断：二者的集合有没有公共元素。

通信题 \(5\)（IOI2020 网络站点）

题意：程序 A 输入一棵树，并将这棵树重标号。程序 B 需要处理多次询问，每次以新的编号给定树上的两个点 \(s,t\) 以及与 \(s\) 相邻的点的编号，B 需要回答从 \(s\) 走到 \(t\) 的路径上包含与 \(s\) 相邻的哪个点。重标号必须是 \(\mathbf{1\sim n}\) 不重不漏。

部分分：重标号只需要在 \(1\sim n^2\) 内不重复即可。

先考虑部分分：可以用每个点的标号记录它的欧拉序 \((st_u,ed_u)\)。这样我们就可以根据 \(t\) 的编号知道它在 \(s\) 的哪个子树内，或者需要从 \(s\) 往上走。

正解：dfs 的过程中，对于深度为奇数的点，入栈时给它赋一个 dfn；否则出栈是给它赋一个 dfn。这样画画图就可以发现能确定 \(t\) 在 \(s\) 的哪个子树内了。