周报素材

发布时间 2023-09-12 21:21:25作者: WW爆米花

H. Hardcore Hangman

题意:

有一个隐藏字符串,只允许提问6次,
每次提问可问多个字母,
若隐藏字符串中出现了所提问的字母,则返回所在下标,
编写程序输出隐藏字符串

分析

把26个字母映射成0-25,则可用二进制唯一表示出来,
因为2的5次方>26,所以5位二进制数即可表示一个字母。

则隐藏字符串每一个字母都用5位二进制表示

已知二进制数只有01两种情况

5次机会,每次询问一个位

如:第一次询问最高位为1的有哪些位置,将这些位置的最高位设为1,其他位置设为0
第二次询问次高位为1的有哪些位置,将这些位置的次高位设为1,其他位置设为0

则5次后,隐藏字符串的每个位置都得到了一个二进制数,将其转化为十进制数再转化为字母

现在考虑询问方式:
询问最高位为1,等价于询问二进制数最高位为1的字母,
最高位为1的数是16-32,则我们询问字母包括:p(16)及p之后的所有字母

using namespace std;
#define ll long long
//#define endl '\n'
const int N=1e5+10;
#define inf 0x3f3f3f3f3f3f3f3f
/*
int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
*/

void solve(){
    cout<<"? ";
    for(char i='a';i<='z';i++)cout<<i;
    cout<<endl;
    int n;cin>>n;
    for(int i=1,x;i<=n;i++)cin>>x;
    vector<int> a(n+1);
    for(int i=0,t;i<5;i++){
        cout<<"? ";
        for(int j=0;j<26;j++){
            if(j&(1<<i))cout<<(char)('a'+j);
        }
        cout<<endl;
        cin>>t;
        for(int j=1,x;j<=t;j++){
            cin>>x;a[x]|=(1<<i);
        }
    }
    cout<<"! ";
    for(int i=1;i<=n;i++){
        cout<<(char)('a'+a[i]);
    }
    cout<<endl;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}