题解：CF1765G Guess the String

Grammar_hbw · 2026-03-04 15:21:56 · 题解

注意到 789>\frac 3 4 n，这启示我们可能要找一个期望询问次数 \frac 3 4 n 的随机做法。

先询问 2 2 直接获得 s_2。（这一步用 1 询问也行，不过由于 q 数组的性质以及 s_1=0，询问 2 2 的结果直接就是 s_2）。

• 对于每个偶数 i>2，我们先询问一次 i 位置。
• 当结果 \ge 2 时，我们直接可以得到 s_{i-1} 和 s_{i}。注意实现的时候要先对 s_{i-1} 赋值，否则在询问结果 =i-1 时你会用未赋值的 s_{i-1} 去赋 s_{i}。
• 否则，根据结果，你可以确定 s_{i}。
• 当你使用的是第一种询问时，如果 s_i=s_2，那 s_{i-1} \ne s_1，否则上一个询问的结果必然是 \ge 2 的。如果你用的是第二种询问，那这一条的等号和不等号互换。实现中可以认为第一种询问的 t=0，第二种的 t=1，根据异或的性质，这一条可以归结为 s_i = s_2 \operatorname{xor} t \Rightarrow s_{i-1} = 1 \operatorname{xor} t。也就是说，当且仅当 s_i = s_2 \operatorname{xor} t 时可以用一次询问确定这两个位置。
• 如果上一条的条件不满足，那只需要额外用一次询问 1 i-1 获得 s_{i-1}。
• 随机询问类别 t，那么对于每一个 i 都有 \frac 1 2 的概率用 1 次，\frac 1 2 的概率用 2 次。i 总共有 \frac n 2 个，那么可以得到期望询问次数 \frac 3 4 n。
• 如果 n 是奇数，额外询问 1 次。

然而，随机化做法不能只看期望，否则你会像我一样靠期望得到了一个似乎正确的做法却 WA（不是这个题）。我们还要算一下错误率。上面的做法一定能得到最后的答案，所以错误只会出现在询问次数 >789 的时候。假定 n 是偶数。n 是奇数的时候显然错误率更低。我们设询问了 x 次，那么显然有 (x-n) 组用了 2 次、(2n-x) 组用了 1 次，概率 \mathrm{C}^{x-n}_{\frac n 2} \times (\frac 1 2)^{x-n}\times (\frac 1 2)^{\frac n 2 - (x-n)}。

令 x > 789，总的错误率为

，当 n=1000 时约为 p=2 \times 10^{-4}。n 更小的点错误率只会更低。本题共 78 个测试点，则总的正确率为 (1-p)^{78} \approx 98.5 \%。如果这都不过，那你会为省选攒下大量 rp。

祝大家 rp++，正赛随机化都能过。

:::info[Code Time]

#include <bits/stdc++.h>
using namespace std;
const int N=1007;
mt19937 rnd((size_t)(random_device()()+time(0)));
int s[N],res;
int query(int tp,int x){
    cout<<(tp+1)<<' '<<x<<endl; // tp=0 的询问应该以 1 开头，tp=1 的询问应该以 2 开头。
    cin>>res;
    return res;
}
void answer(int n){
    cout<<"0 ";
    for(int i=1;i<=n;i++) cout<<s[i];
    cout<<endl;
    cin>>res; // 回答完之后需要读入一个表示该组数据正确与否的 1。
}
int main(){
    int t;
    cin>>t;
    while(t-->0){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++) s[i]=-1; // 多测清空，初始化为 -1。
        s[1]=0; // 题目要求 s[1]=0。
        s[2]=query(1,2);
        for(int i=4;i<=n;i+=2){
            int tp=rnd()&1;
            int u=query(tp,i);
            if(u>=2) s[i-1]=s[u-1]^tp,s[i]=s[u]^tp; // 一定要先赋值 i-1。
            else if(u==1) s[i]=tp;
            else s[i]=tp^1;
            if((s[i]==(s[2]^tp))&&u<2) s[i-1]=tp^1;
            if(!~s[i-1]){
                u=query(0,i-1);
                if(u) s[i-1]=s[u];
                else s[i-1]=1;
            }
        }
        if(n&1){
            int u=query(0,n);
            if(u) s[n]=s[u];
            else s[n]=1;
        }
        answer(n);
    }
}

// rp++

:::