题解 P7824【「RdOI R3」毒水】
whiteqwq
·
·
题解
P7824 「RdOI R3」毒水解题报告：
更好的阅读体验
题意
（$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;
}
```