特殊题杂碎

# [交互]翻牌游戏 **题意** ：你需要写两个程序 A,B。 首先交互库给出一个排列 $P_{1\sim n}$ ，A 程序可以查看整个排列，并做至多一次交换。 然后，交互库给出一个值 $k$ ，B 程序不知道排列，但可以每次询问排列的某个位置，需要在 $\lceil n/2\rceil$ 次询问内找出 $P_i=k$ 。 A,B 之间不得交流。 $n\leq 2\times10^5$ ------------ 首先考虑 B 程序的输入集合。显然，当输入集合为全体排列时，B 程序无法保证每次都完成任务，这才需要 A 程序的协助，把一些“不好”的排列转化为“好”的排列，即简化 B 程序的输入集合。 观察一些简单的策略，我们发现，仅针对“值”或“位置”之一的交换策略都是双射，无法简化输入集合。这提示我们要总和考虑“值”与“位置”。 一个排列，将“值”与“位置”结合，我们可以想到**置换**。 由置换又可以想到环，于是我们让 B 程序遍历 $k$ 所在的环（先询问 $P_k=k_2$ ，然后询问 $P_{k_2}$ ，不断重复直到完成任务），这样最坏情况下所需操作次数是 最大环的大小。 A 只需要负责把最大环拆成两个较小的环即可，不难发现这样拆之后最大环的大小 $\leq \lceil n/2\rceil$ 。 # [构造]模与匹配 **题意** ： 有一个左右各有 $n$ 个点的二分图，点编号为 $1\sim n$ 。 边 $(i,j)$ 的权值为 $i\bmod j$。 给出 $k$ ，要求选出一组匹配，使得权值恰为 $k$ ，或指出无解。 $n\leq 2\times10^5$ ------------ 首先考虑 $k$ 的范围。 注意到 $\mod i$ 的结果必 $\leq i-1$ ，一个显然的上界是 $\dfrac{n(n-1)}{2}$ 。只需让 $i$ 匹配 $i+1$ （特殊地，$n$ 匹配 $1$）即可取到。 让 $i$ 匹配 $i$ ， $0$ 也可以取到，这是下界。 我们有 $n!$ 种匹配方法而只用对付 $O(n^2)$ 个值，先猜想解是稠密的，即 $k=0\sim n(n-2)/2$ 都有解。 考虑选出一个集合（不含 $n$）使得和为 $n$ ，然后进行适当操作使得这个集合恰有贡献。 不难想到，对这个集合进行轮换，这样除了最大的元素外，其余元素都获得了一个比自己大的模数。 为了让最大的元素也有贡献，将 $n$ 加入集合来垫背。但是 $n$ 换到 $S$ 最左侧元素 $c$ 时可能产生额外贡献。 再将 $1$ 加入集合，这样 $n$ 模的是 $1$ ，就没有贡献了。 剩下的任务就是选一个含 $1$ 但不含 $n$ 的集合使得和为 $k$ 。 从大到小贪心，能选择选（保持余量 $\geq 1$ 因为最后要选 $1$）即可。