题解：CF2037E Kachina's Favorite Binary String

· · 题解

前言

显然，前缀 01 子序列数是单调不降的。

0 的贡献是 0，1 的贡献是其前面 0 的数量，可前缀和维护。

思路

问区间 1 到 2，至区间 1 到 n，如果变大了，那这一位一定是 1，因为只有 1 有贡献，如果没变，且大于 0（前面至少有一个 0），那这一位一定是 0，因为 1 会和前面的 0 产生贡献。

到现在，只有那一段询问结果是 0 的前缀没确定了。

诶！是 0 耶，所有 1 前面没有 0，那不就只能是全 1、全 0 或一段 1 拼接一段 0 了吗！

枚举 1 与 0 的分界点，前缀和暴力检查是否只有 1 种形态符合询问结果，于是，这道题就愉快得做完了。

代码

#include <bits/stdc++.h>
#define int long long
#define vit vector
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
#define db double
#define it iterator

using namespace std;
const int N=1e4+5,INF=0x3f3f3f3f,mod=998244353;
int _,n,a[N],b[N],s[N];
signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>_;
    while(_--){
        cin>>n;
        for(int i=1;i<=n;i++){
            if(i>1){
                cout<<"? 1 "<<i<<endl;
                cin>>a[i];
            }else a[1]=0;
            if(a[i]>a[i-1]) b[i]=1;
            else if(a[i-1]>0) b[i]=0;
        }
        int I=0,J,ct=0;
        for(int i=1;i<=n;i++){
            if(a[i]) break;
            I=i;
        }
        for(int i=0;i<=I;i++){
            for(int j=1;j<=i;j++) b[j]=1;
            for(int j=i+1;j<=I;j++) b[j]=0;
            int x=0,f=1;
            for(int i=1;i<=n;i++){
                s[i]=s[i-1]+!b[i];
                if(b[i]) x+=s[i];
                if(x!=a[i]) f=0;
            }
            ct+=f;
            if(f) J=i;
        }
        cout<<"! ";
        if(ct!=1) cout<<"IMPOSSIBLE";
        else{
            for(int i=1;i<=J;i++) cout<<1;
            for(int j=J+1;j<=I;j++) cout<<0;
            for(int i=I+1;i<=n;i++) cout<<b[i];
        }
        cout<<endl;
    }
    return 0;
}