题解：CF2280B Secret String Patterns

· · 题解

题目大意

有一个长度为 n 的隐藏二进制字符串 s。每次可以询问一个区间 [l,r] 中有多少个 1。

最多询问 5 次，判断字符串中是否存在相邻的 01。

解题思路

其实不同于另一篇题解，这题只要询问 2 次就能确定答案了。

首先如果字符串里没有 01，那么所有的 1 肯定都在 0 前面，形如：

111...111000...000

先询问整个字符串，假设一共有 k 个 1。如果 k=0 或 k=n，所有字符都相同，也就不可能有 01，直接回答 NO。否则就询问前 k 个位置里有多少个 1。

如果前 k 个位置都是 1，后面就只能是 0，答案为 NO。否则说明有 1 跑到了某个 0 的后面，字符串中一定存在相邻的 01，答案为 YES。这样最多询问 2 次，满足题目要求。

AC 代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        cout<<"? 1 "<<n<<endl;
        int k;
        cin>>k;
        if(k==-1) return 0;
        if(k==0 || k==n) // 没有 1 或者没有 0
        {
            cout<<"! NO"<<endl;
            continue;
        }
        cout<<"? 1 "<<k<<endl; // 查询前 k 个
        int cnt;
        cin>>cnt;
        if(cnt==-1) return 0;
        if(cnt==k) // 所有 1 都在前面
            cout<<"! NO"<<endl;
        else
            cout<<"! YES"<<endl;
    }
    return 0;
}