自动搬运

查看原文

来自洛谷，原作者为

	xht 好想爱这个世界啊

搬运于2025-08-24 22:27:42，当前版本为作者最后更新于2023-04-18 22:29:07，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

对于两个点 $x,y$，如果我们按照如下方式建图：

• 若 $x,y$ 颜色相同，则 $x,y$ 之间连一条无向边，记为 $x \leftrightarrow y$。
• 若 $x$ 喜欢 $y$，则连一条 $x \to y$ 的有向边。

先不考虑询问的限制次数。

如果我们询问所有的点对 $(x,y)$，返回的结果要么为 $1$，要么为 $2$。

如果为 $1$，则只有以下三种情况：

1. $x,y$ 颜色相同。
2. $x$ 喜欢 $y$，但 $y$ 不喜欢 $x$。
3. $y$ 喜欢 $x$，但 $x$ 不喜欢 $y$。

容易发现，当答案为 $1$ 时，$x,y$ 之间一定有边；答案为 $2$ 时，$x,y$ 之间一定无边，除了 $x \to y$ 且 $y \to x$ 的情况。

进一步可以发现，每个点的度数都是 $3$，但是询问出来的度数可能为 $1$。

若询问出来 $x$ 的度数为 $1$，则说明存在一个度数同样为 $1$ 的点 $y$，符合 $x \to y$ 且 $y \to x$ 的情况，而询问出来的那条边，则是一条无向边 $x \leftrightarrow z$，这意味着 $x,z$ 的颜色相同。

若询问出来 $x$ 的度数为 $3$，设这 $3$ 个点为 $y,z,w$。考虑到如果我们询问 $(x,y,z),(x,y,w),(x,z,w)$，其中有且仅有一组的答案为 $1$，其它两组的答案都为 $2$。

不妨设为 $1$ 的询问为 $(x,y,z)$，则只可能是 $x \leftrightarrow y$ 且 $z \to x$，或者 $x \leftrightarrow z$ 且 $y \to x$。

尽管我们无法得知是哪种，但是我们可以以此确定 $x \to w$ 这条边。

通过这种方法，我们可以确定所有的有向边，那么剩下的边就是无向边，即颜色相同的点。

这个做法的询问次数为 $\mathcal O(n^2)$ 的，瓶颈在询问两两点对上。

考虑优化这个过程。

我们可以通过 $\mathcal O(n)$ 次询问求出一个极大独立集。

方法为，从 $1 \sim 2n$ 依次尝试加入当前的极大独立集 $S$，如果询问 $(S,x)$ 的答案为 $|S| + 1$，则说明可以加入，否则说明有边。

找到极大独立集之后，对于独立集之外的点，在独立集中二分找到所有边。

此时还剩下独立集之外的点中的边没有找到，那么重复上述过程，直到所有剩下的点都是一个独立集。

由于每个点的度数最多为 $3$，因此每次独立集的大小 $\ge$ 总点数的 $\frac 14$。这意味着每次我们可以将点的规模缩小到原来的 $\frac 34$，那么一共只需要最多重复 $\mathcal O(\log n)$ 次就能找到所有边，因此求最大独立集部分的询问次数为 $\mathcal O(n \log n)$。

又由于每找到一条边需要一次二分，而边数是 $\mathcal O(n)$ 的，所以二分部分也只有 $\mathcal O(n \log n)$ 次询问。

这样我们就可以用 $\mathcal O(n \log n)$ 次询问找到所有边，为了减小常数防止被卡，可以先对点进行 random_shuffle。

inline int get(int x, vi p) {
	int l = 0, r = p.size() - 1;
	while (l < r) {
		int mid = (l + r) >> 1;
		vi q(1, x);
		for (int i = l; i <= mid; i++) q.pb(p[i]);
		if (Query(q) != (int)q.size()) r = mid;
		else l = mid + 1;
	}
	return p[l];
}

inline int ask(int x, int y, int z) {
	vi p(3);
	p[0] = x, p[1] = y, p[2] = z;
	return Query(p);
}

void Solve(int n) {
	srand(time(0));
	vi A, B;
	for (int i = 1; i <= (n << 1); i++) B.pb(i);
	random_shuffle(B.begin(), B.end());
	vector<vi> e(n << 1 | 1);
	while (B.size()) {
		vi S = B, v(n << 1 | 1);
		A.clear(), B.clear();
		for (int x : S) {
			A.pb(x);
			if (Query(A) != (int)A.size()) A.pop_back(), B.pb(x);
			else v[x] = 1;
		}
		for (int i : B) {
			vi p = A;
			p.pb(i);
			do {
				p.pop_back();
				int k = get(i, p);
				e[k].pb(i), e[i].pb(k);
				for (int &x : p)
					if (x == k) swap(x, p.back());
				p.pop_back();
				p.pb(i);
			} while (Query(p) != (int)p.size());
		}
	}
	vi v(n << 1 | 1);
	vector<map<int, bool>> f(n << 1 | 1);
	for (int x = 1; x <= (n << 1); x++)
		if (e[x].size() == 3u) {
			int y = e[x][0], z = e[x][1], w = e[x][2];
			if (ask(x, y, w) == 1) swap(z, w);
			else if (ask(x, z, w) == 1) swap(y, w);
			f[x][w] = f[w][x] = 1;
		}
	for (int x = 1; x <= (n << 1); x++)
		if (!v[x])
			for (int y : e[x])
				if (!f[x][y]) v[x] = v[y] = 1, Answer(x, y);
}