<题目链接>
题目大意：
有一个长度为n(n<1000)的01串，该串中至少有一个0和一个1，现在由你构造出一些01串，进行询问，然后系统会给出你构造的串与原串的 Hamming distance ，现在要求你按照步骤进行交互式操作，最终得到任意一个0、1的下标。
解题分析：
因为原串中至少存在一个0和一个1，所以一定存在一个01或者10序列，因此我们可以用二分来寻找这个序列（注意二分过程中选择区间的操作）。二分之后，一定能够得到01或10序列，然后将其按先0后1的顺序输出即可。
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std; int main(){
ios::sync_with_stdio(false);
int n,num;cin>>n;
puts("?");
for(int i=;i<=n;i++)cout<<"";
puts("");
cin>>num; //第一次交互，先得到序列中1的个数
int l=,r=n;
while(r-l>=){ //二分寻找01或10串
int mid=(l+r)>>;
puts("?");
for(int i=;i<=n;i++){ //这里的区间判定方法很难想
if(i>=l && i<=mid)cout<<"";
else cout<<"";
}puts("");
int x1;cin>>x1;
if(abs(num-x1)==(mid-l+))l=mid; //判断左区间是否全为0或全为1,因为我们需要查找的是01串，所以需要向含有01串的地方收敛
else r=mid;
}
//得到了10或01串的位置后，判断其中0、1的位置
puts("?");
for(int i=;i<=n;i++){
if(i==l)cout<<"";
else cout<<"";
}puts("");
int x2;cin>>x2;
if(x2<num) printf("! %d %d\n",r,l); //先输出0的位置
else printf("! %d %d\n",l,r);
}
2019-02-01