题解：CF2037E Kachina's Favorite Binary String

zhouruoheng · 2024-11-19 17:28:19 · 题解

交互题，记得用 endl 或者 cout.flush() 清空缓存区。

询问次数最大为 n，设 k_i=f(1,i) (2 \le i \le n)。
先考虑无解的情况，显然是 k_n=0 时不能确定答案。
然后遍历 k，考虑如果 s_i=0，则一定有 k_i=k_{i-1}。所以当 k_i>k{i-1} 时，s_i=1。但这样有一个问题，如果 s 为 \mathtt{111\dots000\dots1\dots}，那么开头的 1 也都不会有贡献。所以找到第一个不等于 0 的 k_i，说明 [1,i-1] 中有 k_i 个 0，所以开头就有 i-1-k_i 个 1。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int N=1e4+5;
int n;
int s[N];
int query(int l,int r)
{
    int x;
    cout<<"? "<<l<<" "<<r<<' '<<endl;
    cin>>x;
    return x;
}
int k[N];
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++) s[i]=0;
    for(int i=2;i<=n;i++) k[i]=query(1,i);
    if(k[n]==0)
    {
        cout<<"! IMPOSSIBLE "<<endl;
        return ;
    }
    for(int i=2;i<=n;i++) if(k[i]>k[i-1]) s[i]=1;
    for(int i=2;i<=n;i++)
        if(s[i])
        {
            for(int j=1;j<=i-1-k[i];j++) s[j]=1;
            break;
        }
    cout<<"! "; 
    for(int i=1;i<=n;i++) cout<<s[i];
    cout<<' '<<endl;
}
int main ()
{
    #ifndef ONLINE_JUDGE 
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    #endif
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}