自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:36:17，当前版本为作者最后更新于2022-02-22 15:10:40，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P8135 [ICPC2020 WF] QC QC

两种人，$1$ 或 $0$。$1$ 只说真话，$0$ 对于询问相同的人的状态的回答相同。进行不超过 $12$ 轮询问，每轮询问形如向第 $i$ 个人问第 $p_i$ 个人的状态。需保证 $p_i$ 互不相同且 $i \neq p_i$。已知 $1$ 的人数严格大于 $0$ 的人数，试确定每个人的状态。

高妙构造题。

首先，我们只能从回答的结果反推出每个人的状态，且一定是让两个人相互询问。若不相互询问，我们难以确定任何一个人的状态，因此导致获得的信息完全无用。

考虑两个 $1$ 相互询问，回答必然是 $1, 1$。$1, 0$ 相互询问，回答 至少有一个 $0$。两个 $0$ 相互询问，回答可能是任何结果。容易发现若回答为 $1, 1$，则两个人的状态必然相同。

根据上述结论，我们考虑将所有人划分为若干 等价类，每个等价类内部所有人的状态均相同。一开始，每个人都是一个等价类。称为 一型等价类。

接下来，将所有一型等价类两两配对并互相询问。若询问结果不是 $1, 1$，说明它们当中必然 至少有一个 $0$。将这些 大小相同 的 等价类对 两两丢到一边，称为 二型等价类。

每次配对的过程中，可能有单独的一型等价类剩余。丢到一边，称为 三型等价类。

• 性质 1：任何时候任何一型等价类和三型等价类的大小均为 $2$ 的幂。
• 性质 2：不会出现大小相同的三型等价类。
• 性质 3：一型等价类和三型等价类的 $1$ 的个数严格大于 $0$ 的个数。这是因为二型等价类中 $0$ 不少于 $1$（关键性质）。

考虑配对的最终结果。显然，若一型等价类个数 $\geq 2$，则还可以继续配对。若一型等价类个数等于 $1$，则看做三型等价类。

因此，最终不剩余任何一型等价类。根据上述三条性质，容易发现必然存在三型等价类，且最大的的三型等价类必然为 $1$。若不然，根据小于 $2 ^ K$ 的不同的 $2$ 的幂之和最大为 $2 ^ K - 1$ 这一事实，与性质 3 矛盾。

现在我们用较少的步数确定了至少一个 $1$。只需要用这个 $1$ 去 倍增 确定所有二型等价类的类型即可。倍增的思想体现为每确定一个等价类的类型，若该等价类为 $1$，则每次能够确定的等价类的类型会增加该等价类的数量。

除非运气特别差，$12$ 次询问足以确定所有人的状态，因为最差结果是问出来的结果都是二型等价类，唯一的三型等价类大小为 $1$，且一开始用三型等价类问二型等价类的状态，得到的结果全是 $0$。这种情况在加入适当随机化之后出现概率可以视为 $0$。

#include <bits/stdc++.h>
using namespace std;

#define vint vector <int>
#define pb push_back

string query(vint p) {
	string res;
	cout << "test ";
	for(int it : p) cout << it << " ";
	cout << endl, cin >> res;
	return res;
}

const int N = 100 + 5;
int n;
vector <int> id[N], t1, t2, t3, fix;

void merge(vint &x, vint y) {for(int it : y) x.push_back(it);}
void solve() {
	cin >> n, t1.clear(), t2.clear(), t3.clear(), fix.clear();
	for(int i = 1; i <= n; i++) id[i].clear(), id[i].pb(i), t1.pb(i);
	while(t1.size()) {
		vector <int> p(n), nt1;
		for(int i = 0; i + 1 < t1.size(); i += 2) p[t1[i] - 1] = t1[i + 1], p[t1[i + 1] - 1] = t1[i];
		if(t1.size() & 1) t3.pb(t1.back());
		string res = query(p);
		for(int i = 0; i + 1 < t1.size(); i += 2) {
			int x = t1[i], y = t1[i + 1];
			if(res[x - 1] == '1' && res[y - 1] == '1') merge(id[x], id[y]), nt1.pb(x);
			else t2.pb(x), t2.pb(y);
		} t1 = nt1;
	}
	
	int bk = t3.back(), cur = 0;
	merge(fix, id[bk]), t3.pop_back();
	vector <int> p(n);
	for(int it : t3) p[id[bk][cur++] - 1] = it;
	string res = query(p); cur = 0;
	for(int it : t3) if(res[id[bk][cur++] - 1] == '1') merge(fix, id[it]);
	
	while(t2.size()) {
		int lim = min(fix.size(), t2.size());
		vector <int> p(n), nfix = fix;
		for(int i = 0; i < lim; i++) p[fix[i] - 1] = t2.back(), t2.pop_back();
		string res = query(p);
		for(int i = 0; i < lim; i++) if(res[fix[i] - 1] == '1') merge(nfix, id[p[fix[i] - 1]]);
		fix = nfix;
	}
	
	string ans;
	for(int i = 0; i < n; i++) ans += '0';
	for(int it : fix) ans[it - 1] = '1';
	cout << "answer " << ans << endl;
}

int main() {
	int T; cin >> T;
	while(T--) solve();
}

优化：注意到当且仅当最后一次合并时，将偶数个大小为 $2 ^ K$ 的一型等价类两两（组成一对）丢到二型等价类时，最大三型等价类较小，不大于 $2 ^ {K - 1}$，且三型等价类大小总和小于 $2 ^ K$。但注意到此时对于所有最大的二型等价类 对 $x, y$，必然恰有一个为 $1$，恰有一个为 $0$。因为若两个都为 $0$，则可以推出 $1$ 的个数不大于 $0$ 的个数，与题意矛盾。这样一来，每次我们必然能成功获得一个较大的为 $1$ 的等价类，优化显著。

一个乱搞方法（来源于 LOJ 第一篇提交）：考虑每次将两个等价类合并。对于所有不同的等价类对 $(x, y)$，按 $\max(sz_x, sz_y)$ 从大到小排序，并优先选择能操作的等价类对询问。在不超过 $8$ 次询问内能得到答案，此时大小最大的等价类即为 $1$，其它等价类均为 $0$（若为 $1$ 就被最大等价类合并了）。

启示：构造题当中 $2$ 的幂一般很有性质。