Question

ABC337 E Bad Juice

交互题

\(n\) 瓶果汁中有 \(1\) 瓶是坏的，现在需要把这些果汁分给 \(m\) 个人，每个人可以喝任意瓶，然后通过 \(m\) 个人的回复判断哪一瓶是坏的

需要输出最小的 \(m\) 以及坏果汁的编号

Solution

\(m\) 返回的结果由 \(01\) 构成，自然而然想到二进制，考虑 \(m\) 位二进制最多表示 \(2^m\) 个数字，所以一个数字对应一种情况，也就是最多能表示 \(2^m\) 种情况，所以最小的 \(m = \log_2(n-1)+1\)

然后考虑一一对应的情况，显然，用二进制直接对应编号就好了

特别的把 000... 的情况对应 \(n\) ，之后就把二进制数对应编号，具体的如果 \(x\) 的第 \(j\) 位为 \(1\) ，就说明第 \(j\) 个人需要喝第 \(x\) 瓶果汁

最后的答案求解其实很简单，只需要对 \(1\) 的人所喝的果汁取交集就好了

Code

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int m=0;
    while((1<<m) < n) m++;
    cout<<m<<endl;
    vector<vector<int> > p(m+1,vector<int>());
    vector<int> vis(n+1,1);
    for(int i=1;i<n;i++){
        int x = i;
        for(int j=1;j<=m;j++)
            if((x>>(j-1))&1) p[j].push_back(i);
    }
    for(int i=1;i<=m;i++){
        cout<<p[i].size()<<" ";
        for(int j=0;j<p[i].size();j++)
            cout<<p[i][j]<<" ";
        cout<<endl;
    }
    char ch;
    for(int i=1;i<=m;i++){
        cin>>ch;
        if(ch == '0'){
            for(int j=0;j<p[i].size();j++)
                vis[p[i][j]] = 0;
        }
    }
    int ans = -1;
    for(int i=1;i<n;i++)
        if(vis[i]) ans = i;
    if(ans == -1) cout<<n<<endl;
    else cout<<ans<<endl;
    return 0;
}