专栏文章

题解：P7004 [NEERC 2013] Interactive Interception

CCuFeO4
P7004题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq9bjms
此快照首次捕获于
2025/12/04 01:04
3 个月前
此快照最后确认于
2025/12/04 01:04
3 个月前
查看原文
非常有意思的一道题。注意 qq 是不变的。
允许的查询次数比较小，考虑二分。由于知道了速度 qq 也无法知道位置，但知道了位置可以反推出速度 qq 的范围，而且可以证明 qq 可能的取值范围一直在缩小，从而考虑二分询问位置 xx。
具体的，假如当前询问为 [lk,rk][l_{k},r_{k}]，那么最快的速度 vmaxv_{max} 就是 max⁡1≤i<k(rk−li)/(k−i)\max\limits_{1\le i<k}(r_k-l_i)/(k-i)，最慢的速度 vminv_{min} 就是 min⁡1≤i<k(lk−ri)/(k−i)\min\limits_{1\le i<k}(l_k-r_i)/(k-i)，然后左右端点 l=lk+vminl=l_{k}+v_{min}，r=rk+1+vmaxr=r_{k+1}+v_{max}。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...