好题。

题意：

给定长度为 $n$（$n$ 为偶数） 的 01 字符串 $S$。

你可以向交互库进行询问。你可以向交互库输出一个长度为 $n$ 的 01 字符串 $Q$。设 $S$ 和 $Q$ 有 $k$ 个对应的位置上的字符相同。若 $k=n$ 或 $k=\frac n 2$，则交互库将返回 $k$，否则交互库将返回 $0$。

你最多向交互库询问 $n+500$ 次，要求求出 $S$。你只需要使最后一次询问的返回值为 $n$ 即可。此时你应立即结束程序，否则将得到不可预料的结果。

若你的字符串长度不为 $n$ 或出现 01 以外的字符，或者你的询问次数超过上限，则交互库会返回 $-1$。此时你应立即结束程序，否则将得到不可预料的结果。

$1\leq n\leq 1000$。

（我抄的题面）

你考虑如果已经确定了一个相同个数为 $k=\frac n 2$ 个的字符串会怎么做。

你考虑每次把第一个数和另外一个数一起反转。如果相同个数仍然为 $k=\frac n 2$，那么显然第一个数和另外一个数必然一个对一个错。我们这样询问 $1$ 和其他每一个位置，就能够得到包含所有位置的两个正确性相反的集合。然后，我们将这个得到的 $01$ 串和取反后的串询问，找到正确的输出即可。

这部分的次数显然是 $n$ 个。

考虑如何确定一个相同个数为 $k=\frac n 2$ 个的字符串。

首先，我们设一个全0​串，每次修改最左边的0为1，在这 $n$ 次询问中，肯定能找到一个相同个数为 $k=\frac n 2$ 的字符串。

你考虑他为啥是对的，如果全为0的时候有大于 $k=\frac n 2$ 个位置是对的，那么你变成全1的时候，有小于 $k=\frac n 2$ 个位置是对的。因为每次 $k$ 的变化最多为1，所以总会有一个串满足相同个数 $k=\frac n 2$。

然后我们得到了一个询问次数 $2n$ 的算法。然而你过不了嘛，必须优化。

你考虑如何在 $500$ 次内解决战斗。你考虑一开始确定一个相同个数为 $k=\frac n 2$ 个的字符串的时候，你随机选择位置，这样被卡的概率就会大大降低。

更精确地，每次随机选择的正确率是：$\frac{n \choose{\frac n 2}}{2^n}$。当 $n=1000$时，取随机次数为 $499$，此时它的正确率大于 $0.999$。

这样我们就得到了一个次数为 $n+500$ 的算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
int n,m;
int s[1005],ans[1005];
int main(){
    mt19937 rd((unsigned long long)new char);
    cin>>n;
    for(int i=1;i<500;++i){
        for(int j=1;j<=n;++j)s[j]=rd()%2,cout<<s[j];
        cout<<endl;
        cin>>m;
        if(m==n)return 0;
        if(m==n/2)break;
    }
    ans[1]=s[1],s[1]^=1;
    for(int i=2;i<=n;++i){
        s[i]^=1;
        for(int i=1;i<=n;++i)cout<<s[i];
        cout<<endl;
        cin>>m;s[i]^=1;
        if(m==n)return 0;
        ans[i]=s[i]^(m==n/2);
    }
    for(int i=1;i<=n;++i)cout<<ans[i];
    cout<<endl;
    cin>>m;
    if(m==n)return 0;
    for(int i=1;i<=n;++i)ans[i]^=1;
    for(int i=1;i<=n;++i)cout<<ans[i];
    cout<<endl;
    return 0;
}