[二分+随机]Codeforces1040D【Subway Pursuit】题解

Author Avatar
ZigZagK 2018年9月8日 10:58
remove_red_eye 17

题目概述

交互题,现在要猜一个数 $x$ ,可以询问 $x$ 是不是 $l\le x\le r$ ,但是每次询问完成后 $x$ 会移动一个到距离 $\le K$ 的点。如果一次询问 $(l,l)$ 时 $x=l$ ,则猜中了,在 $4500$ 次内猜中。

解题报告

假如上一次在 $[L,R]$ 之间,那么很明显可以这样:取 $mid={L+R\over 2}$ ,然后问 $(L,mid)$ ,如果问到了那么下一次的区间就是 $[L-K,mid+K]$ ,否则 $[mid+1-K,R+K]$ 。

但是……这样永远都停不下来啊?很明显如果 $x$ 在一个小范围内反复跳跃根本不可能刚好问到 $x$ 啊?

你随机我也随机,就是这么扯皮……如果 $R-L\le 4K$ 因为 $K$ 不大,那么就随机一个 $pos$ 问 $(pos,pos)$ ,如果没问到就 $[L-K,R+K]$ 继续做。

示例程序

第一发没过……随便改了个随机种子就过了……

#include<cstdio>
#include<cstdlib>
using namespace std;
typedef long long LL;

int K;LL n,L,R,now;

inline bool Ask(LL L,LL R){
    printf("%lld %lld\n",L,R);fflush(stdout);char s[5];scanf("%s",s);
    if (s[0]=='Y') return true;return false;
}
int main(){
    srand(759405);scanf("%lld%d",&n,&K);L=1;R=n;
    for (LL mid=L+(R-L>>1);;mid=L+(R-L>>1)){
        if (R-L<=(K<<2)) {now=rand()%(R-L+1)+L;if (Ask(now,now)) return 0;L-=K;R+=K;}
        else if (Ask(L,mid)) L-=K,R=mid+K; else L=mid+1-K,R+=K;if (L<1) L=1;if (R>n) R=n;
    }return 0;
}

本文链接:https://zigzagk.top/2018/09/08/CF1040D
本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0 CN 许可协议。转载请注明作者和出处QwQ。