CF1840G2 In Search of Truth (Hard Version) 题解

· · 题解

upd on 2025.11.14 根据要求删除部分“喵”语气词。

第一次写紫题题解喵，希望各位能阅读到最后。

首先我来解析一下题意吧。注意这个题目是交互题哦。

出题人隐藏了一个转盘，这个转盘上一共有 n 个格子并且分别写有 1 \sim n 这些数字，但是，你是不知道 n 是多少的。而且，出题人非常狡猾，这 n 个格子的顺序完全是乱的喵！转盘上当然是有一个箭头的，这个箭头一开始指向的位置，出题人是会告诉你的，就是 x！

现在，你可以指挥出题人将这个转盘进行旋转。具体来说，如果你输出 + k，表示你让出题人将这个转盘顺时针旋转 k 格；反过来，如果你输出 - k，就表示你让出题人将这个转盘逆时针旋转 k 格啦。

旋转了转盘以后，出题人会告诉你当前箭头指向的格子上写的那个数字是什么喵。你需要根据这一些乱七八糟的数据，在不超过 1000 次的操作中，准确猜出 n 是多少！如果最后你猜出来了，需要输出 ! n 哦！

题意有点复杂，希望各位好好分析分析一下喵。

接下来就是思路环节了！各位要认真看哦。讲得可能不是很好请各位原谅喵。

首先我们考虑一个简单一点的做法喵。

弄一个数值 M=10^3。

接着我们分两步：

这个方法好像不错呢，能过掉这题吗？思路没毛病，只可惜最多需要 2000 次操作机会，而题目只给了 1000 次，没办法顺利过题。但是这种方法是可以过简单版的！

接下来就只能考虑优化一下刚才的那种方法咯。

想想看，如果咱们能把 n 的范围自己整得更小一点就好了，对吧？

那咱可以先求出一个 n 的下界，假设就是 minn 吧。咋弄？不妨用点儿人类智慧，随机地来上个 M 次 + k 操作，取中间拿到的最大值就好啦。

你是不是好奇 M 是多少呀？总要知道的，但咱们等会再说。

我们肯定想设定一个范围，比方说是 [minn,minn+K]，如果咱能保证 n 在这个范围内的话，肯定就可以再用 2 \times \sqrt{K} 次机会来找出 n 了，对不？至于为什么是用这么多次——各位可别忘了刚才说的那种简单版的方法哦！

接下来就要上数学了喵。我们该如何确定了这个 M 和 K？

首先有个简单的结论：
如果固定了一个 M 值，直接取 K=(\frac{10^3-M}{2})^2 就行了，是吧？可别问我为啥，这可是在有限的操作次数里能选到的最大的 K 了！

接下来咱来算算概率。如果 n \le minn-K，那么前面随机算出的数全都 \le minn 的概率为 (\frac{minn}{n})^M。不过 n 是我们不知道的，这玩意儿有点不好算，是不是？那咱们就把概率整大点儿嘛，变成 (\frac{minn}{minn+K+1})^M 总行了，对不？因为现在这个值比前边那个大。

上面算的是错误率，那这个错误率要取怎样的 M 和 K，值才会最小呢？我们取 M=300 和 K=122500，当 minn=10^6 的时候，我们的错误率只有 10^{-17} 左右哦！这个概率这么小，完全足够你过了这题，对不对呀？

顺便讲个事儿，如果你这题没过，你可以去买彩票了，这么小的概率都给你撞上了，说明你运气很好喵！哈哈！

最后我来放上我的 AC 代码，保证对的啦！里面还有详细注释呢，保证能让你明明白白！

#include<bits/stdc++.h>
using namespace std;
const int M = 300;
const int N = 1e6+5;
const int K = 350;
//定义三个常量方便后面的使用
//M：一开始的随机跳次数
//N：转盘大小，定义数组时使用
//K：最后锁定的区间，我们取最合适的长度
int x,minn,v[N];
int main(){
    cin>>x;minn=0;
    //读入 + 初始化
    mt19937 Rand(time(0));
    //用当前时间作为随机种子
    for(int i=1;i<=M;i++){
        //一共随机 M 次
        int Move=Rand()%1000000000+1;
        //随机生成一个数值 Move
        cout<<"+ "<<Move<<"\n";fflush(stdout);
        //移动随机数 Move 步
        int now;cin>>now;minn=max(minn,now);
        //拿到当前所在位置并取最大值
    }
    cout<<"+ "<<minn<<"\n";
    //再次移动 minn 步
    fflush(stdout);cin>>x;
    //取到当前新的位置并存下来
    for(int i=1;i<=1000000;i++)v[i]=-1;v[x]=0;//初始化
    if(minn<=K){
        //如果值域较小，直接在这个范围里查
        for(int i=1;;i++){
            cout<<"+ 1\n";
            fflush(stdout);
            cin>>x;
            //每次 +1 并取到当前值
            if(v[x]!=-1){
                //如果这个位置被遍历过说明找到了
                cout<<"! "<<i-v[x]<<"\n";
                fflush(stdout);break;//输出并结束查询
            }
            v[x]=i;//存下来，证明这个位置遍历过了
        }
    }
    else{
        //否则值域范围较大，处理方式更为复杂
        for(int i=1;i<=K;i++){
            cout<<"+ 1\n";
            fflush(stdout);
            cin>>x;v[x]=i;
            //首先每次 +1 并记录位置
        }
        cout<<"+ "<<minn-K<<"\n";
        fflush(stdout);cin>>x;
        //移动 minn-K 步并更新当前位置
        for(int i=1;;i++){
            cout<<"+ "<<K<<"\n";
            fflush(stdout);cin>>x;
            //每次移动 K 步并取当前位置
            if(v[x]!=-1){
                //如果这个位置曾被遍历过
                cout<<"! "<<minn+K*i-v[x]<<"\n";
                fflush(stdout);break;
                //对应计算出答案并输出，结束查询
            }
        }
    }
    return 0;
}

如果你们觉得本篇题解还不错的话，麻烦各位点一个小小的赞，万分感谢喵！