自动搬运

查看原文

来自洛谷，原作者为

	Larunatrecy 举杯邀明月，对影成三人。

搬运于2025-08-24 23:01:39，当前版本为作者最后更新于2024-11-15 11:58:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先随机若干次直到询问结果为 $0$ 或 $3$，显然只需要 $O(1)$ 次。

之后考虑在这三个点的基础上增量构造，每次加入一个点，维护已经加入的点之间的两两连边，设 $a_{i,j}$ 表示 $i,j$ 是否有边。

当加入一个点 $u$ 时，对于当前的完全图中的点 $i,j$，我们询问 $(i,j,u)$ 再减去 $a_{i,j}$ 就可以知道 $a_{i,u}+a_{j,u}$，我们把这些点 shuffle 之后两两分组，每组做上述操作，如果 $a_{i,u}+a_{j,u}=0$ 或 $2$，边的状态就确定了，否则这两条边恰好一个有一个没有。

我们把所有没有确定的二元组两两分组，也就是 $4$ 个一组然后两个二元组各问一个点，显然如果是 $0$ 或 $2$ 那么这四个就都确定，否则这四个形成了一个 $0,1$ 交错的链，然后再递归下去。

也就是说我们维护若干长度为 $2^k$ 的链，满足链上的点的连边状态是 $01$ 交错的，最后如果只剩一条链，我们再多花 $2$ 次操作就能问出来整条链。 因为我们 shuffle 过，所以可以认为询问结果是 $02$ 还是 $1$ 是等概率的，因此如果现在有 $n$ 条链，期望有 $n/4$ 条链会传到下一层，因此期望的询问次数是 $T(n)=n/2+T(n/4)$，差不多是 $\frac{2}{3}n$ 左右，当然每一层可能剩下一条链无法配对，我们还要再多花一次问出来。

最后的最坏询问次数大概在 $3370\sim 3380$ 左右。