2013-2014 Northeastern European Regional Contest (NEERC 13) I. Interactive Interception（思维题 二分好题 交互）

题目

思路来源

洛谷题解

题解

100次，很容易想到是二分，但是check很难想

两个未知量p、v，因为最后要求最终位置p，

所以考虑二分位置p，用一个区间[lp,rp]去控制，

同样地，速度也用一个区间[lv,rv]去控制

那么下一个位置区间，就是由当前位置区间l、r分别加上最慢速度lv、最快速度rv去生成，

而历史每次询问出来的lp、rp，可以对lv、rv形成一个新的约束，最终收敛到lp=rp

不是很能直观地证明，只是能大概感觉，

询问的次数变多时，用限制条件去卡，速度实际是收敛的很快的

代码

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<bitset>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=105,M=1e5+5,INF=0x3f3f3f3f,mod=998244353;
int p,v,l,r,lv,rv,c,pl[N],pr[N];
char s[5];
bool in(int l,int r){
    printf("check %d %d\n",l,r);
    fflush(stdout);
    scanf("%s",s);
    return s[0]=='Y';
}
void out(int l){
    printf("answer %d\n",l);
    fflush(stdout);
}
int main(){
    sci(p),sci(v);
    l=0,r=p;
    lv=0,rv=v;
    while(l<r){
        int mid=(l+r)/2;
        if(in(l,mid))r=mid;
        else l=mid+1;
        //printf("l:%d r:%d lv:%d rv:%d\n",l,r,lv,rv);
        pl[++c]=l;
        pr[c]=r;
        rep(i,1,c-1){
            lv=max(lv,(l-pr[i])/(c-i));
            rv=min(rv,(r-pl[i])/(c-i));
        }
        l+=lv;r+=rv;
    }   
    out(l);
    return 0;
}