当前位置：首页 > article >正文

Codeforces Round 973 (Div. 2) C. Password Cracking

article 2024/9/27 5:58:01

题目链接：题目

大意：

猜一串二进制密码，每次可询问某串字符是否是密码的子串。

思路：

从左到右不断构建ans字符串，每次不是加 $1$ 就是加 $0$ ，这可以通过询问得到。如果末尾既不能加 $1$ 又不能加 $0$ ，说明已经构建到了最右边，那么开始向左边构建。（写这题的时候一直不对，后来发现是忘记cin >> t了，归根结底还是不熟悉交互式编程的输入输出方式）

代码：

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define MOD 1000000007
#define fi first
#define se second
#define pii pair<int,int>
#define vec vector

int query(string s){
    cout << "? " << s << endl;
    cout.flush();
    int res;
    cin >> res;
    return res;
}

void solve(){
    int n;
    cin >> n;
    string ans = "";
    bool turn = false;
    while(ans.size() < n){
        if(turn){
            if(query("1" + ans) == 1){
                ans = "1" + ans;
            }else{
                ans = "0" + ans;
            }
            continue;
        }
        if(query(ans + "1") == 1){
            ans = ans + "1";
        }else{
            if(query(ans + "0") == 1){
                ans = ans + "0";
            }else{
                turn = true;
            }
        }
    }
    cout << "! " << ans << '\n';
    cout.flush();
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}