题解：P7004 [NEERC 2013] Interactive Interception

CuFeO4 · 2025-02-14 17:01:15 · 题解

非常有意思的一道题。注意 q 是不变的。

允许的查询次数比较小，考虑二分。由于知道了速度 q 也无法知道位置，但知道了位置可以反推出速度 q 的范围，而且可以证明 q 可能的取值范围一直在缩小，从而考虑二分询问位置 x。

具体的，假如当前询问为 [l_{k},r_{k}]，那么最快的速度 v_{max} 就是 \max\limits_{1\le i<k}(r_k-l_i)/(k-i)，最慢的速度 v_{min} 就是 \min\limits_{1\le i<k}(l_k-r_i)/(k-i)，然后左右端点 l=l_{k}+v_{min}，r=r_{k+1}+v_{max}。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t;i += p)
#define drep(i,s,t,p) for(int i = s;i >= t;i -= p)
#ifdef LOCAL
  //auto I = freopen("in.in","r",stdin),O = freopen("out.out","w",stdout);
  auto I = stdin,O = stdout;
#else
  auto I = stdin,O = stdout;
#endif
using ll = long long;using ull = unsigned long long;
using db = double;using ldb = long double;
int p,v,L[101],R[101],t;
auto Q = [](int l,int r){cout<<"check "<<l<<' '<<r<<endl;string s;cin>>s;return (s[0] == 'Y');};
signed main(){
  cin.tie(nullptr)->sync_with_stdio(false);
  cin>>p>>v;
  int l = 0,r = p,lv = 0,rv = v;
  while(l < r){
    int mid = (l + r) >> 1;
    if(Q(l,mid)) r = mid;
    else l = mid + 1;
    for(int i = 0;i < t; ++i) 
      lv = max(lv,(l-R[i])/(t-i)),
      rv = min(rv,(r-L[i])/(t-i));
    L[t] = l,R[t] = r;
    l += lv,r += rv;
    t++;
  }
  cout<<"answer "<<l<<endl;
}