题解：CF2280B Secret String Patterns

· · 题解

题意简述

有一个隐藏的 \texttt{01} 字符串，你可以询问至多 5 次，每次询问一个区间 l \sim r，回答 s_l \sim s_r 间 1 的数量。

最后问这个隐藏的字符串是否存在一个 i 使得 s_i = 0 且 s_{i+1} = 1。

思路

其实根本不用 5 次，两次即可。

首先正难则反，考虑什么情况下没有。很明显，只有三种情况：

否则，就一定存在了。

那么就简单了。首先询问 s_1 \sim s_n 中 1 的数量，确定总共有几个 1。然后特判前两种无解。假设有 x 个 1，然后询问 s_1 \sim s_x，如果全是 1，那就是第三种无解情况，否则有解。

参考代码


#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll T,n,x,y;
int main(){
    // 交互题不能关闭同步流
    // ios::sync_with_stdio(0);
    // cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n;
        cout<<"? 1 "<<n<<endl;
        cin>>x;
        if(!x||x==n){
            cout<<"! NO"<<endl;// 全是 0 或全是 1
            continue;
        }
        cout<<"? 1 "<<x<<endl;
        cin>>y;
        if(x==y)cout<<"! NO"<<endl;
        else cout<<"! YES"<<endl;
    }
    return 0;
}