menu ZigZagK的博客

正在努力加载中QAQ

[二分+随机]Codeforces1040D【Subway Pursuit】题解
apps Codeforces
local_offer 查看标签
comment 0 条评论
remove_red_eye 168 次访问

题目概述

交互题,现在要猜一个数 $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;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
邮箱不能为空,请填写正确格式
网址请用http://或https://开头
评论不能为空
资瓷Markdown和LaTex数学公式
keyboard_arrow_up