题解：CF2280B Secret String Patterns

· · 题解

题目传送门

题目描述

交互题。给定一个隐藏长为 N 的 01 序列，你可以每次猜测一个区间并得知其中的 1 的数量，要求在五次询问中确定这个序列中有没有 01 这个子串。

解法描述

简单题。

显然当一个序列不满足条件时所有 1 全部都在 0 前面，也就是形如 111\cdots000 这种。

那我们就可以先问整个区间里所有 1 的数量，设结果为 x，接下来只需要问 [1,x] 中 1 的数量即可。如果答案仍然为 x，那就肯定是不合法的那种形式，反之亦然。

那这道题就用两次询问搞定了。

需要注意的细节就是如果第一次查询时得到的 x 是 0 或 N 的话那就没有必要进行后一次查询了，原因显然。

以及在大多数情况下 CodeForces 对于 YES 和 NO 都是有 Special Judge 的，但是这道题没有，所以要注意一下。

AC Code

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define int long long
//#define endl '\n'
using namespace std;
int T,N;
signed main()
{
//  ios::sync_with_stdio(0);
//  cin.tie(0);
//  cout.tie(0);
    cin>>T;
    while(T--)
    {
        cin>>N;int x,y;
        cout<<"? 1 "<<N<<endl;cin>>x;
        if(x==N||!x)
        {
            cout<<"! NO"<<endl;continue;
        }
        cout<<"? 1 "<<x<<endl;cin>>y;
        if(x==y)
        {
            cout<<"! NO"<<endl;continue;
        }
        cout<<"! YES"<<endl;
    }
    return 0;
}

完结撒花！