为了庆祝 Atcoder 上绿写一篇题解吧

zibenlun · 2024-01-24 21:32:58 · 题解

题目链接

比较水的交互题

Solution

题目大意就是让你用最少的朋友验证出坏了的橙汁。

题目中比较关键的在于只有一杯坏掉的橙汁，所以我们可以想到用二进制来表示每一杯橙汁的编号，经过询问后再把所有喝到坏橙汁的朋友转换成二进制，就可以查询到哪一杯橙汁是坏的。

小细节

• 想要知道 n 杯橙汁的情况，我们其实只需要知道其中的 n-1 杯就行。因为前 n-1 杯要是有坏的，最后一杯一定不是坏的，反之最后一杯一定是坏的。

• 橙汁的编号一定不能从零开始，如果第 0 杯是坏掉的，那么我们也无法判断。

• 其余的细节放在代码注释中了。

#include<bits/stdc++.h>
using namespace std;
vector<int> v[100005];
int n,lg,u=1; 
int main(){
    cin>>n;
    while(u*2<=n){
        u*=2;
        lg++;
    }
    cout<<lg+(u!=n)<<endl;//不能正好满一位，再额外加一位 
    for(int i=1;i<=n-1;i++){
        int cnt=0,x=i;
        while(x){
            x>>=1;
            cnt++;
        }//预处理这一杯橙汁的位数 
        x=i;
        for(int j=1;x;j++){
            if(x&1) v[j].push_back(i);//统计每一个人需要喝哪几杯 
            x>>=1;
        }
    }
    for(int i=1;i<=lg+(u!=n);i++){
        cout<<v[i].size();
        for(auto j:v[i]) cout<<" "<<j;
        cout<<endl;
    }
    int pos=0,ans=0;
    for(int i=1;i<=lg+(u!=n);i++){
        char c;
        cin>>c;
        int x=c-'0';
        ans+=(1<<pos)*x;//转换回杯子的编号 
        pos++;
    }
    if(ans!=0) cout<<ans<<endl;
    else cout<<n<<endl;
    return 0;
}