专栏文章

题解：CF2038G Guess One Character

MMournInk
CF2038G题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mir35zoz
此快照首次捕获于
2025/12/04 14:59
3 个月前
此快照最后确认于
2025/12/04 14:59
3 个月前
查看原文
一到很有意思的思维题。
给定一个长度为 nn 的 0/1 串，要求进行三次以内子串出现次数询问后确定串的任意一位是 0 还是 1。
不难想到，我们一定会去确定 s1s_1 或 sns_n 而不是 s2∼n−1s_{2 \sim n - 1} 中的任意一位。
不难发现性质：
如果有 aa 个 0，且有 bb 个 00，那么此时共有 a−ba - b 个 0 的块（此处的块指由若干个连续的 0 组成的子串）。
一个简易的证明为：
  • 选择形成新的块：去掉两个 0，形成一个 00
  • 选择合并到前面的块：去掉一个 0，前面的块变长
不难发现以上两种操作的单次代价均为使块数 −1-1。
观察到，如果两个块之间没有 1 来间隔，那么这两个块应当合并为一个块。
进而发现：对于每一个 0 的块，前面都会有 1 来隔开。而第一个块的前面不一定会有 1。
此时就可以通过 10 的个数 qq 与 0 的块的数量 a−ba - b 来确定答案 s1s_1，如果 q<a−bq < a - b，那么 s1s_1 为 0，否则 s1s_1 为 1。
注意此题为交互题，所以在输出后不要忘记 flush。
附代码：
CPP
#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;
}
本文来自： 做干净的奥赛
另附官方题解。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...