CF2038G Guess One Character 题解

考虑 01 连续段，先询问 11 的个数为 a，1 的个数为 b，则显然，1 构成了 a-b 个极长连续段。如果 b=0/n 则可以直接判定。否则考虑询问 10 的个数为 x，如果 x=a-b，那说明每个 1 连续段后面都有一段 0，显然 s_n=0，否则一定有 x=a-b-1，说明最后一个 1 连续段之后没有 0 了，显然 s_n=1。直接交互即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

int T,n;

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        int X,a,b;
        puts("1 10");
        fflush(stdout);
        scanf("%d",&X);
        puts("1 11");
        fflush(stdout);
        scanf("%d",&a);
        puts("1 1");
        fflush(stdout);
        scanf("%d",&b);
        int x1=b-a;
        if(b==0){puts("0 1 0");fflush(stdout);scanf("%d",&X);continue;}
        if(b==n){puts("0 1 1");fflush(stdout);scanf("%d",&X);continue;}
        if(x1==X){printf("0 %d 0\n",n);fflush(stdout);scanf("%d",&X);continue;}
        else printf("0 %d 1\n",n),fflush(stdout),scanf("%d",&X);;
    }

    return 0;
}