M_sea

CF1039B Subway Pursuit
CodeForcesLuogu分析交互题一般都是二分。二分一个可能的区间,然后逐渐缩小范围,缩到差不多时就随机一个...
扫描右侧二维码阅读全文
31
2018/10

CF1039B Subway Pursuit

CodeForces

Luogu

分析

交互题一般都是二分。

二分一个可能的区间,然后逐渐缩小范围,缩到差不多时就随机一个位置。

缩小范围时要考虑到列车的移动。

然后外面套个while(1),如果你不是特别非的话基本可以水过去。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
typedef int mainint;
#define int long long
using namespace std;

char tmp[110];

inline int ok(int l,int r) {
    cout<<l<<" "<<r<<endl;
    fflush(stdout);
    cin>>tmp+1;
    return tmp[1]=='Y';
}

mainint main() {
    srand(19260817); srand(rand());
    int n,k; cin>>n>>k;
    int L=1,R=n;
    while (1) {
        while (R-L>50+rand()%25) {
            int mid=(L+R)>>1;
            if (ok(L,mid)) R=mid;
            else L=mid+1;
            L=max(1ll,L-k),R=min(n,R+k);
        }
        int p=rand()%(R-L+1)+L;
        if (ok(p,p)) return 0;
        L=max(1ll,L-k),R=min(n,R+k);
    }
    return 0;
}
最后修改:2018 年 11 月 09 日 06 : 18 PM

发表评论