题解 ABC337E Bad Juice

JuRuoOIer · 2024-01-20 21:35:18 · 题解

题解 ABC337E Bad Juice

Part1 题意

有 n 杯果汁，其中一杯是发霉的，喝了发霉的果汁会窜稀。

现在你不知道哪杯是发霉的，但明天你要把这些果汁因此你想去坑你的好基友，让他们喝下这些果汁。每个基友可以喝很多杯果汁，每杯果汁可以被很多基友喝。

为了得罪尽量少的人，请求出最少需要给多少基友喝果汁，并构造出一种方案。

接下来用一个字符串 s 给出你的方案中每个人的窜稀情况，1 代表窜稀，0 代表没有窜稀。你需要据此输出发霉的果汁编号。

交互题。先读入 n，然后输出方案，然后读入 s，然后输出发霉的果汁编号。每次输出完需要刷新标准输出。编号全部从 1 开始。

Part2 做法

写这篇题解是因为赛时有很强的大佬来问我。

这是一道很经典的题目，建议记住。类似的思想可能用到。

首先答案如下：

• 最少需要的人数是 \log_2 (n-1)+1。
• 其中第 i 个人（从 1 开始）要喝所有编号二进制从低到高第 i 位为 1 的果汁。如果这个人窜稀了，则发霉的果汁编号二进制从低到高低 i 位显然也为 1，否则为 0。

Part3 常见问题

• Q1：为什么这样人数最少？
• A1：简单理解：如果选用 3 作为底数，那么显然 \log_3(n-1)>\frac{1}{2}\log_2(n-1)（\frac{1}{2}\log_2(n-1)=\log_4(n-1)），但是每一位却需要两个人分别喝掉这一位为 1 的果汁和这一位为 2 的果汁，因此更劣。
• Q2：为什么是 \log_2 (n-1)+1，而非 \log_2 n+1？
• A2：注意到 n=2^k 与 n=2^k-1 时的方案是相同的，只不过当 n=2^k 时，可能会出现 s 所有字符均为 0 的情况（即编号为 n 的果汁发霉了），需要特判。
• Q3：怎么刷新标准输出？
• A3：我也不知道别的，但是 endl 自动刷新（前提是你没有 #define endl '\n'）。

Part4 代码

加注释必要性不大，所以基本没加。与上文思路完全相同。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<cstring>
#include<string>
#define ll long long
#define ull unsigned long long
#define lf double
#define ld long double
using namespace std;
ll n,ans;
string s;
int main(){
    cin>>n;
    cout<<__lg(n-1)+1<<endl;
    for(int i=0;i<=__lg(n-1);i++){
        //这里我比较懒，选择了循环两次，即一次统计，一次输出
        ll sum=0;
        for(int j=1;j<=n;j++){
            if(j&(1<<i))sum++;
        }
        cout<<sum;
        for(int j=1;j<=n;j++){
            if(j&(1<<i))cout<<' '<<j;
        }
        cout<<endl;
    }
    cin>>s;
    for(int i=0;i<s.length();i++){
        if(s[i]=='1')ans+=(1<<i);
    }
    if(ans==0)ans=n;
    cout<<ans<<endl;
    return 0;
}