题解：CF2280B Secret String Patterns

· · 题解

题目传送机

思路

经过思考，不难发现，当整个字符串都是 1 或都是 0 时，绝对不存在子串 01。

所以我们可以先询问 s_1 到 s_n 之间 1 的数量，记作 k ，如果整个字符串都是 1 或都是 0 时，就输出 ! NO。

当整个字符串中既有 1，又有 0 时，我们可以发现，如果所有 0 都在末尾，也绝对不存在子串 01。

所以我们只需再询问 s_{k+1} 到 s_n 之间 1 的数量， 如果 s_{k+1} 到 s_n 之间全都是 0 时，即字符串中的所有 0 都在末尾时，就输出 ! NO。

如果 s_{k+1} 到 s_n 之间存在至少 1 个 1 时，就代表整个字符串中至少存在 1 个子串 01，此时我们输出 ! YES。

代码还是比较简单的，只需按照上文模拟即可。

代码

#include<bits/stdc++.h>
using namespace std;
    long long a,b,c,d,e,w,k,j;
int main(){
    cin>>w;
    while(w--){
        cin>>a;
        cout<<"?"<<" "<<1<<" "<<a<<"\n";
        cin>>k;
        if(k==a){
            cout<<"! NO\n";
        }else{
            cout<<"?"<<" "<<k+1<<" "<<a<<"\n";
            cin>>j;
            if(j==0){
                cout<<"! NO\n";
            }else{
                cout<<"! YES\n";
            }
        }
    }
    return 0;
}