洛谷-P7998 [WFOI - 01] 猜数 题解

文章洛谷-P7998 [WFOI - 01] 猜数 题解分享给大家，欢迎收藏极客资料网，专注分享技术知识

Solution

交互库自适应，也就是它会尽量使你的代码进行尽量多的交互，从而卡掉一些诸如随机化的做法。

显然我们需要通过询问不断缩小查找范围。假设当前已经确定 \(q\in [1,n]\)，如果询问 \((l,r)\)，那么交互库返回“比 \(l\) 大”或“比 \(r\) 小”就可以使下一轮区间长度为 \(\max(r-1,n-l)\)，取到最大值。

于是有性质：询问的区间必须满足 \(r-1=n-l\)。否则可以拓展小的一边使 \(\max(r-1,n-l)\) 不变而区间长度增加，得到更优解。

\(1.9813035\) 这样的奇怪限制启发我们考虑 dp。设 \(f_i\) 为长度为 \(i\) 的区间确定唯一值的最小代价。若一次询问后区间长度缩减到 \(j\)，则 \(l=i-j-1,r=j+1\)。于是转移方程为：

直接跑 dp 是 \(O(n^2)\) 的，期望得分 \(70\)。

我们可以证明代价函数满足四边形不等式。因此 dp 具有决策单调性，二分队列算法可以在 \(O(n\log n)\) 复杂度内解决本题。

Code

#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;
}

文章来源:https://www.cnblogs.com/xiaoniu142857/p/20045596
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！