很神奇啊。
注意到如果能找到一个刚好有 \(\dfrac{n}{2}\) 个位置相同的串，记作 \(a\)。然后枚举 \(i=2\ldots n\)，每次反转 \(a_1\) 和 \(a_i\) 的值，新串记作 \(b\)。如果此时还是刚好有 \(\dfrac{n}{2}\) 个位置相同，那么说明 \(b_1\) 和 \(b_i\) 与目标串的正确性相反，反之相同。于是最后可以再花 2 次询问找到目标串。下面就是要解决如何找到 \(a\) 的问题了。
有一个询问 \(n\) 次的算法：考虑初始全为 0，每次反转最前面的一个 0 直到刚好有 \(\dfrac{n}{2}\) 个位置相同。正确性就是你考虑分类成 1 多还是 0 多，然后看一位一位改的影响。
但是这是 \(2n+1\) 的啊，怎么办？考虑一种神奇的做法：每次直接随机一个串判断，重复 499 次。每次询问撞到这种串的概率是 \(\dfrac{\dbinom{n}{\frac{n}{2}}}{2^n}\)，重复 499 次后得到这种串的概率极高，基本可以看作总是能找到。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int a[1005],b[1005];
signed main(){
mt19937 rnd(time(0));
int n=read();
for(int i=1;i<=499;i++){
for(int j=1;j<=n;j++)a[j]=rnd()&1;
for(int j=1;j<=n;j++)printf("%d",a[j]);
cout<<endl;int cnt=read();
if(cnt==n)return 0;
if(cnt==n/2)break;
}
a[1]^=1,b[1]=a[1];
for(int i=2;i<=n;i++){
a[i]^=1;for(int j=1;j<=n;j++)printf("%d",a[j]);
cout<<endl;int cnt=read();
if(cnt==n)return 0;
b[i]=a[i]^(cnt==n/2),a[i]^=1;
}
for(int i=1;i<=n;i++)printf("%d",b[i]);
cout<<endl;int cnt=read();
if(cnt==n)return 0;
for(int i=1;i<=n;i++)printf("%d",b[i]^1);
return 0;
}