[NOIP2012提高组] 开车旅行题解

xiao7Mr10

2026-05-09 10:27:43

发布于：重庆

9阅读

0回复

0点赞

前言

一年多前写的题解，因为当时水平不高所以学的比较细致，写的也很细致，只修改了部分不影响阅读的内容。

分析问题

对第二类问题的形式分析，发现题目给出的两类问题本质上都可以转化为以下形式再解决：

两人从城市 $s$ 为起点最多行驶长为 $X$ 的距离，他们开车行驶的距离分别是多少？

在这里，我们用 $da(s,X)$ 与 $db(s,X)$ 表示此时小 A 与小 B 行驶过的路程，以便以后续分析。

做了这样的转化后，两类问题本质如下：

询问从每个城市 $i$ 开始 $\Large \frac{da(i,X_0)}{db(i,X_0)}$ 的最大值。
多次询问 $da(s,X)$ 与 $db(s,X)$ 的值。

所以我们解决本题的关键在于快速计算 $da(s,X)$ 与 $db(s,X)$ 的值。

预处理

我们通过对问题的分析，知道了两类问题的本质。现在摆在面前的问题有两个：

小 A 和小 B 在城市 $i$ 时行驶到的下一座城市是什么。
某组问题下，两人行驶的距离分别是多少。

要解决第二个问题，就绕不开第一个问题。所以我们首先需要预处理出两人在城市 $i$ 分别行驶的下一座城市是什么，这里记作 $ga_i$ 与 $gb_i$ .

解决这个问题其实有一个力大砖飞的做法，我们开个 set 倒序处理问题，每次查找前驱和后继，但是这里介绍一个比较精妙的链表做法。

首先我们分析 $|h_i-h_j|$ 的性质，对于一个确定的 $i$ ，实际上能成为它最小值的数只有两个：第一个小于等于 $h_i$ 的数与第一个大于等于 $h_i$ 的数。这里把他们分别设为前驱 $pre_i$ 与后继 $nxt_i$ 。

为了求出前驱 $pre_i$ 与后继 $nxt_i$ 。我们不妨将 $h$ 升序排序，然后记 $rnk_i$ 表示第 $i$ 座城市的排名。

考虑求 $ga_i$ 与 $gb_i$ 的过程，此时前驱和后继都可能成为 $gb_i$ ，采用比较距离谁更小的方法进行判断。而对于 $ga_i$ 的求法就稍微复杂一点了，它的决策和 $gb_i$ 的取值有关，所以采用分类讨论来进行求解：

当 $gb_i = pre_i$ 时，说明此时的候选点可以是后继 $nxt_i$ 或者 $pre_i$ 的前驱，需要进行比较判断。
当 $gb_i = nxt_i$ 时，说明此时的候选点可以是前驱 $pre_i$ 或者 $nxt_i$ 的后继，需要进行比较判断。

int getid(int id,int x,int y){//这个函数实现了判断对应定点id，x,y两个点谁更优 
	if(!x||!y)return a[x+y].id;//注意需要判断是否存在 
	if(a[id].val-a[x].val<=a[y].val-a[id].val)return a[x].id;
	return a[y].id;
}

这样就大功告成了？其实不然，因为两人只能去往 $i$ 后面的城市 $j$ ，而刚刚的算法没有考虑到这个问题，这样就影响了答案的正确性。

这个问题其实很好解决。实际上我们需要的只是在计算第 $i$ 个城市的答案后把它的影响撤销掉，这样就可以消除对答案的影响，所以这里我们采用更为简单的双向链表的方式实现。

	for(int i = 1;i <= n;i++)pos[a[i].id]=i,a[i].pre=i-1,a[i].nxt=i+1;a[1].pre=a[n].nxt=0;//预处理rnk(这里是pos),以及链表 
	for(int i = 1;i < n;i++){//这里采用分数通分的方法解决问题 
		int id=pos[i],l=a[id].pre,r=a[id].nxt;
		if(l&&(a[id].val-a[l].val<=a[r].val-a[id].val||!r))gb[i]=a[l].id,ga[i]=getid(id,a[l].pre,r);//gb(i)=pre[i] 
		else gb[i]=a[r].id,ga[i]=getid(id,l,a[r].nxt);//gb(i)=nxt[i]
		if(l)a[l].nxt=r;//删除 
		if(r)a[r].pre=l;
	}

这个算法流程的时间复杂度为 $O(n)$ 。注意，因为我们这里排了序，所以我们求 $i$ 的答案时，链表上对应的位置实际上为 $rnk_i$ ，不要搞混了。

动态规划

现在需要求解 $da(s,X)$ 与 $db(s,X)$ 的值，这里我们考虑采用动态规划。

以 $da(s,X)$ 的转移为例，我们设 $da_{i,j,0/1}$ 表示从第 $i$ 座城市开始，行驶时间是 $j$ 天，现在是小 A 还是小 B 在开车。我们设上一座城市为 $k$ ，转移如下：

$da_{i,j,0} = da_{k,j-1,1}+|h_i-h_k|(j>1)$ 。这里表示此时小 B 和小 A 换班，然后加上城市的距离。
$da_{i,j,1} = da_{k,j-1,0}+|h_i+h_k|(j>1)$ 。这里表示此时小 A 和小 B 换班，然后加上城市的距离。

这个 dp 显然是 $O(n^2)$ 量级的，而我们查询一组 $(s,X)$ 的答案所花费的时间是 $O(n)$ 的，这并不够优秀。

优化动态规划一般我们就只从两个方向入手：优化状态设计与加速状态转移。这里我们先分析加速状态转移的做法，可以考虑采纳矩阵加速法，但是由于上一个城市的量级为 $O(n)$ ，直接使用使得这个算法反而还更劣。笔者并没有想到对应的优化方法，有方法的读者可以提出。

既然优化转移不行，那我们就从优化状态设计的角度下功夫。首先发现这三维状态好像都不省不掉的，但是可以优化表达方式。

我们考虑第一维 $i$ 和第三维 $k$ ，发现好像都不太能简化，但是第二维 $j$ 似乎可以。我们发现 $j$ 的大小与行驶的路程的大小相关，所以我们可以考虑二进制拆分的思想计算答案。

把 $j$ 改写为二进制位的形式，这样状态设计就变为了：现在行驶到了第 $i$ 座城市，行驶时间是 $2^j$ 天，现在是小 A 还是小 B 在开车。

这样我们同时需要知道 $2^j$ 天后所跳跃到的城市。同理我们也可以设 $f_{i,j,k}$ 表示对应状态所跳跃到的城市。此时三个数组的转移稍有不同，需要分析 $j=1$ 时 $k$ 的取值，转移如下：

$f_{i,j,k} = \begin{cases} f_{i,0, 1-k} &j=1 \\f_{i,f_{i,j-1,k},k} & j>1 \end{cases}$
$da_{i,j,k} = \begin{cases} da_{i,0, k}+da_{f_{i,0,k},0,1-k} &j=1 \\da_{i,j-1,k}+da_{f_{i,j-1,k},j-1,k}& j>1 \end{cases}$
$db_{i,j,k} = \begin{cases} db_{i,0, k}+db_{f_{i,0,k},0,1-k} &j=1 \\db_{i,j-1,k}+db_{f_{i,j-1,k},j-1,k}& j>1 \end{cases}$

当 $j=0$ 需要初始化，依据刚刚计算的 $ga_i,gb_i$ 处理，这部分代码如下。

	for(int i = 1;i <= n;i++){
		f[0][i][0]=ga[i],f[0][i][1]=gb[i];
		if(ga[i])da[0][i][0]=abs(a[pos[i]].val-a[pos[ga[i]]].val);
		if(gb[i])db[0][i][1]=abs(a[pos[i]].val-a[pos[gb[i]]].val);
	}//初始化 
	for(int j = 1;j <= 30;j++){
		for(int i = 1;i <= n;i++){
			for(int k = 0;k <= 1;k++){
				int num=(j==1?k^1:k);
				f[j][i][k]=f[j-1][f[j-1][i][k]][num];
				if(!f[j][i][k])continue;
				da[j][i][k]=da[j-1][i][k]+da[j-1][f[j-1][i][k]][num];
				db[j][i][k]=db[j-1][i][k]+db[j-1][f[j-1][i][k]][num];
			}
		}
	}//状态转移

实际上这就是倍增的过程，像这样利用二进制拆分来动态规划的方法我们称之为倍增优化 dp。

查询答案

查询答案就好办了。对于一组 $(s,X)$ ，我们从高到低枚举二进制位，在路程不超过 $X$ 的情况下直接跳跃即可。具体实现可以采用一个结构体存储 $da(s,X)$ 与 $db(s,X)$ 的值，此时这里需要注意转移到第 $0$ 位时开车的人。

ques calc(int st,int X){
	int dis1=0,dis2=0,op = 0;
	for(int i = 30;i >= 0;i--){
		if(dis1+dis2+da[i][st][op]+db[i][st][op]<=X&&f[i][st][op]){
			dis1+=da[i][st][op],dis2+=db[i][st][op];
			st=f[i][st][op],op=(!i?op^1:op);//注意这里由于i=0说明是另一个人开车
		}
	}return (ques){dis1,dis2};
}

这样我们单次处理一组 $(s,X)$ 的答案的复杂度为 $O(\log n)$ 。总体的时间复杂度就是 $O((n+q)\log n)$ 。总而言之是个经典题。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
struct Point{
	int val,id,nxt,pre;
}a[N];
struct ques{
	int x,y;
};
int n,m,st,X,l,lg[N],r,ga[N],gb[N],f[31][N][2],da[31][N][2],db[31][N][2];
bool cmp(Point x,Point y){
	return x.val<y.val;
}int pos[N];
int getid(int id,int x,int y){//这个函数实现了判断对应定点id，x,y两个点谁更优 
	if(!x||!y)return a[x+y].id;//注意需要判断是否存在 
	if(a[id].val-a[x].val<=a[y].val-a[id].val)return a[x].id;
	return a[y].id;
}
ques calc(int st,int X){
	int dis1=0,dis2=0,op = 0;
	for(int i = 30;i >= 0;i--){
		if(dis1+dis2+da[i][st][op]+db[i][st][op]<=X&&f[i][st][op]){
			dis1+=da[i][st][op],dis2+=db[i][st][op];
			st=f[i][st][op],op=(!i?op^1:op);
		}
	}return (ques){dis1,dis2};
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin >> n;lg[0]=-1;
	for(int i = 1;i <= n;i++)cin >> a[i].val,a[i].id=i,lg[i]=lg[i>>1]+1;sort(a+1,a+1+n,cmp);
	for(int i = 1;i <= n;i++)pos[a[i].id]=i,a[i].pre=i-1,a[i].nxt=i+1;a[1].pre=a[n].nxt=0;//预处理rnk(这里是pos),以及链表 
	for(int i = 1;i < n;i++){//这里采用分数通分的方法解决问题 
		int id=pos[i],l=a[id].pre,r=a[id].nxt;
		if(l&&(a[id].val-a[l].val<=a[r].val-a[id].val||!r))gb[i]=a[l].id,ga[i]=getid(id,a[l].pre,r);//gb(i)=pre[i] 
		else gb[i]=a[r].id,ga[i]=getid(id,l,a[r].nxt);//gb(i)=nxt[i]
		if(l)a[l].nxt=r;//这里也需要需要判断是否存在 
		if(r)a[r].pre=l;
	}
	for(int i = 1;i <= n;i++){
		f[0][i][0]=ga[i],f[0][i][1]=gb[i];
		if(ga[i])da[0][i][0]=abs(a[pos[i]].val-a[pos[ga[i]]].val);
		if(gb[i])db[0][i][1]=abs(a[pos[i]].val-a[pos[gb[i]]].val);
	}//初始化 
	for(int j = 1;j <= 30;j++){
		for(int i = 1;i <= n;i++){
			for(int k = 0;k <= 1;k++){
				int num=(j==1?k^1:k);
				f[j][i][k]=f[j-1][f[j-1][i][k]][num];
				if(!f[j][i][k])continue;
				da[j][i][k]=da[j-1][i][k]+da[j-1][f[j-1][i][k]][num];
				db[j][i][k]=db[j-1][i][k]+db[j-1][f[j-1][i][k]][num];
			}
		}
	}//状态转移 
	cin >> X >> m;
	ques ans1=calc(1,X);int id=1;
	for(int i = 2;i <= n;i++){
		ques tmp=calc(i,X);if(!tmp.y)tmp.x=1;
		if(ans1.y*tmp.x<tmp.y*ans1.x||(ans1.y*tmp.x==tmp.y*ans1.x&&a[pos[i]].val>a[pos[id]].val))id=i,ans1=tmp;
	}cout << id << "\n";
	for(int i = 1;i <= m;i++){
		cin >> st >>X;ans1=calc(st,X);
		cout << ans1.x << " " << ans1.y << "\n";
	}
	return 0;
}

有帮助，赞一个

去预览

0/2000

这里空空如也