自动搬运

查看原文

来自洛谷，原作者为

	abruce I won't feel lonely, nor will I be sorrowful... not before everything is buried.

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

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

以下是正文

由于出题人咕了，所以由我验题人来写一篇（备用）题解。
很妙的题。

10pts

对于每瓶水，我们用 $3$ 只小白鼠来检验，如果有一瓶水有超过两只小白鼠死亡，则这是毒水。最大需要 $3000$ 只。

30pts

如果没有变异鼠，这是一个非常经典的问题，我们可以考虑二进制分组，对于第 $i$ 只小白鼠，我们让它喝下二进制下第 $i$ 位为 $1$ 的所有水，这样就可以通过二进制拼出来哪瓶是毒水。
但是因为变异鼠的存在，所以我们对于每个二进制位都需要 $3$ 只小白鼠来检验。最大需要 $30$ 只。

100pts

我们发现对于每个二进制位都用 $3$ 只小白鼠来检验太浪费了，我们来考虑怎么优化。
我们可以再重复一次上面的过程。首先肯定是要用 $10$ 只小白鼠每个二进制位用一只。然后我们再对这 $10$ 只进行二进制分组。新用 $4$ 只小白鼠，第 $i$ 只小白鼠代表这 $10$ 只中二进制位为 $1$ 的小白鼠所喝的水的异或。最后还需要 $1$ 只小白鼠喝前面这 $4$ 只小白鼠所喝的水的异或。一共需要 $15$ 只，刚好满足。
如果选的最后 $5$ 只鼠中有奇数只被毒死，这说明中间有变异鼠，因为这 $5$ 只鼠总共把每瓶水都喝了偶数次。那么前面 $10$ 只就都是有效信息，用它们判断即可。
否则说明变异鼠在前面 $10$ 只中，这时我们就要用中间那 $4$ 只进行检验。如果它和它所管辖的小白鼠状态异或起来得到 $1$，那么就说明它管辖的小白鼠中有变异鼠。
这样我们就可以得知变异鼠的位置，把它的状态改变即可。
下面是代码。

#include<bits/stdc++.h>
using namespace std;
int n,k,v[16],cnt;
bitset<1005> b[16],bit;
bool pd;
int main() {
	int x,lg,lglg;
	cin>>n>>k,bit.set();
	if(n==1)return cout<<2<<endl<<1<<endl,0;
	if(n==2) {
		cout<<"1 1 1"<<endl<<2<<endl;
		cin>>x;
		cout<<2-x<<endl;
		return 0;
	}
	lg=log2(n-1)+1;
	lglg=log2(lg-1)+1;
	for(register int i=0; i<lg; i++) {
		int cnt=0;
		for(register int j=0; j<n; j++)if(j&(1<<i))cnt++,b[i][j]=1;
		cout<<"1 "<<cnt<<' ';
		for(register int j=0; j<n; j++)if(j&(1<<i))cout<<j+1<<' ';
		cout<<endl;
	}
	for(register int i=0; i<lglg; i++) {
		cout<<"1 ";
		for(register int j=0; j<lg; j++)if(j&(1<<i))b[i+lg]^=b[j];
		cout<<b[i+lg].count()<<' ';
		for(register int j=0; j<n; j++)if(b[i+lg][j])cout<<j+1<<' ';
		cout<<endl;
		b[lg+lglg]^=b[i+lg];
	}
	cout<<"1 "<<b[lg+lglg].count()<<' ';
	for(register int j=0; j<n; j++)if(b[lg+lglg][j])cout<<j+1<<' ';
	cout<<endl<<2<<endl;
	for(register int i=0; i<=lg+lglg; i++)cin>>v[i],v[i]^=1;
	for(register int i=lg; i<=lg+lglg; i++)pd^=v[i];
	if(!pd) {
		int fake=0;
		for(register int i=0; i<lglg; i++) {
			int p=v[i+lg];
			for(register int j=0; j<lg; j++)if(j&(1<<i))p^=v[j];
			fake+=p<<i;
		}
		v[fake]^=1;
	}
	for(register int i=0; i<lg; i++)if(v[i])bit&=b[i];
	cout<<bit._Find_first()+1<<endl;
	return 0;
}