【洛谷P1081】开车旅行【链表，倍增】

题目链接

分析

感觉这题有紫啊。

朴素的思路，预处理路程，暴力枚举会到那个城市，然后直接模拟整个过程。显然超时，复杂度 $O((n+m)\ast n^2)$。

换思路，首先，可以发现，对于某个已知的城市，且已经确定是小A/小B开车，那下一步的终点城市是唯一的。而且无论哪个询问，只要能在规定时间内求出以 $s_i$ 为起点，路程不超过 $x_i$ 公里的终点和两个人的行驶路程就行。

考虑怎么优化算法，$m$ 这一维没法优化，考虑优化成 $logn$ 级别的，考虑倍增。想想就能发现，先由小A/小B开车，开若干次车，有唯一的终点，且最多开n次车。所以设 $f[0/1][i][j]$ 表示从城市 $i$ 出发，由小A/小B先开车，开 $2^j$ 次车所到达的终点，$dis[0/1][i][j]$ 表示从城市 $i$ 出发，开 $2^j$ 次车，小A/小B开车的路程。有转移方程：
{ f [ 0 ] [ i ] [ j ] = f [ 0 ] [ f [ 0 ] [ i ] [ j − 1 ] ] [ j − 1 ] d i s [ 0 ] [ i ] [ j ] = d i s [ 0 ] [ i ] [ j − 1 ] + d i s [ 0 ] [ f [ 0 ] [ i ] [ j − 1 ] ] [ j − 1 ] d i s [ 1 ] [ i ] [ j ] = d i s [ 1 ] [ i ] [ j − 1 ] + d i s [ 1 ] [ f [ 0 ] [ i ] [ j − 1 ] ] [ j − 1 ] \left\{

\right. ⎩ ⎨ ⎧​f[0][i][j]dis[0][i][j]dis[1][i][j]​=f[0][f[0][i][j−1]][j−1]=dis[0][i][j−1]+dis[0][f[0][i][j−1]][j−1]=dis[1][i][j−1]+dis[1][f[0][i][j−1]][j−1]​
特别地 , 当 j = 1 时 , 有 { f [ 0 ] [ i ] [ 1 ] = f [ 1 ] [ f [ 0 ] [ i ] [ 0 ] ] [ 0 ] ; d i s [ 0 ] [ i ] [ 1 ] = d i s [ 0 ] [ i ] [ 0 ] ; d i s [ 1 ] [ i ] [ 1 ] = d i s [ 1 ] [ f [ 0 ] [ i ] [ 0 ] ] [ 0 ] ; 特别地,当j=1时,有\left\{

f[0][i][1]=f[1][f[0][i][0]][0];dis[0][i][1]=dis[0][i][0];dis[1][i][1]=dis[1][f[0][i][0]][0];" role="presentation" style="position: relative;">f[0][i][1]dis[0][i][1]dis[1][i][1]=f[1][f[0][i][0]][0];=dis[0][i][0];=dis[1][f[0][i][0]][0];$$\begin{array}{rl}f[0][i][1]& =f[1][f[0][i][0]][0];\\ dis[0][i][1]& =dis[0][i][0];\\ dis[1][i][1]& =dis[1][f[0][i][0]][0];\end{array}$$

\right. 特别地,当j=1时,有⎩ ⎨ ⎧​f[0][i][1]dis[0][i][1]dis[1][i][1]​=f[1][f[0][i][0]][0];=dis[0][i][0];=dis[1][f[0][i][0]][0];​
当 $j=0$ 时，我们要对两个数组进行预处理。将城市按照高度升序排序，然后建立双向链表，$l_i,r_i$ 指针分别表示按照给出顺序数第 $i$ 个城市排序后在他前面/后面的那个城市，也就是比这个城市低和高的第一个城市。

不难发现，第 $i$ 个城市下一步的目的地，一定是 $l_i,r_i,l_{l_i},r_{r_i}$ 当中的其中之一，只要枚举四个城市，看看哪个是小A/小B开车的到达地即可。但是有个限制：只能往东边走，但是这四个城市可能有在 $i$ 城市西边的。这时候就需要按照输入的时候的顺序枚举 $i$，然后每次按照上述方式求出 $f[1][i][0],dis[1][i][0],f[0][i][0],dis[0][i][0]$，然后把这个城市从链表中删去，就可以保证后面城市绝对不会走到他这里。删去的操作只需要将 $r[l[i]]=r[i],l[r[i]]=l[i]$，中间那个就被删去了。

到这里就完成了预处理部分。

查询答案的时候，对于子任务2，利用倍增的思想，从大到小枚举 $i$ ，看现在还能不能开 $2^i$ 次车，然后分别记录开车距离，更新走到的城市，这个跟求LCA有点像。对于子任务1，枚举出发城市，每次用距离算比值就行。这样总的时间复杂度就是$O((n+m)logn)$。

上代码

写了一年多啊这道题终于过了TwT。

#include
#include
#include
using namespace std;
typedef long long ll;

struct node
{
	ll h,p;
}a[100010],b[100010];

const ll inf=0x7ffffffffffff;
int n,m,x0;
ll l[100010],r[100010];
int s[100010],x[100010];
ll f[2][100010][23],dis[2][100010][23];
ll disa,disb;
double ans,mn=2147483647,mnp;

inline int cmp(node l,node r) {return l.h<r.h;}

void solve(int s,int x)//s出发，最多走x的处理 
{
	disa=disb=0;
	for(int i=20;i>=0;i--)
	{
		if(f[0][s][i]&&x>=dis[0][s][i]+dis[1][s][i])//能开就开 
		{
			disa+=dis[0][s][i];
			disb+=dis[1][s][i];
			x-=(dis[0][s][i]+dis[1][s][i]);
			s=f[0][s][i];
		}
	}
	return;
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i].h);
		a[i].p=i;
		b[i].h=a[i].h;
		b[i].p=i;
	}
	sort(b+1,b+n+1,cmp);//替换一个数组 
	l[1]=r[n]=0;
	for(int i=1;i<=n;i++)//双向链表 
	{
		l[b[i].p]=b[i-1].p;
		r[b[i].p]=b[i+1].p;
	}
	for(int i=1;i<=n;i++)//保证按输入顺序枚举(只走东边) 
	{
		/*求差值的最小值次小值及其编号 */ 
		ll fir,firp,sec,secp,tmp[5];
		fir=sec=inf/20,firp=secp=0;
		
		if(l[l[i]]) tmp[1]=a[i].h-a[l[l[i]]].h;
		else tmp[1]=inf/2;
		if(l[i]) tmp[2]=a[i].h-a[l[i]].h;
		else tmp[2]=inf/2;
		if(r[i]) tmp[3]=a[r[i]].h-a[i].h;
		else tmp[3]=inf/2;
		if(r[r[i]]) tmp[4]=a[r[r[i]]].h-a[i].h;
		else tmp[4]=inf/2;
		/*------处理小A和小B的第一步(次小,最小)-------*/ 
		for(int j=2;j<=3;j++) if(tmp[j]<fir) fir=tmp[j],firp=j;
		if(firp==2) f[1][i][0]=l[i];
		if(firp==3) f[1][i][0]=r[i];
		for(int j=1;j<=4;j++) if(j!=firp&&tmp[j]<sec) sec=tmp[j],secp=j;
		if(secp==1) f[0][i][0]=l[l[i]];
		if(secp==2) f[0][i][0]=l[i];
		if(secp==3) f[0][i][0]=r[i];
		if(secp==4) f[0][i][0]=r[r[i]];
		if(f[1][i][0]) dis[1][i][0]=fir;//第一步的距离 
		if(f[0][i][0]) dis[0][i][0]=sec;
		/*--顺序删去链表的西边城市--*/ 
		if(l[i]) r[l[i]]=r[i];
		if(r[i]) l[r[i]]=l[i];
	}
	for(int i=1;i<=n;i++)//第一步，j=0的初值 
	{
		f[0][i][1]=f[1][f[0][i][0]][0];
		dis[0][i][1]=dis[0][i][0];
		dis[1][i][1]=dis[1][f[0][i][0]][0];
	}
	for(int i=1;i<=n;i++) dis[1][i][0]=0;//第一步一定小A开 
	/*-------倍增数组预处理-------*/
	for(int j=2;j<=20;j++)
	{
		for(int i=1;i<=n;i++)
		{
			f[0][i][j]=f[0][f[0][i][j-1]][j-1];
			dis[0][i][j]=dis[0][i][j-1]+dis[0][f[0][i][j-1]][j-1];
			dis[1][i][j]=dis[1][i][j-1]+dis[1][f[0][i][j-1]][j-1];
		}
	}
	cin>>x0;
	cin>>m;
	for(int i=1;i<=m;i++) scanf("%d%d",&s[i],&x[i]);
	for(int i=1;i<=n;i++)
	{
		solve(i,x0);
		ans=(double)disa/(double)disb; 
		if(ans<mn) mn=ans,mnp=i;
	}
	cout<<mnp<<endl;
	for(int i=1;i<=m;i++)
	{
		solve(s[i],x[i]);
		cout<<disa<<' '<<disb<<endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117