本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-24 21:32:58

题目链接

比较水的交互题

Solution

题目大意就是让你用最少的朋友验证出坏了的橙汁。

题目中比较关键的在于只有一杯坏掉的橙汁，所以我们可以想到用二进制来表示每一杯橙汁的编号，经过询问后再把所有喝到坏橙汁的朋友转换成二进制，就可以查询到哪一杯橙汁是坏的。

小细节

• 想要知道 $n$ 杯橙汁的情况，我们其实只需要知道其中的 $n-1$ 杯就行。因为前 $n-1$ 杯要是有坏的，最后一杯一定不是坏的，反之最后一杯一定是坏的。

• 橙汁的编号一定不能从零开始，如果第 $0$ 杯是坏掉的，那么我们也无法判断。

• 其余的细节放在代码注释中了。

#include<bits\/stdc++.h>
using namespace std;
vector<int> v[100005];
int n,lg,u=1; 
int main(){
	cin>>n;
	while(u*2<=n){
		u*=2;
		lg++;
	}
	cout<<lg+(u!=n)<<endl;\/\/不能正好满一位，再额外加一位 
	for(int i=1;i<=n-1;i++){
		int cnt=0,x=i;
		while(x){
			x>>=1;
			cnt++;
		}\/\/预处理这一杯橙汁的位数 
		x=i;
		for(int j=1;x;j++){
			if(x&1) v[j].push_back(i);\/\/统计每一个人需要喝哪几杯 
			x>>=1;
		}
	}
	for(int i=1;i<=lg+(u!=n);i++){
		cout<<v[i].size();
		for(auto j:v[i]) cout<<" "<<j;
		cout<<endl;
	}
	int pos=0,ans=0;
	for(int i=1;i<=lg+(u!=n);i++){
		char c;
		cin>>c;
		int x=c-'0';
		ans+=(1<<pos)*x;\/\/转换回杯子的编号 
		pos++;
	}
	if(ans!=0) cout<<ans<<endl;
	else cout<<n<<endl;
	return 0;
}