题解：CF2280B Secret String Patterns

FHQ_Treap · 2026-11-11 16:43:02 · 题解

思路

考虑什么情况下是无解的，显然当且仅当所有 1 的位置构成一个前缀。

于是我们只需要先查询 ? 1 n 得到 [1,n] 中 1 的数量 x，然后查询 ? 1 x 得到 y，分类讨论：

• 如果 x = y，那么所有 1 的位置构成一个前缀，无解；
• 如果 x \not= y，那么一定有解。

:::success[Code]

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int _;
    cin >> _;
    for(int __ = 1;__<=_;++__)
    {
        int n;
        cin >> n;
        cout << "? 1 " << n << endl;
        int x;
        cin >> x;
        if(!x)
        {
            cout << "! NO" << endl;
            continue;
        }
        cout << "? 1 " << x << endl;
        int y;
        cin >> y;
        cout << "! " << (x == y?"NO":"YES") << endl;
    }
    return 0;
}

:::

尾声

如果你也想让这篇题解被更多萌新看到，请你点一个小小的赞，助力我的文章造福更多萌新，谢谢你们！