AT_abc337_e 题解

Yuneko · 2024-01-21 12:40:38 · 个人记录

题目链接

题目传送门（at）

题目传送门（luogu）

题意简述

有 n 瓶饮料，其中有一瓶坏的，你需要使用最少的小白鼠使得这些小白鼠能找出已经变质的饮料的编号，对于每只小白鼠，你可以给他们喝任意瓶的饮料，每瓶饮料可以被平均分。

解题思路

妙妙构造题。

思路一：

拿 n 个小白鼠，每个小白鼠喝编号不同的饮料，这也是最简单的思路，但无法通过此题。

思路二：

拿 n-1 个小白鼠，每只小白鼠编号分别为 1,2,\dots,n-1，对于编号为 i 的小白鼠，就喝第 i,i+1 瓶的饮料，最后变质的饮料编号很容易求出，但无法通过此题。

此思路参考代码：

#include<bits/stdc++.h>
using namespace std;
#define map unordered_map
#define forl(i,a,b) for(register long long i=a;i<=b;i++)
#define forr(i,a,b) for(register long long i=a;i>=b;i--)
#define lc(x) x<<1
#define rc(x) x<<1|1
#define cin(x) scanf("%lld",&x)
#define cout(x) printf("%lld",x)
#define lowbit(x) x&-x
#define pb push_back
#define pf push_front
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//#define endl '\n'
#define QwQ return 0;
#define ll long long
string s;
ll n,a[110];
int main()
{
    IOS;
    cin>>n;
    cout<<n-1<<endl;
    forl(i,1,n-1)
        cout<<"2 "<<i<<" "<<i+1<<endl;
    cin>>s;
    forl(i,0,s.size()-1)
        a[i+1]=s[i]-'0';
    forl(i,1,n-1)
        if(a[i] && a[i+1])
        {
            cout<<i+1<<endl;
            QwQ;
        }
    if(a[1] && !a[2])
        cout<<1<<endl;
    else
        cout<<n<<endl;
    QwQ;
}

思路三：

拿 \lceil \log_2(n) \rceil 个小白鼠，编号为 i 的小白鼠都喝下 x \bmod 2^i=1 的所有饮料，其中 x 为所有的饮料编号，这样，若最后给出的字符串第 i 位为 1，说明最终饮料编号的第 i 位为 1，最后变质的饮料编号直接计算即可，但是此思路还是无法通过此题。

此思路参考代码：

#include<bits/stdc++.h>
using namespace std;
#define map unordered_map
#define forl(i,a,b) for(register long long i=a;i<=b;i++)
#define forr(i,a,b) for(register long long i=a;i>=b;i--)
#define lc(x) x<<1
#define rc(x) x<<1|1
#define cin(x) scanf("%lld",&x)
#define cout(x) printf("%lld",x)
#define lowbit(x) x&-x
#define pb push_back
#define pf push_front
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//#define endl '\n'
#define QwQ return 0;
#define ll long long
ll n,ans;
string s[110],sss;
void init()
{
    forl(i,1,100)
    {
        ll x=i;
        string ss="";
        while(x)
            ss+=x%2+'0',x/=2;
        //reverse(ss.begin(),ss.end());
        ss+="0000000000000000000000";
        s[i]=ss;
    }
}
ll query(ll x)
{
    ll su=0;
    while(x)
        x/=2,su++;
    return su;
}
long long pw(long long x,long long y,long long mod)
{
    if(y==0)
        return 1;
    long long an=1,tmp=x;
    while(y!=0)
    {
        if(y&1)
            an=(an%mod*tmp%mod)%mod;
        tmp=(tmp%mod*tmp%mod)%mod;
        y=y>>1;
    }
    an=an%mod;
    return an%mod;
}
int main()
{
    IOS;
    init();
    cin>>n;
    cout<<query(n)<<endl;
    ll cs=query(n);
    forl(i,1,cs)
    {
        ll sum=0;
        ll ans[110]={0};
        forl(j,1,n)
            if(s[j][i-1]=='1')
                sum++,ans[sum]=j;
        cout<<sum<<" ";
        forl(i,1,sum)
            cout<<ans[i]<<" ";
        cout<<endl;
    }
    cin>>sss;
    forl(i,0,cs-1)
        if(sss[i]=='1')
            ans+=pw(2,i,1e18);
    cout<<ans<<endl;
    QwQ;
}

思路四：

分两种情况考虑：

• 若 \lceil \log_2(n) \rceil = \log_2(n)，则拿 \lceil \log_2(n) \rceil - 1 个小白鼠，编号为 i 的小白鼠都喝下 x \bmod 2^i=1 的所有饮料，其中 x 为所有的饮料编号，这样，若最后给出的字符串第 i 位为 1，说明最终饮料编号的第 i 位为 1，最后的变质饮料编号直接计算即可，若给出的字符串中的所有数字均为 0，则容易得出最后的变质饮料编号为 n。

• 若 \lceil \log_2(n) \rceil \neq \log_2(n)，则拿 \lceil \log_2(n) \rceil 个小白鼠，编号为 i 的小白鼠都喝下 x \bmod 2^i=1 的所有饮料，其中 x 为所有的饮料编号，若最后给出的字符串第 i 位为 1，说明最终饮料编号的第 i 位为 1，最后变质的饮料编号直接计算即可。

此思路可以通过此题。

此思路参考代码：

#include<bits/stdc++.h>
using namespace std;
#define map unordered_map
#define forl(i,a,b) for(register long long i=a;i<=b;i++)
#define forr(i,a,b) for(register long long i=a;i>=b;i--)
#define lc(x) x<<1
#define rc(x) x<<1|1
#define cin(x) scanf("%lld",&x)
#define cout(x) printf("%lld",x)
#define lowbit(x) x&-x
#define pb push_back
#define pf push_front
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//#define endl '\n'
#define QwQ return 0;
#define ll long long
ll n,ans;
string s[110],sss;
long long pw(long long x,long long y,long long mod)
{
    if(y==0)
        return 1;
    long long an=1,tmp=x;
    while(y!=0)
    {
        if(y&1)
            an=(an%mod*tmp%mod)%mod;
        tmp=(tmp%mod*tmp%mod)%mod;
        y=y>>1;
    }
    an=an%mod;
    return an%mod;
}
map<ll,ll>vis;
void init()
{
    forl(i,0,20)
        vis[pw(2,i,1e18)]=1;
    forl(i,1,100)
    {
        ll x=i;
        string ss="";
        while(x)
            ss+=x%2+'0',x/=2;
        //reverse(ss.begin(),ss.end());
        ss+="0000000000000000000000";
        s[i]=ss;
    }
}
ll query(ll x)
{
    ll su=0;
    while(x)
        x/=2,su++;
    return su;
}
int main()
{
    IOS;
    init();
    cin>>n;
    if(!vis[n])
    {
        cout<<query(n)<<endl;
        ll cs=query(n);
        forl(i,1,cs)
        {
            ll sum=0;
            ll ans[110]={0};
            forl(j,1,n)
            {
                if(s[j][i-1]=='1')
                    sum++,ans[sum]=j;
            }
            cout<<sum<<" ";
            forl(i,1,sum)
                cout<<ans[i]<<" ";
            cout<<endl;
        }
        cin>>sss;
        forl(i,0,cs-1)
            if(sss[i]=='1')
                ans+=pw(2,i,1e18);
        cout<<ans<<endl;
    }
    else
    {
        cout<<query(n)-1<<endl;
        ll cs=query(n)-1;
        forl(i,1,cs)
        {
            ll sum=0;
            ll ans[110]={0};
            forl(j,1,n)
                if(s[j][i-1]=='1')
                    sum++,ans[sum]=j;
            cout<<sum<<" ";
            forl(i,1,sum)
                cout<<ans[i]<<" ";
            cout<<endl;
        }
        cin>>sss;
        forl(i,0,cs-1)
            if(sss[i]=='1')
                ans+=pw(2,i,1e18);
        if(ans)
            cout<<ans<<endl;
        else
            cout<<n<<endl;
    }
    QwQ;
}