分析
首先要搞清楚,交互库的自适应会让区间长度尽可能增大(答案自适应)
也就是说,如果现在区间为 \([l,r]\),你选取的区间为 \([l',r']\),
那么交互库会让你的区间变成 \([l,r'-1]\) 和 \([l'+1,r]\) 中区间更长的那一个,不妨枚举这个长度
设 \(dp[i]\) 表示区间长度为 \(i\) 时的最小询问总代价,也就是要决定下一步让交互库缩短到的区间长度,设其为 \(j\)
那么就要保证 \(1\leq i-j+1\leq j\leq n\),且此时询问代价为 \(\frac{1}{j-(i-j+1)+1}=\frac{1}{2j-i}\)
那么 \(dp[i]=\min_{\lceil\frac{i+1}{2}\rceil\leq j\leq i}\{dp[j-1]+\frac{1}{2j-i}\}\)
按照最优决策点决策就能将总代价卡在能过的范围内,且 \(j\) 的选取可以将范围缩小到 \(p[i-1]\pm \Delta\),
由于并不需要非常精确地求出最小的 dp 值,所以这样预处理的复杂度就是 \(O(n\Delta)\) 的
代码
#include <iostream>
using namespace std;
const int N=100011;
double dp[N]; int n,pos[N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n,pos[1]=1;
for (int i=2;i<=n;++i){
dp[i]=i;
int L=max((i+2)>>1,pos[i-1]-800);
int R=min(i,pos[i-1]+800);
for (int j=L;j<=R;++j){
double t=dp[j-1]+1.0/(j-(i-j+1)+1);
if (dp[i]>t) dp[i]=t,pos[i]=j;
}
}
int l=1,r=n;
while (l<r){
int lmid=r-pos[r-l+1]+1,rmid=l+pos[r-l+1]-1,x,opt;
cout<<"? "<<lmid<<' '<<rmid<<'\n',cout.flush();
cin>>x>>opt;
switch (opt){
case 0:{
l=x+1;
break;
}
case 1:{
cout<<"! "<<x<<'\n';
cout.flush();
l=r=x;
break;
}
case 2:{
r=x-1;
break;
}
}
}
cout<<"! "<<l<<'\n';
cout.flush();
return 0;
}
标签:guess,01,洛谷,int,pos,leq,区间,frac,dp
From: https://www.cnblogs.com/Spare-No-Effort/p/18172107