洛谷-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\)。于是转移方程为：

\[f_i=\min_{\left\lceil\frac{i-1}{2}\right\rceil\le j

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

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

Code

#include 
#define rep(i,a,b) for(int i(a);i
#define fi first
#define se second
using namespace std;
namespace{
    constexpr int N=1e5+5;
    deque q;
    int n,l[N],r[N],g[N];
    db f[N];
}
inline const pii ask(int l,int r){
    cout<<"? "<>res.fi>>res.se;
    return res;
}
inline void submit(int x){
    cout<<"! "<=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()]=w(q.back(),r[q.back()])){
            if(r[q.back()]>1;
                if(check(i,mid)&&w(i,mid)

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

Solution

Code

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