题解--毒水

· · 题解

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

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;
}