是可爱的卡齐娜耶！！！
题目大意
交互题（不会交互题的可以去做洛谷的板子 P1733），\(T\) 组交互，每次交互库会指定一个长度为 \(n\) 的 \(01\) 字符串（只由 \(0\) 和 \(1\) 组成），你最多询问 \(n\) 次，每次询问你给出一个区间 \([l,r]\)，交互库会给出指定字符串的 01 子串的个数（0 和 1 可以不相连，且 0 和 1 只要有其一位置不同都将会认为成不同的 01 子串）。在最多 \(n\) 次询问后，确定这个字符串，或者输出 IMPOSSIBLE 代表无论怎样 \(n\) 次询问都不能确定这个字符串。
解题思路
考虑字符串中的每个字符都要得到，每次询问至少要确定一个字符。要实现这种询问，考虑询问 \(n-1\) 次，第 \(i\) 次询问询问区间 \([1,1+i]\)，当 \(i\) 增大时，如果答案变大，说明这一位是 1 且答案的增量 \(\Delta ans\) 为当前位之前的 0 的个数。如果答案不变，说明这一位为 0 或者这一位之前 0 的个数为 \(0\)。
假如说在第 \(i\) 次询问 \([1,i+1]\) 的答案 \(ans_i\) 第一次非零，那么第 \(i+1\) 位为 1 并且再次之前一定只有一种可能：
\[\underbrace{1\dots1}_{i-ans_i\ 个}\underbrace{0\dots0}_{ans_i\ 个}
\]
再之后，0 的个数被确定，记录一下当前零的个数，那么如果之后答案不变，当位就一定是 0，更新当前零的个数，如果答案变大，变大的一定是前面的零的个数，如果不是，那么这个序列不可能存在（不合法），直接输出 IMPOSSIBLE 即可。
进行完这 \(n-1\) 次询问后，只有三种情况：
- 这个序列已经被确定
- 这个序列不合法，已经输出 IMPOSSIBLE
- 这个序列从头到尾交互库给出的所有数都是 \(0\)，此时这个序列肯定是由 \(k\) 个连续的
1和 \(n-k\) 个连续的0拼接而成，其中 \(0\le k\le n\)，此时再进行任何区间的询问得到的答案都肯定是 \(0\)，第 \(n\) 次询问可有可无，都无法确定序列，输出 IMPOSSIBLE。
AC Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
using namespace std;
int T,n;
int re()//防止作弊不放快读快写
void wr(int x)
signed main()
{T=re();while(T--){n=re();string s="";//当前确定的序列 int last=0,zero=0;//前一个的答案和当前 0 的个数 for(int i=2;i<=n;i++){printf("? 1 %d\n",i);fflush(stdout);int x=re();if(last==0){if(x==0)continue;//如果 x 不等于 0，则此处为 ans 的第一次非零，此时序列确定 for(int j=1;j<=i-1-x;j++)s+='1';for(int j=1;j<=x;j++)s+='0';s+='1';zero=last=x;}else{int cha=x-last;//ans 的增量 if(cha==0)zero++,s+='0';else if(cha==zero)s+='1',last=x;else//不合法 break;}}if(s.length()!=n)//后两种情况 puts("! IMPOSSIBLE");elsecout<<"! "<<s<<'\n';fflush(stdout);}return 0;
}