题解 P1081 【开车旅行】

· · 题解

为了通过提高试炼场的倍增关，被迫做紫题/kel……（yrz菜菜……）

（特别鸣谢：本题解由《算法竞赛进阶指南》赞助播出，《算法竞赛进阶指南》，一本你值得拥有的算法好书！）

刚才一不小心把这个题的方法暴露了呢……没错，这个题的main idea就是：倍增！

倍增，字面意思就是“成倍增长”，也许你听说过在国际象棋棋盘上摆放麦粒的故事，体验了指数函数爆炸级别的恐怖，也在快速幂，ST表和最近公共祖先LCA中领略到这些高效的算法的神奇

没错，上面的东西都是倍增思想的具体体现

那这个题到底是怎么跟倍增的技巧扯上关系的呢？？？别急，咱们一步一步来，从分析题目开始！

Part I

记城市 i 的海拔高度为h_i ，城市 i 和城市 j 之间的距离 d_{i,j} 恰好是这两个城市海拔高度之差的绝对值，即 d_{i,j}=|h_i-h_j|。

小 \text{B} 总是沿着前进方向选择一个最近的城市作为目的地，而小 \text{A} 总是沿着前进方向选择第二近的城市作为目的地 。

看来，小\text{A}和小\text{B}下次到达的城市是非常重要的，赶紧把它预处理出来！

也就是说，我们要预处理出在城市i的时候，小\text{A}要走的城市ga_i和小\text{B}要走的城市gb_i

那怎么预处理呢？？？不难想到，$gb_i$就是**离当前的$i$的高度最接近的城市**，我们先给每个城市按高度排个序，这样的话，排序之后**要求的$gb_i$就是$i-1$和$i+1$中，和$i$的高度差更小的那个** 而$ga_i$就同理啦，根据刚才的思路，$ga_i$肯定是$i-1,i-2,i+1,i+2$其中之一，这四个里面肯定有一个是$gb_i$，再从剩下三个里面找个小的就是$ga_i$了 怎么找的问题解决了，但还有一个重要的事情没考虑——每次必须去往**前进方向**的城市，这该怎么办呢？ 咱们先从城市$1$来考虑，毕竟从城市$1$出发，哪个城市都能到嘛！找到排序后城市$1$的位置，然后按照刚才说的比较大小，就可以找到$gb_1$和$ga_1

那i=2的时候呢？

完全没有问题！我们就用这种**弄完一个删一个**的方式，这样就可以保证当前要考虑的城市里只有前进方向的城市，因为当一个城市处理过去之后，它就再也不能到达了 那这波操作具体怎么实现呢？既然**要资瓷频繁的删除操作**，开动脑筋想一想，用**双向链表**是更好不过了（没学过双向链表的同学们可以去 [P1160 队列安排](https://www.luogu.com.cn/problem/P1160)） 接下来，让我们开始愉快地写代码吧！虽然双向链表的实现还是挺基础的，但是**要注意的细节和坑还是挺多的**（要不然我为啥光双向链表就调了一晚上），尤其是要注意**判定当前元素的前驱和后继不存在的情况** ```cpp struct qwq{//存储城市的结构体 int hi,id;//hi为城市的海拔高度，id为城市的序号 int pre,nxt;//pre和next是链表的象征！ }h[100005]; bool cmp(qwq x,qwq y){//排序用的cmp函数 return x.hi<y.hi;//按高度从小到大排 } int pos[100005],ga[100005],gb[100005];//pos为城市排序后所在的位置，ga和gb就是我们要求的东西 ``` ```cpp scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&h[i].hi);//输入就不用说了吧 h[i].id=i;//城市的编号 } sort(h+1,h+1+n,cmp);//排个序 for(int i=1;i<=n;i++){ pos[h[i].id]=i;//把pos数组整出来 h[i].pre=i-1;//用链表把城市串一串 h[i].nxt=i+1; } h[1].pre=h[n].nxt=0;//把头部的前驱和尾部的后继（边界部分）搞成0 for(int i=1;i<n;i++){ int p=pos[i],p1=h[p].pre,p2=h[p].nxt; //把当前的城市以及它的前驱和后继都找出来，方便后续操作 if(p1&&(h[p].hi-h[p1].hi<=h[p2].hi-h[p].hi||!p2))//如果当前城市i到p1的距离比到p2的小，或者干脆没有p2只能选p1（选择p1必须保证p1是存在的，切记注意） gb[i]=h[p1].id,ga[i]=choose(h[p1].pre,p2,p);//那gb就当然选p1啦，ga的话就从那两个里面选（怎么选马上就讲） else gb[i]=h[p2].id,ga[i]=choose(p1,h[p2].nxt,p);//否则呢，就反过来，gb选p2，ga从p1和p2的后继中选 del(p);//弄完了就把它删掉，反正以后都到不了了 } ``` ```cpp int choose(int a,int b,int i){//当前城市为i，从a与b中选择一个更优的 if(!a)return h[b].id;//如果其中一个城市没有，那就只能被迫选另一个了 if(!b)return h[a].id;//俺也一样，注意返回的是id if(h[i].hi-h[a].hi<=h[b].hi-h[i].hi)//如果城市i与a的高度差比i与b的小 return h[a].id;//那就选a咯 else return h[b].id;//要不就是b } void del(int pos){//双向链表基本操作——删除链表中的元素 if(h[pos].nxt)h[h[pos].nxt].pre=h[pos].pre;//连这个都不会的话可以去双向链表入门题回炉重造了 if(h[pos].pre)h[h[pos].pre].nxt=h[pos].nxt;//如果实在理解不了的话可以画个图，还是很好理解的 } ``` （话说这一步的实现用STL大法中的**set+迭代器**也珂以实现，（~~据说你甚至可以手写平衡树~~），由于本人写set迭代器屡屡出锅，这里就不给大家展示了） ------------ ## Part II 对题目分析的第一步完美结束，我们接着来看： >1、 对于一个给定的 $x=x_0

，从哪一个城市出发，小 \text{A} 开车行驶的路程总数与小 \text{B} 行驶的路程总数的比值最小

2、对任意给定的 x=x_i 和出发城市 s_i ，小 \text{A} 开车行驶的路程总数以及小 \text {B} 行驶的路程总数。

我们发现，题目中要求的东西跟到达的城市，小 \text{A} 走的路程和小 \text{B} 走的路程

那怎么搞到这些信息呢？我们只需要知道出发的城市和行驶的天数，哦对了，还有轮到谁开车

那我们就一天一天的开，去模拟开车过程？

别忘了数据范围辣么大，他俩有时候开上十天半个月也开不完，怎么办呢？

反手一个倍增，闷声发大财！

为啥用倍增就可以呢？因为通过倍增枚举，是将每次把一个数变成它相应的两倍，也就是说：

\text{用倍增枚举：}1,2,4,8,16,32,64,128,256,512,1024\cdots\end{aligned}}

这简直快的不是一点半点啊！

领教到倍增的威力之后，我们来看看接下来怎么做，根据刚才说的，我们是通过已知条件推出新的状态，也就是说，这是一个dp，或者说是递推的过程

动态规划需要考虑三件事：数组、方程、初始化

—— \text{v\color{red}ectorwyx}

首先是考虑状态定义的问题，根据刚才推出的关键信息，我们分别要定义三个数组——f表示走到的城市，da表示小A走过的距离，db表示小\text{B}走过的距离

并且，决定这三者的因素在前面也说过了，我们就用f_{i,j,k}表示开车2^i天（说好的倍增呐），从城市j出发到达的城市，k=0表示轮到小\text{A}先开车，k=1表示轮到小\text{B}先开车

同样，da_{i,j,k}和db_{i,j,k}也是这么定义的！

接下来，咱们来考虑初始化的问题：

f_{0,j,0}=ga_j f_{0,j,1}=gb_j

（很好理解，2^0是1，开一天之后到达的就是我们刚才预处理出的ga和gb）

da_{0,j,0}=|h_j-h_{ga_j}|

（第一次会走到ga_j，路程就是它俩的距离）

da_{0,j,1}=0

（小\text{B}压根啥也没走）

我们再来考虑状态转移方程：

其实倍增的状态转移还是比较套路的，无非就是对“前一半”和“后一半”进行处理

当然这里还有一个坑点：特判 i=1 的情况

为啥呢？咱以f数组为例分析一下分析一下

当i=1时，2^i=2，所以我们要分析前1天和后1天的情况，这两天是由不同的人开，所以：

f_{i,j,k}=f_{i-1,(f_{i-1,j,k}),k \mathrm{xor} 1}(i=1)

（\mathrm{xor}就是异或啦，用来把k变成相反的）

当i>1时，2^{i-1}是个偶数，所以前后两段是同一个人开车，因此：

f_{i,j,k}=f_{i-1,(f_{i-1,j,k}),k}(i>1)

这样我们就把f数组的转移写完了，da和db可以如法炮制：行驶的总路程=前半段走的路程+后半段走的路程

da_{i,j,k}=\begin{cases}da_{i-1,j,k}+da_{i-1,({f_{i-1,j-1,k}),k \mathrm{xor} 1}}(i=1)\\da_{i-1,j,k}+da_{i-1,({f_{i-1,j-1,k}),k }}(i>1)\end{cases} db_{i,j,k}=\begin{cases}db_{i-1,j,k}+db_{i-1,({f_{i-1,j-1,k}),k \mathrm{xor} 1}}(i=1)\\db_{i-1,j,k}+db_{i-1,({f_{i-1,j-1,k}),k }}(i>1)\end{cases}

我们发现，i=1的时候，除了k要取相反，其它压根没啥区别，所以写代码的时候，特判i=1时取反，其它照写就行啦！

    int f[25][100005][2];
    long long da[25][100005][2],db[25][100005][2];//十年OI一场空，不开long long见祖宗！
    for(int i=1;i<=n;i++){
        if(ga[i]){//预处理的时候一定要注意只有这个东西存在的时候才能预处理
            f[0][i][0]=ga[i];
            da[0][i][0]=abs(h[pos[i]].hi-h[pos[ga[i]]].hi);//注意我们在前面已经将h数组排好了序，所以别忘了取pos
            db[0][i][0]=0;  
        }
        if(gb[i]){//另一边的初始化对称过来即可
            f[0][i][1]=gb[i];
            da[0][i][1]=0;
            db[0][i][1]=abs(h[pos[i]].hi-h[pos[gb[i]]].hi);
        }   
    }
    t=(int)(log(1.0*n)/log(2)+1);//倍增时只需要枚举到log2n就可以，所以要先把它算出来，用的是对数的换底公式：logab=logcb/logca
    for(int i=1;i<=t;i++){//循环顺序很重要！一定要先枚举天数，再枚举城市，这样才能保证后面要用的东西前面已经推出来了
        for(int j=1;j<=n;j++){
            for(int k=0;k<=1;k++){
                int l=(i==1)?k^1:k;//当k=1时，别忘了取相反
                if(f[i-1][j][k])f[i][j][k]=f[i-1][f[i-1][j][k]][l];//递推f数组
                if(f[i][j][k]){//别忘了必须保证存在
                    da[i][j][k]=da[i-1][j][k]+da[i-1][f[i-1][j][k]][l];//按照刚才推出的转移方程递推
                    db[i][j][k]=db[i-1][j][k]+db[i-1][f[i-1][j][k]][l];
                }
            }
        }
    }

Part III

该推的都推完啦，我们接下来要考虑的，就是如何用我们推出的东西，得到最终的答案

也就是说，我们的首要任务就是计算出calc(s,x)，也就是从城市s出发，最多走x的距离，小\text{A}和小\text{B}能走的距离la和lb

那咋办呢？我们可以借鉴倍增求LCA的思路：从大到小往上跳

也就是说：我们按照i从大到小枚举，如果走完2^i天，总路程还是不超过x呢，那就走过去，更新la和lb的答案

没错，就这么简单，我们来把代码写出来！

long long da[25][100005][2],db[25][100005][2],la,lb;//再次提醒：十年OI一场空，不开long long见祖宗！
void calc(int s,long long x){
    la=lb=0;//不要忘了初始化哦！
    int k=0;//k依然表示谁先开车
    for(int i=t;i>=0;i--){//从大往小枚举，看看能不能跳
        if(f[i][s][k]&&da[i][s][k]+db[i][s][k]<=x){//如果当前城市存在，并且走完这些天还是超不过x
            x-=da[i][s][k]+db[i][s][k];//剩余路程减去走了的路程
            la+=da[i][s][k],lb+=db[i][s][k];//把新走的路程加到统计的答案里去
            if(!i)k^=1;//别忘了i=0的时候依然要取相反
            s=f[i][s][k];//跳的终点的城市里去
        }
    }
}

回到题目，第一问就是要求出对于给定的x，从哪个s出发，la和lb的比值最小，而第二问呢，实际上就是让你计算calc(s,x)时la和lb的值

    long long x;
    int s;
    scanf("%lld",&x);//第一问：找到一个s使la:lb最小
    int p=0;//p代表最后找到的城市s
    long long ansa=1,ansb=0;//ansa和ansb是找到的比值最小的la和lb
    for(int i=1;i<=n;i++){//枚举每个城市
        calc(i,x);//计算出小A和小B的路程
        if(!lb)la=1;//题目要求：如果lb为0，那就变成1
        if(la*ansb<lb*ansa||(la*ansb==lb*ansa&&h[pos[i]].hi>h[pos[p]].hi))//由于比例的分数算除法会产生玄学的精度问题，所以我们把它换成乘积的形式，除此以外，比值相等时选择高度较高的一个
        ansa=la,ansb=lb,p=i;//更新答案
    } 
    printf("%d\n",p);//找到答案输出
    int m;
    scanf("%d",&m);
    while(m--){
        scanf("%d%lld",&s,&x);
        calc(s,x);//直接计算calc(s,x)就行
        printf("%lld %lld\n",la,lb);
    }
    return 0;

Part IV

上完整代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
struct qwq{//存储城市的结构体以及cmp
    int hi,id,pre,nxt;
}h[100005];
bool cmp(qwq x,qwq y){
    return x.hi<y.hi;
}
int choose(int a,int b,int i){//选择更优解
    if(!a)return h[b].id;
    if(!b)return h[a].id;
    if(h[i].hi-h[a].hi<=h[b].hi-h[i].hi)
    return h[a].id;
    else return h[b].id;
}
void del(int pos){//删除链表元素
    if(h[pos].nxt)h[h[pos].nxt].pre=h[pos].pre;
    if(h[pos].pre)h[h[pos].pre].nxt=h[pos].nxt;
}
int n,t;
int pos[100005],ga[100005],gb[100005];//一堆变量
int f[25][100005][2];
long long da[25][100005][2],db[25][100005][2],la,lb;
void calc(int s,long long x){//calc函数
    la=lb=0;
    int k=0;
    for(int i=t;i>=0;i--){
        if(f[i][s][k]&&da[i][s][k]+db[i][s][k]<=x){
            x-=da[i][s][k]+db[i][s][k];
            la+=da[i][s][k],lb+=db[i][s][k];
            if(!i)k^=1;
            s=f[i][s][k];
        }
    }
}
int main(){
//Part I——预处理ga和gb                                                   
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&h[i].hi);
        h[i].id=i;
    }
    sort(h+1,h+1+n,cmp);
    for(int i=1;i<=n;i++){
        pos[h[i].id]=i;
        h[i].pre=i-1;
        h[i].nxt=i+1;
    }
    h[1].pre=h[n].nxt=0;
    for(int i=1;i<n;i++){
        int p=pos[i],p1=h[p].pre,p2=h[p].nxt;                                  
        if(p1&&(h[p].hi-h[p1].hi<=h[p2].hi-h[p].hi||!p2))      
        gb[i]=h[p1].id,ga[i]=choose(h[p1].pre,p2,p);
        else gb[i]=h[p2].id,ga[i]=choose(p1,h[p2].nxt,p);   
        del(p);
    }
//Part II——用倍增推出f,da,db                                                         
    for(int i=1;i<=n;i++){
        if(ga[i]){
            f[0][i][0]=ga[i];
            da[0][i][0]=abs(h[pos[i]].hi-h[pos[ga[i]]].hi);
            db[0][i][0]=0;  
        }
        if(gb[i]){
            f[0][i][1]=gb[i];
            da[0][i][1]=0;
            db[0][i][1]=abs(h[pos[i]].hi-h[pos[gb[i]]].hi);
        }   
    }
    t=(int)(log(1.0*n)/log(2)+1);
    for(int i=1;i<=t;i++){
        for(int j=1;j<=n;j++){
            for(int k=0;k<=1;k++){
                int l=(i==1)?k^1:k;
                if(f[i-1][j][k])f[i][j][k]=f[i-1][f[i-1][j][k]][l];
                if(f[i][j][k]){
                    da[i][j][k]=da[i-1][j][k]+da[i-1][f[i-1][j][k]][l];
                    db[i][j][k]=db[i-1][j][k]+db[i-1][f[i-1][j][k]][l];
                }
            }
        }
    }
// Part III——计算calc得到答案                                  
    long long x;
    int s;
    scanf("%lld",&x);
    int p=0;
    long long ansa=1,ansb=0;
    for(int i=1;i<=n;i++){
        calc(i,x);
        if(!lb)la=1;
        if(la*ansb<lb*ansa||(la*ansb==lb*ansa&&h[pos[i]].hi>h[pos[p]].hi))
        ansa=la,ansb=lb,p=i;
    } 
    printf("%d\n",p);
    int m;
    scanf("%d",&m);
    while(m--){
        scanf("%d%lld",&s,&x);
        calc(s,x);
        printf("%lld %lld\n",la,lb);
    }
    return 0;
}
\color{#4275f5}{\text{yrz 是小珂愛！！！}}