题解：CF2280B Secret String Patterns

drac1 · 2026-11-10 15:09:11 · 题解

11.10 括号处未能指出具体什么没有，已修改。

题目大意

给定一个只有 0 和 1 的字符串长度，最多 5 次询问出这个字符串里是否有 s_i = 0 并且 s_{i+1} 的位置。

求问方式详见题目。

思路

如果没有 s_i = 0 并且 s_{i+1} 的位置，那么必然是 1 全在前面和 0 全在后面的（全 0 和全 1 是相同的情况）。

那么，我们先询问整一个数组，求出 1 有多少，如果前面恰好有那么多个 1，那么这个数组就不可能有 0 在 1 的前面这样的情况了。

注意，题目中的 5 次询问就是用来晃眼的，不要相信真需要 5 次。

最后记得按照题目要求输出即可。

#include <bits/stdc++.h>
using namespace std;
void solve();
int main() {
    // ios::sync_with_stdio(false);
    // cin.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--) solve();
    return 0;
}
#define int long long
void solve() {
    int n;
    cin >> n;
    auto input=[](int x, int y)->int {
        cout << "? " << x << " " << y << "\n";
        int a;
        cin >> a;
        return a;
    };
    int a = input(1, n);
    if (a == n || a == 0) {
        cout << "! NO\n";
        return ;
    }
    int b = input(1, a);
    if (b != a) cout << "! YES\n";
    else cout << "! NO\n";
    return ;
}