专栏文章

题解：CF2037E Kachina's Favorite Binary String

zzhouruoheng
CF2037E题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mir31q8j
此快照首次捕获于
2025/12/04 14:56
3 个月前
此快照最后确认于
2025/12/04 14:56
3 个月前
查看原文
交互题，记得用 endl 或者 cout.flush() 清空缓存区。
询问次数最大为 nn，设 ki=f(1,i)k_i=f(1,i) (2≤i≤n)(2 \le i \le n)。
先考虑无解的情况，显然是 kn=0k_n=0 时不能确定答案。
然后遍历 kk，考虑如果 si=0s_i=0，则一定有 ki=ki−1k_i=k_{i-1}。所以当 ki>ki−1k_i>k{i-1} 时，si=1s_i=1。但这样有一个问题，如果 ss 为 111…000…1…\mathtt{111\dots000\dots1\dots}，那么开头的 11 也都不会有贡献。所以找到第一个不等于 00 的 kik_i，说明 [1,i−1][1,i-1] 中有 kik_i 个 00，所以开头就有 i−1−kii-1-k_i 个 11。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...