交互

题意：有一个长度为 $n$ 的 $\texttt{01}$ 串，你每次可以询问一个字符串是否是这个 $\texttt{01}$ 串的子串，在 $2n$ 次询问之内求出这个 $\texttt{01}$ 串。

死亡回放

首先可以询问一个字符串是否是这个 $\texttt{01}$ 串的子序列，那么可以二分出 $\texttt{0}$ 的数量，然后枚举空位插 $\texttt{1}$。由于害怕被卡所以如果 $\texttt{0}$ 的数量比 $\texttt{1}$ 的数量少就将 $\texttt{01}$ 交换以减少询问次数。调了四十分钟，提交之后 WA 了。

发现是子串，汗流浃背了。那估计是固定一个位置开始延伸子串，首先问一次是不是全 $\texttt{1}$ 串，如果是则结束，否则从一个 $\texttt{0}$ 开始先向右扩展，然后再向左扩展。最坏情况会询问 $1+2 \times (n-1) + 2 = 2n + 1$ 次，因为无法向右扩展需要两次询问判定。考虑如何卡询问常数，很显然第 $2n$ 次询问如果是错的也可以确定串的最左端一位是啥，但是处理起来会有点麻烦。而每次随机问 $\texttt{01}$ 有 $\dfrac{1}{2}$ 的概率直接问对，那么被卡到最坏询问次数的概率就是 $\dfrac{1}{2^{100}}$，太对了哥。

实际上被卡到最坏询问次数的概率是 $\dfrac{1}{2^{n}}$，太错了，最后我化成雪白的灰。

只需要在第 $2n$ 次询问后直接输出答案就可以做到最坏 $2n$ 次询问，时间复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
int n,cnt;
int ask(string s){
    static int ret;
    cout<<'?'<<' '<<s<<endl;
    cin>>ret,++cnt;
    return ret;
}
void answer(string s){
    cout<<'!'<<' '<<s<<endl;
}
void solution(){
    cin>>n,cnt=0;
    string s;
    s.resize(n,'1');
    if(ask(s)) return answer(s);
    s="0";
    while(s.size()<n){
        if(ask(s+'0')) s=s+'0';
        else if(cnt==n*2||ask(s+'1')) s=s+'1';
        else break;
    }
    while(s.size()<n){
        if(ask('0'+s)) s='0'+s;
        else if(cnt==n*2||ask('1'+s)) s='1'+s;
        else break;
    }
    answer(s);
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin>>T;
    while(T--) solution();
    return 0;
}