专栏文章

题解：CF1746E1 Joking (Easy Version)

FFederico2903
CF1746E1题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipz047s
此快照首次捕获于
2025/12/03 20:15
3 个月前
此快照最后确认于
2025/12/03 20:15
3 个月前
查看原文

思路

考虑怎么应对交互库的说谎，即什么情况一定是确定的：
设现在的答案集合为 SS，我们将其四等分为 S1,S2,S3,S4S_1, S_2, S_3, S_4。
我们询问一次 S1∪S2S_1 \cup S_2，再问一次 S1∪S3S_1 \cup S_3。
考虑对于交互库的每种回答处理，例如回答 NO 和 NO：
注意到交互库在这两个询问中至多只能说一次谎，那么也就是说不存在 YES 和 YES 这种情况，即答案不存在于 (S1∪S2)∩(S1∪S3)=S1(S_1 \cup S_2) \cap (S_1 \cup S_3) = S_1 中。
其他几种情况是类似的，每次都能使集合大小缩小为原来的 34\frac{3}{4}。
但是注意到只剩下三个的时候，这个方法失效了，因为存在一种回答方案使排除的集合为空集。
设最后的集合为 {a,b,c}\{a, b, c\}，那么我们先询问一次 aa。
如果我们得到了否定的回答，则再问一次 {a}\{a\}，如果还是否定的回答，则能确定答案在 {b,c}\{b, c\} 中。
如果不满足上述情况，那么我们现在一定是最后一次得到了一个交互库对答案在 {a}\{a\} 中的肯定回答，我们再问一次 {b}\{b\}，如果得到了肯定回答，则答案必定不是 cc（和上面的思路类似），否则答案必定不是 bb。
剩下两个数直接回答就行了。

AC 代码

CPP
int query(vector <int> res) {
	cout << "? " << res.size() << " ";
	for (auto v : res) cout << v << " ";
	cout << endl;
	string str;
	cin >> str;
	if (str == "YES") return 1;
	else return 0;
}

void answer(int res) {
	cout << "! " << res << endl;
	string str;
	cin >> str;
	if (str == ":)") exit(0);
}

signed main() {
	cin >> n;
	if (n == 1) answer(1);
	if (n == 2) answer(1), answer(2);
	vector <pii> res;
	rep (i, 1, n) res.emplace_back(i, 0);
	while (res.size() > 3) {
		vector <int> res1, res2;
		rep (i, 0, (int) res.size() - 1) {
			if ((i & 3) == 0) res1.push_back(res[i].ec), res2.push_back(res[i].ec);
			if ((i & 3) == 1) res1.push_back(res[i].ec);
			if ((i & 3) == 2) res2.push_back(res[i].ec);
		}
		int q1 = query(res1), q2 = query(res2);
		if (!q1 && !q2) {
			rep (i, 0, (int) res.size() - 1) {
				if ((i & 3) == 0) res[i].fb = 1;
			}
		}
		if (!q1 && q2) {
			rep (i, 0, (int) res.size() - 1) {
				if ((i & 3) == 1) res[i].fb = 1;
			}
		}
		if (q1 && !q2) {
			rep (i, 0, (int) res.size() - 1) {
				if ((i & 3) == 2) res[i].fb = 1;
			}
		}
		if (q1 && q2) {
			rep (i, 0, (int) res.size() - 1) {
				if ((i & 3) == 3) res[i].fb = 1;
			}
		}
		vector <pii> nxt;
		for (auto [v, st] : res) {
			if (!st) nxt.emplace_back(v, st);
		}
		nxt.swap(res);
	}
	if (res.size() == 3) {
		int Q = query(vector <int>(1, res[0].ec));
		if (!Q) {
			Q = query(vector <int>(1, res[0].ec));
			if (!Q) answer(res[1].ec), answer(res[2].ec);
		}
		Q = query(vector <int>(1, res[1].ec));
		if (Q) answer(res[0].ec), answer(res[1].ec);
		else answer(res[0].ec), answer(res[2].ec);
	}
	else {
		answer(res[0].ec);
		if (res.size() > 1) answer(res[1].ec);
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...