题解：CF2280B Secret String Patterns

· · 题解

题目大意

系统有一个长度为 n 的隐藏 01 字符串 s。你需要判断这个字符串中是否存在连续的两个字符 01。

你可以向系统提问，每次询问一个区间 [l, r]，系统会返回该区间内字符 1 的个数。你最多只能询问 5 次。

如果存在 01 子串，输出 ! YES，否则输出 ! NO。

思路

如果一个字符串中不存在 01 子串，那么它一定形如：

111\dots11000\dots00

也就是说，所有的 1 都排在所有的 0 前面。

我们可以利用这个性质进行判断。假设整个字符串中 1 的总个数为 k。

  1. 第一次询问：查询整个字符串 [1, n]，得到 1 的总个数 k。

    • 如果 k = 0（全为 0）或 k = n（全为 1），显然没有 01，直接输出 ! NO。

  2. 第二次询问：查询前缀区间 [1, k]。

    • 如果这个区间里 1 的个数严格小于 k，说明前 k 个字符里混进了 0。既然总共只有 k 个 1，那么后面必然有 1 来补齐总数，这意味着在某个 0 后面出现了 1。直接输出 ! YES。

  3. 第三次询问：查询后缀区间 [k+1, n]。

    • 如果这个区间里 1 的个数大于 0 的个数，说明后 n-k 个字符里混进了 1。同理，因为前面已经用掉了一些 1，这里如果还有 1，说明前面必然有 0 。直接输出 ! YES。

  4. 如果以上两次检查都完全吻合（前 k 个全是 1，后 n-k 个全是 0），说明字符串严格符合 111...000 的形式，不存在 01，输出 ! NO。

故最多只需要进行 3 次询问即可。

代码

找上述过程模拟即可。

#include<bits/stdc++.h>
using namespace std;
int query(int l,int r) {
    cout<<"? "<<l<<" "<<r<<'\n';
    int res;
    cin>>res;
    return res;
}
int main() {
    int t;
    cin>>t;
    while(t--) {
        int n;
        cin>>n;
        int k=query(1,n);
        if(k==0||k==n) {
            cout<<"! NO\n";
            continue;
        }
        if(query(1,k)<k) {
            cout<<"! YES\n";
            continue;
        }
        if(query(k+1,n)>0) {
            cout<<"! YES\n";
            continue;
        }
        cout<<"! NO\n";
    }
}

~点个赞吧~