题解：CF2038G Guess One Character

· · 题解

一到很有意思的思维题。

给定一个长度为 n 的 0/1 串，要求进行三次以内子串出现次数询问后确定串的任意一位是 0 还是 1。

不难想到，我们一定会去确定 s_1 或 s_n 而不是 s_{2 \sim n - 1} 中的任意一位。

不难发现性质：

如果有 a 个 0，且有 b 个 00，那么此时共有 a - b 个 0 的块（此处的块指由若干个连续的 0 组成的子串）。

一个简易的证明为：

  • 选择形成新的块：去掉两个 0，形成一个 00
  • 选择合并到前面的块：去掉一个 0，前面的块变长

不难发现以上两种操作的单次代价均为使块数 -1。

观察到，如果两个块之间没有 1 来间隔，那么这两个块应当合并为一个块。

进而发现：对于每一个 0 的块，前面都会有 1 来隔开。而第一个块的前面不一定会有 1。

此时就可以通过 10 的个数 q 与 0 的块的数量 a - b 来确定答案 s_1，如果 q < a - b，那么 s_1 为 0，否则 s_1 为 1。

注意此题为交互题，所以在输出后不要忘记 flush。

附代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    for(cin >> t; t --; )
    {
        int n, a, b, q, d;
        cin >> n;
        cout << "1 0\n";
        cout.flush();
        cin >> a;
        cout << "1 00\n";
        cout.flush();
        cin >> b;
        cout << "1 10\n";
        cout.flush();
        cin >> q;
        if(a - b - q) cout << "0 1 0\n";
        else cout << "0 1 1\n";
        cout.flush();
        cin >> d;
    }
    return 0;
}

本文来自：

另附官方题解。