P7824 「RdOI R3」毒水 解题报告

解题报告

P7824 「RdOI R3」毒水解题报告：

更好的阅读体验

题意

$n$ 瓶水，其中一瓶有毒，你可以检测若干次，每次选择若干瓶水，检测其中是否有毒水，但有且仅有一次检测结果会反过来，你需要在 $maxk$ 次检测内找出毒水。注意，结果不是实时得到，当你询问结束后才能一次性得到所有结果。

（$1\leqslant n\leqslant 1000,1\leqslant maxk\leqslant 15$）

分析

交互杀我！！！

$10pts$：很容易把每一瓶水检验三次，只要有两次检验出来就一定是毒水。

$30pts$：考虑没有那次反过来的检测如何求，我们可以直接检测每个二进制位是否有毒水，然后拼起来就好了，如果有那次反过来的检测，检测三次就可以避免。

$100pts$：检验三次消耗过大，考虑快速检验二级制位。

我们用 $\log \log n$ 次检测对二进制位的检测再次二进制拆分，然后再用 $1$ 次检测作为新加入的检测的异或。

很容易发现如果反转不在新加入的 $\log\log n+1$ 个检测，那么这 $\log\log n+1$ 个检测的死亡数为偶数。于是如果其为偶数，我们可以直接找到反转在前 $\log n$ 个检测中的位置，否则前 $\log n$ 个检测可以直接算。

检测次数 $\log n+\log\log n+1$，符合要求。

代码

#include<stdio.h>
#include<bitset>
#include<math.h>
using namespace std;
const int maxn=1005,maxk=15;
int n,k,lg,lglg;
int v[maxk];
bitset<maxn>ans,b[maxk];
int main(){
    scanf("%d%d",&n,&k);
    if(n==1&&k==0){
        puts("2"),fflush(stdout);
        puts("1"),fflush(stdout);
        return 0;
    }
    lg=log2(n-1)+1,lglg=log2(lg-1)+1;
    for(int i=0;i<lg;i++){
        for(int j=0;j<n;j++)
            if((j>>i)&1)
                b[i][j]=1;
        printf("1 %d ",b[i].count());
        for(int j=0;j<n;j++)
            if(b[i][j])
                printf("%d ",j+1);
        puts(""); 
    }
    for(int i=0;i<lglg;i++){
        for(int j=0;j<lg;j++)
            if((j>>i)&1)
                b[lg+i]^=b[j];
        printf("1 %d ",b[lg+i].count());
        for(int j=0;j<n;j++)
            if(b[lg+i][j])
                printf("%d ",j+1);
        puts("");
    }
    for(int i=0;i<lglg;i++)
        b[lg+lglg]^=b[lg+i];
    printf("1 %d ",b[lg+lglg].count());
    for(int i=0;i<n;i++)
        if(b[lg+lglg][i])
            printf("%d ",i+1);
    puts("\n2"),fflush(stdout);
    for(int i=0;i<=lg+lglg;i++)
        scanf("%d",&v[i]);
    int ok=0;
    for(int i=0;i<=lglg;i++)
        ok^=(v[lg+i]^1);
    if(ok==0){
        int pos=0;
        for(int i=0;i<lglg;i++){
            int ook=(v[lg+i]^1);
            for(int j=0;j<lg;j++)
                if((j>>i)&1)
                    ook^=(v[j]^1);
            pos+=(ook<<i);
        }
        v[pos]^=1;
    }
    ans.set();
    for(int i=0;i<lg;i++)
        if(v[i]==0)
            ans&=b[i];
    for(int i=0;i<n;i++)
        if(ans[i]){
            printf("%d\n",i+1),fflush(stdout);
            break;
        }
    return 0;
}