[ABC337E] Bad Juice 题解
fydj
·
·
题解
E - Bad Juice
题目翻译
有 N 杯果汁，编号为 1 到 N，其中有且只有一杯坏果汁。
你可以选 M 位朋友，给第 i 人喝 K_i 杯果汁，编号分别为 A_{i,1} 到 A_{i,K_i}。
先输出 M，再输出 M 行，第 i 行描述第 i 个人的情况，依次输出 K_i，A_{i,1} 到 A_{i,K_i}。
然后会得到一个字符串 S，从左往右数第 i 位表示第 i 个人有没有喝到坏果汁。
最后你要输出坏果汁的编号，并让 M 最小。
思路
算法 1
##### 算法 2
$M=N-1$。类似线段树的做法。对于区间 $[l,r]$，让一个人喝 $[l,mid]$ 中的所有果汁，然后继续询问区间 $[l,mid]$ 和 $[mid+1,r]$。发现这并不比算法 1 好多少。
##### 算法 3
$M=\log N$。想起了小时候的一个魔术：给你几张卡片，卡片上写了一些数，让你在心里想一个数，问你这个数在哪几张卡片上，然后就可以猜出你想的数。这个魔术的原理是二进制拆分，第 $i$ 张卡片上有着范围内所有二进制下第 $i$ 位是 $1$ 的数。如果你想的数在第 $i$ 张卡片上，就说明它在二进制下第 $i$ 位为 $1$；反之，为 $0$。
发现这个魔术和这道题目十分类似，可以使用类似的做法。用 $\log N$ 个人，第 $i$ 个人喝 $[1,N]$ 内所有编号二进制第 $i$ 位为 $1$ 的果汁。如果他喝到了坏果汁，那么就说明坏果汁编号在二进制下第 $i$ 位为 $1$；反之，为 $0$。
一个细节，当 $N$ 为 $2$ 的正整数次幂的时候，第 $\log N$ 次询问只会询问 $N$，显得十分浪费，所以可以不进行最后一次询问，当坏果汁都不被前面所有人喝到的时候，就说明坏果汁的编号为 $N$。
### 代码
```cpp
#include<algorithm>
#include<iostream>
#include<cstring>
#include<utility>
#include<cstdio>
#include<cmath>
#include<map>
using namespace std;
typedef long long ll;
const int N=10009;
char chart,s[N]={}; bool fushu;
template <typename T> void read(T &a) { a=fushu=0; do chart=getchar(); while((chart<48||chart>57)&&chart!='-'); if(chart=='-') fushu=1,chart=getchar(); do a=(a<<1)+(a<<3)+(chart^48),chart=getchar(); while(chart>47&&chart<58); if(fushu) a=-a; return ; }
template <typename T,typename ...Args> void read(T &a,Args &...args) { read(a); read(args...); return ; }
int n,sask=0;
int main()
{
int i,j,sum,ans=0;
cin>>n;
sask=__lg(n)+1;
if(n==(1<<sask-1)) --sask;
cout<<sask<<endl;
for(i=0;i<sask;++i) {
sum=0;
for(j=1;j<=n;++j)
if(j&(1<<i))
++sum;
cout<<sum<<" ";
for(j=1;j<=n;++j)
if(j&(1<<i))
cout<<j<<" ";
cout<<endl;
}
cin>>s;
for(i=0;i<sask;++i)
ans|=(1<<i)*(s[i]^48);
if(!ans) ans=n;
cout<<ans<<endl;
return 0;
}
```