自动搬运

查看原文

来自洛谷，原作者为

	rui_er 九万里风鹏正举

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

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

以下是正文

UPD(2021.6.22)：加强了数据，更新解法。

本题解是「RdOI R2」称重(weigh) 的官方题解。

简单思维题。

根据题意，一个假球比一个真球轻，但两个假球比一个真球重，显然询问一要得到信息肯定要使 $p=q$，否则得不到任何有用的信息。

考虑分类讨论：

• 第一种情况：在 $n=2i$ 个球中找一个假球。

考虑将球拆为两组，每组有 $i$ 个球，并询问。因为只有一个假球，显然两组的质量肯定不相等，此时假球在质量更小的一组。

• 第二种情况：在 $n=2i$ 个球中找两个假球。

同样拆成两组，各 $i$ 个球。如果得到 =，则两组各有一个假球；否则两个假球都在质量更小的一组。

• 第三种情况：在 $n=2i+1$ 个球中找一个假球。

将球拆为三组，分别有 $i,i,1$ 个，询问 $i$ 个球的两组。如果得到 =，则单独的球是假球；否则假球在质量更小的一组。

• 第四种情况：在 $n=2i+1$ 个球中找两个假球。

同样拆成三组，分别有 $i,i,1$ 个。询问前两组。如果得到 =，则两组各有一个假球；否则在质量更大的一组（总共只有两个假球，可以断定这组必定全为真球）中取一个球与单独的球询问，质量相等则两个假球都在质量更小的一组，否则单独的球是假球，另一个假球在质量更小的一组。

现在思路就比较显然了吧，初始状态是 $\left[1,n\right]$ 中找两个假球，然后按照上面的分类讨论进行二分即可。

std 在所有测试点中的最大询问次数是 $15$ 次。

给出 std 代码供参考：Link

但是上面的 std 在 2021.6.22 的数据加强中被卡成了 Unaccepted $99$ 分。

考虑进一步优化。

当在区间内找一个假球的时候，我们每次排除 $\dfrac{1}{2}$ 的球，但是显然可以更优。我们在左、右各取大约 $\dfrac{1}{3}$ 的球进行询问，如果相等则递归询问中间段，否则询问更轻的段，这样利用三分的思想，每次可以排除 $\dfrac{2}{3}$ 的球。

代码：

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define loop while(true)
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define fil(x,y) memset(x, y, sizeof(x))
#define mulT0 int T; for(scanf("%d", &T);T;T--)
#define mulT1 int T, rnds; for(scanf("%d", &T),rnds=1;rnds<=T;rnds++)
using namespace std;
typedef long long ll;
const int N = 505;

int n, a[N], b[N];
vector<int> ans;
int interact(int *a, int p, int *b, int q) {
	printf("1 %d ", p);
	rep(i, 1, p) printf("%d ", a[i]);
	printf("%d ", q);
	rep(i, 1, q) printf("%d%c", b[i], " \n"[i==q]);
	fflush(stdout);
	char tmp[2];
	scanf("%s", tmp);
	if(tmp[0] == '<') return -1;
	if(tmp[0] == '=') return 0;
	return 1;
}
void searchAns(int L, int R, int k) {
//	printf("searchAns %d %d %d\n", L, R, k);
	int len = R - L + 1, M = (L + R) >> 1, tA = 0, tB = 0;
	int ML = L + (R - L) / 3, MR = R - (R - L) / 3;
//	printf("%d %d\n", ML, MR);
	if(len == k) {
		if(k == 1) ans.push_back(L);
		else ans.push_back(L), ans.push_back(R);
		return;
	}
	if(k == 1) {
		rep(i, L, ML) a[++tA] = i;
		rep(i, MR, R) b[++tB] = i;
		int res = interact(a, tA, b, tB);
		if(!res) return searchAns(ML+1, MR-1, 1);
		if(res == 1) return searchAns(MR, R, 1);
		return searchAns(L, ML, 1);
	}
	if(len & 1) {
		rep(i, L, M-1) a[++tA] = i;
		rep(i, M, R-1) b[++tB] = i;
		int res = interact(a, tA, b, tB);
		if(!res) {
			searchAns(L, M-1, 1);
			searchAns(M, R-1, 1);
		}
		else if(res == 1) {
			a[1] = L; b[1] = R;
			int qwq = interact(a, 1, b, 1);
			if(qwq == 1) {
				ans.push_back(R);
				searchAns(M, R-1, 1);
			}
			else searchAns(M, R-1, 2);
		}
		else {
			a[1] = R - 1; b[1] = R;
			int qwq = interact(a, 1, b, 1);
			if(qwq == 1) {
				ans.push_back(R);
				searchAns(L, M-1, 1);
			}
			else searchAns(L, M-1, 2);
		}
	}
	else {
		rep(i, L, M) a[++tA] = i;
		rep(i, M+1, R) b[++tB] = i;
		int res = interact(a, tA, b, tB);
		if(!res) {
			searchAns(L, M, 1);
			searchAns(M+1, R, 1);
		}
		else if(res == 1) searchAns(M+1, R, 2);
		else searchAns(L, M, 2);
	}
}

int main() {
	scanf("%d", &n);
	searchAns(1, n, 2);
	sort(ans.begin(), ans.end());
	printf("2 %d %d\n", ans[0], ans[1]);
	fflush(stdout);
	return 0;
}