洛谷-P7998 [WFOI - 01] 猜数 题解
xiaoniu142857
·
·
题解
Solution
交互库自适应，也就是它会尽量使你的代码进行尽量多的交互，从而卡掉一些诸如随机化的做法。
显然我们需要通过询问不断缩小查找范围。假设当前已经确定 q\in [1,n]，如果询问 (l,r)，那么交互库返回“比 l 大”或“比 r 小”就可以使下一轮区间长度为 \max(r-1,n-l)，取到最大值。
于是有性质：询问的区间必须满足 r-1=n-l。否则可以拓展小的一边使 \max(r-1,n-l) 不变而区间长度增加，得到更优解。
$$
f_i=\min_{\left\lceil\frac{i-1}{2}\right\rceil\le j<i}f_j+\frac{1}{2j-i+2}
$$
直接跑 dp 是 $O(n^2)$ 的，期望得分 $70$。
我们可以证明代价函数满足四边形不等式。因此 dp 具有决策单调性，二分队列算法可以在 $O(n\log n)$ 复杂度内解决本题。
## Code
```cpp
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i(a);i<b;++i)
#define rept(i,a,b) for(int i(a);i<=b;++i)
#define db double
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
namespace{
constexpr int N=1e5+5;
deque<int> q;
int n,l[N],r[N],g[N];
db f[N];
}
inline const pii ask(int l,int r){
cout<<"? "<<l<<' '<<r<<endl;
pii res;
cin>>res.fi>>res.se;
return res;
}
inline void submit(int x){
cout<<"! "<<x<<endl;
exit(0);
}
inline db w(int j,int i){
return f[j]+1.0/(2*j-i+2);
}
inline int rb(int i){ // i能更新到的最右边界
return min(n,i<<1|1);
}
inline bool check(int i,int j){ // i是否能更新j
return i<j&&rb(i)>=j;
}
int main(){
cin>>n;
if(n==1) submit(1);
l[1]=2,r[1]=rb(1);
q.push_back(1);
rept(i,2,n){
while(!q.empty()&&r[q.front()]<i) q.pop_front();
g[i]=q.front();
f[i]=w(g[i],i);
while(!q.empty()&&check(i,l[q.back()])&&w(i,l[q.back()])<w(q.back(),l[q.back()])) q.pop_back();
if(q.empty()){
l[i]=i+1,r[i]=rb(i);
q.emplace_back(i);
}else if(!check(i,r[q.back()])||w(i,r[q.back()])>=w(q.back(),r[q.back()])){
if(r[q.back()]<rb(i)){
l[i]=r[q.back()]+1,r[i]=rb(i);
q.emplace_back(i);
}
}else{
int L=l[q.back()],R=r[q.back()],mid;
while(L<R){
mid=L+R>>1;
if(check(i,mid)&&w(i,mid)<w(q.back(),mid)) R=mid;
else L=mid+1;
}
r[q.back()]=L-1;
l[i]=L,r[i]=rb(i);
q.emplace_back(i);
}
}
int L=1,R=n;
while(true){
if(L==R) submit(L);
int t=R-L+1-1-g[R-L+1];
pii res=ask(L+t,R-t);
if(res.se==1) submit(res.fi);
if(res.se==0) L=res.fi+1;
else R=res.fi-1;
}
return 0;
}
```