CF2037E Kachina's Favorite Binary String 解题报告

_mi_ka_ · 2024-11-19 19:58:52 · 题解

是可爱的卡齐娜耶！！！

题目大意

交互题（不会交互题的可以去做洛谷的板子 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 并且再次之前一定只有一种可能：

再之后，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");
        else
            cout<<"! "<<s<<'\n';
        fflush(stdout);
    }
    return 0;
}