首页 > 其他分享 >#交互,dp#洛谷 7998 [WFOI - 01] 猜数(guess)

#交互,dp#洛谷 7998 [WFOI - 01] 猜数(guess)

时间:2024-05-04 11:12:33浏览次数:29  
标签:guess 01 洛谷 int pos leq 区间 frac dp

题目传送门


分析

首先要搞清楚,交互库的自适应会让区间长度尽可能增大(答案自适应)

也就是说,如果现在区间为 \([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

相关文章

  • [oeasy]python0015_键盘改造_将esc和capslock对调_hjkl_移动_双手正位
    键盘改造......
  • 01_导论
    第1章导论什么是计量经济学计量经济学定义运用概率统计方法对经济变量之间的(因果)关系进行定量分析的科学。经济问题没法实验,计量经济学不足以确定变量间的因果;但实证的目的恰恰就是要去确定变量间的因果。因果关系如果只是对数据进行预测,那相关关系就足够了。但计量是......
  • P1525 [NOIP2010 提高组] 关押罪犯
    原题链接题解这题我采用了带权并查集的做法,0代表两囚犯处于监狱,1代表两囚犯不同监狱。根据题意,我们想让冲突值尽可能的小,那么我们要先把仇恨值大的两罪犯放在不同监狱;即按仇恨值从大到小的去判断每条仇恨信息。(贪心思想)code #include<bits/stdc++.h>usingnamespacestd;......
  • P2573 [SCOI2012] 滑雪
    原题链接题解这题乍一看好像是一道最小生成树的模板题,但如果直接找模板打会发现WA。仔细一看这题是有向图的最小生成树,可以直接套朱刘算法,but,我还不会······直接套模板的反例3321125132231所以我们再分析题目,发现只要把山的高度设为第一优先级,边的权值......
  • [分块] [Luogu AT_joisc2014_c] 历史研究
    题目描述IOI国历史研究的第一人——JOI教授,最近获得了一份被认为是古代IOI国的住民写下的日记。JOI教授为了通过这份日记来研究古代IOI国的生活,开始着手调查日记中记载的事件。日记中记录了连续\(N\)天发生的事件,大约每天发生一件。事件有种类之分。第\(i\)天发生的......
  • P2024 [NOI2001] 食物链
    原题链接题解带权并查集的应用,普通的并查集只能表示结点间的一种关系(如同一集合中的都是朋友)。而带权并查集的结点权值表示该结点与根结点的关系。相对应,带权并查集的路径压缩也复杂了一点。code #include<bits/stdc++.h>usingnamespacestd;constintN=5e4+5;intn,k......
  • [CSCCTF 2019 Qual]FlaskLight
    [CSCCTF2019Qual]FlaskLight打开环境源代码里发现可通过GET方式传入参数简单验证发现存在SSTI{{''.__class__.__mro__[2].__subclasses__()}}#可以爆出所有的类编写脚本查找可利用的类利用subprocess.Popen执行命令importrequestsimportreimporthtmlimportt......
  • Django Error: [WinError 10013] An attempt was made to access a socket in a way f
      D:\06softw-dev-202306\manage.pyrunserverWatchingforfilechangeswithStatReloaderPerformingsystemchecks...Systemcheckidentifiednoissues(0silenced).May03,2024-10:02:12Djangoversion3.2.18,usingsettings'MPDB.settings......
  • unicode编码 asis_2019_unicorn_shop
    这题就是让我们购买第四个商品当我们输入price为1337.0的时候他会报错,显示要我们只输入一个字符那么我们就要想怎样用一个字符来表示一个比1337还要大的数字答案是unicode编码(题目的名字给了提示)上这个网站我们直接查看2000的unicode编码把这个编码复制一......
  • P6123 [NEERC2016] Hard Refactoring 题解
    本题说白了,就是一道big模拟!!!题意不再赘述,我们直接看思路。这里作者借鉴了某差分思想:末尾加空格,用于判断最后一个条件;若只有\(\le\),对给出的数字和数组第一个进行标记。标记的时候要+32769,因为数组中不存在负数下标,以免越界;若只有\(\ge\),就标记给出的数字和数组最后......