首页 > 其他分享 >[DP] [倍增优化] Luogu P1081 [NOIP2012 提高组] 开车旅行

[DP] [倍增优化] Luogu P1081 [NOIP2012 提高组] 开车旅行

时间:2024-06-11 21:32:27浏览次数:16  
标签:10 le NOIP2012 Luogu 城市 P1081 long 行驶 text

[NOIP2012 提高组] 开车旅行

题目描述

小 \(\text{A}\) 和小 \(\text{B}\) 决定利用假期外出旅行,他们将想去的城市从 $1 $ 到 \(n\) 编号,且编号较小的城市在编号较大的城市的西边,已知各个城市的海拔高度互不相同,记城市 \(i\) 的海拔高度为\(h_i\),城市 \(i\) 和城市 \(j\) 之间的距离 \(d_{i,j}\) 恰好是这两个城市海拔高度之差的绝对值,即 \(d_{i,j}=|h_i-h_j|\)。

旅行过程中,小 \(\text{A}\) 和小 \(\text{B}\) 轮流开车,第一天小 \(\text{A}\) 开车,之后每天轮换一次。他们计划选择一个城市 \(s\) 作为起点,一直向东行驶,并且最多行驶 \(x\) 公里就结束旅行。

小 \(\text{A}\) 和小 \(\text{B}\) 的驾驶风格不同,小 \(\text{B}\) 总是沿着前进方向选择一个最近的城市作为目的地,而小 \(\text{A}\) 总是沿着前进方向选择第二近的城市作为目的地(注意:本题中如果当前城市到两个城市的距离相同,则认为离海拔低的那个城市更近)。如果其中任何一人无法按照自己的原则选择目的城市,或者到达目的地会使行驶的总距离超出 \(x\) 公里,他们就会结束旅行。

在启程之前,小 \(\text{A}\) 想知道两个问题:

1、 对于一个给定的 \(x=x_0\),从哪一个城市出发,小 \(\text{A}\) 开车行驶的路程总数与小 \(\text{B}\) 行驶的路程总数的比值最小(如果小 \(\text{B}\) 的行驶路程为 \(0\),此时的比值可视为无穷大,且两个无穷大视为相等)。如果从多个城市出发,小 \(\text{A}\) 开车行驶的路程总数与小 \(\text{B}\) 行驶的路程总数的比值都最小,则输出海拔最高的那个城市。

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

输入格式

第一行包含一个整数 \(n\),表示城市的数目。

第二行有 \(n\) 个整数,每两个整数之间用一个空格隔开,依次表示城市 \(1\) 到城市 \(n\) 的海拔高度,即 \(h_1,h_2 ... h_n\),且每个 \(h_i\) 都是互不相同的。

第三行包含一个整数 \(x_0\)。

第四行为一个整数 \(m\),表示给定 \(m\) 组 \(s_i\) 和 \(x_i\)。

接下来的 \(m\) 行,每行包含 \(2\) 个整数 \(s_i\) 和 \(x_i\),表示从城市\(s_i\) 出发,最多行驶 \(x_i\) 公里。

输出格式

输出共 \(m+1\) 行。

第一行包含一个整数 \(s_0\),表示对于给定的 \(x_0\),从编号为 \(s_0\) 的城市出发,小 \(\text A\) 开车行驶的路程总数与小 \(\text B\) 行驶的路程总数的比值最小。

接下来的 \(m\) 行,每行包含 \(2\) 个整数,之间用一个空格隔开,依次表示在给定的 \(s_i\) 和 \(x_i\) 下小 \(\text A\) 行驶的里程总数和小 \(\text B\) 行驶的里程总数。

样例 #1

样例输入 #1

4 
2 3 1 4 
3 
4 
1 3 
2 3 
3 3 
4 3

样例输出 #1

1 
1 1 
2 0 
0 0 
0 0

样例 #2

样例输入 #2

10 
4 5 6 1 2 3 7 8 9 10 
7 
10 
1 7 
2 7 
3 7 
4 7 
5 7 
6 7 
7 7 
8 7 
9 7 
10 7

样例输出 #2

2 
3 2 
2 4 
2 1 
2 4 
5 1 
5 1 
2 1 
2 0 
0 0 
0 0

提示

【样例1说明】

各个城市的海拔高度以及两个城市间的距离如上图所示。

如果从城市 \(1\) 出发,可以到达的城市为 \(2,3,4\),这几个城市与城市 \(1\) 的距离分别为 \(1,1,2\),但是由于城市 \(3\) 的海拔高度低于城市 \(2\),所以我们认为城市 \(3\) 离城市 \(1\) 最近,城市 \(2\) 离城市 \(1\) 第二近,所以小A会走到城市 \(2\)。到达城市 \(2\) 后,前面可以到达的城市为 \(3,4\),这两个城市与城市 \(2\) 的距离分别为 \(2,1\),所以城市 \(4\) 离城市 \(2\) 最近,因此小B会走到城市\(4\)。到达城市 \(4\) 后,前面已没有可到达的城市,所以旅行结束。

如果从城市 \(2\) 出发,可以到达的城市为 \(3,4\),这两个城市与城市 \(2\) 的距离分别为 \(2,1\),由于城市 \(3\) 离城市 \(2\) 第二近,所以小 \(\text A\) 会走到城市 \(3\)。到达城市 \(3\) 后,前面尚未旅行的城市为 \(4\),所以城市 \(4\) 离城市 \(3\) 最近,但是如果要到达城市 \(4\),则总路程为 \(2+3=5>3\),所以小 \(\text B\) 会直接在城市 \(3\) 结束旅行。

如果从城市 \(3\) 出发,可以到达的城市为 \(4\),由于没有离城市 \(3\) 第二近的城市,因此旅行还未开始就结束了。

如果从城市 \(4\) 出发,没有可以到达的城市,因此旅行还未开始就结束了。

【样例2说明】

当 \(x=7\) 时,如果从城市 \(1\) 出发,则路线为 \(1 \to 2 \to 3 \to 8 \to 9\),小 \(\text A\) 走的距离为 \(1+2=3\),小 \(\text B\) 走的距离为 \(1+1=2\)。(在城市 \(1\) 时,距离小 \(\text A\) 最近的城市是 \(2\) 和 \(6\),但是城市 \(2\) 的海拔更高,视为与城市 \(1\) 第二近的城市,所以小 \(\text A\) 最终选择城市 \(2\);走到\(9\) 后,小 \(\text A\) 只有城市 \(10\) 可以走,没有第二选择可以选,所以没法做出选择,结束旅行)

如果从城市 \(2\) 出发,则路线为 \(2 \to 6 \to 7\),小 \(\text A\) 和小 \(\text B\) 走的距离分别为 \(2,4\)。

如果从城市 \(3\) 出发,则路线为 \(3 \to 8 \to 9\),小 \(\text A\) 和小 \(\text B\) 走的距离分别为\(2,1\)。

如果从城市 \(4\) 出发,则路线为 \(4 \to 6 \to 7\),小 \(\text A\) 和小 \(\text B\) 走的距离分别为 \(2,4\)。

如果从城市 \(5\) 出发,则路线为 \(5 \to 7 \to 8\),小 \(\text A\) 和小 \(\text B\) 走的距离分别为 \(5,1\)。

如果从城市 \(6\) 出发,则路线为 \(6 \to 8 \to 9\),小 \(\text A\) 和小 \(\text B\) 走的距离分别为\(5,1\)。

如果从城市 \(7\) 出发,则路线为 \(7 \to 9 \to 10\),小 \(\text A\) 和小 \(\text B\) 走的距离分别为\(2,1\)。

如果从城市 \(8\) 出发,则路线为 \(8 \to 10\),小 \(\text A\) 和小 \(\text B\) 走的距离分别为\(2,0\)。

如果从城市 \(9\) 出发,则路线为 \(9\),小 \(\text A\) 和小 \(\text B\) 走的距离分别为 \(0,0\)(旅行一开始就结束了)。

如果从城市 \(10\) 出发,则路线为 \(10\),小 \(\text A\) 和小 \(\text B\) 走的距离分别为\(0,0\)。

从城市 \(2\) 或者城市 \(4\) 出发小 \(\text A\) 行驶的路程总数与小 \(\text B\) 行驶的路程总数的比值都最小,但是城市 \(2\) 的海拔更高,所以输出第一行为 \(2\)。

【数据范围与约定】

对于 \(30\%\) 的数据,有\(1\le n \le 20,1\le m\le 20\);
对于\(40\%\) 的数据,有\(1\le n \le 100,1\le m\le 100\);
对于 \(50\%\) 的数据,有\(1\le n \le 100,1\le m\le 1000\);
对于 \(70\%\) 的数据,有\(1\le n \le 1000,1\le m\le 10^4\);
对于 \(100\%\) 的数据:\(1\le n,m \le 10^5\),\(-10^9 \le h_i≤10^9\),\(1 \le s_i \le n\),\(0 \le x_i \le 10^9\)
数据保证 \(h_i\) 互不相同。

题解

本题有三个关键信息:已行驶的天数,所在城市,小A和小B各自行驶的路程长度;

若已知出发城市与天数,即可求得小A和小B各自行驶的路程长度,并且依据题意,天数还能反映谁现在在开车,所以我们可以把“天数” 作为“阶段”进行状态设计;

定义 $ f[i][j][k] $ 表示从城市 $ j $ 出发,两人共行驶 $ i $ 天,$ k $ 先开车,最终会到达的城市;

很显然,这样开会炸内存,而天数又可以随意划分,可以考虑倍增优化;

重定义 $ f[i][j][k] $ 表示从城市 $ j $ 出发,两人共行驶 $ 2^i $ 天,$ k $ 先开车,最终会到达的城市;

其中 $ 0 $ 代表小A先开车, $ 1 $ 代表小B先开车;

对于初始化,我们现在知道谁先开车,要求到那个城市,只需知道小A或小B在某一个城市时,下一个会到哪里即可,可以预处理出两个数组 $ ga[i] $ 和 $ gb[i] $ 分别表示小A在城市 $ i $ 时,下一个会到哪个城市和小B在城市 $ i $ 时,下一个会到哪个城市;

对于问题 $ 2 $,我们可以同时维护两个数组 $ da[i][j][k] $ 和 $ db[i][j][k] $ 分别表示从城市 $ j $ 出发,两人共行驶 $ 2^i $ 天,$ k $ 先开车,小A行驶的路程总长度以及小B行驶的路程总长度;

对于问题 $ 1 $,我们只需枚举出发点,找最小的即可;

则:

  1. 对于预处理

因为小A和小B只能往后走,所以我们可以从后往前遍历,并同时维护一个单调递增的序列(可以用 $ multiset $)其实应该是平衡树,但我不会,每次只需找当前节点旁边一位或两位的最小值和次小值即可(建议参考下面的代码);

  1. 对于初始化

\[f[0][j][0] = ga[j] \]

\[f[0][j][1] = gb[j] \]

  1. 对于状态转移方程

\[f[1][j][k] = f[0][f[0][j][k]][1 - k] \]

\[f[i][j][k] = f[i - 1][f[i - 1][j][k]][k] \ (i \neq 1) \]

  1. 对于 $ da $ 和 $ db $ 的初始化

\[da[0][j][0] = dis[j][ga[j]] \]

\[da[0][j][1] = 0 \]

\[db[0][j][0] = 0 \]

\[db[0][j][1] = dis[j][gb[j]] \]

对于 $ dis $ 的维护,可以在维护单调递增的序列同时顺便维护;

  1. 对于$ da $ 和 $ db $的状态转移方程

\[da[1][j][k] = da[0][j][k] + da[0][f[0][j][k]][1 - k] \ (i = 1) \]

\[da[i][j][k] = da[i - 1][j][k] + da[i - 1][f[i - 1][j][k]][k] \ (i > 1) \]

\[db[1][j][k] = db[0][j][k] + db[0][f[0][j][k]][1 - k] \ (i = 1) \]

\[db[i][j][k] = db[i - 1][j][k] + db[i - 1][f[i - 1][j][k]][k] \ (i > 1) \]

这里 $ i = 1 $ 时不同,因为 \(2^1\) 只能拆成两个$ 2^0 $ ,$ 2^0 = 1 $ 是奇数,开车的人不同,其它的是偶数,开车的人相同;

#include <iostream>
#include <set>
#include <cmath>
using namespace std;
int n;
int h[10000005];
int x0, m;
struct sss{
	long long id, he;
	bool operator <(const sss &A) const {
		return he < A.he;
	}
};
long long f[18][100005][2]; // 0 a, 1 b;
long long da[18][100005][2];
long long db[18][100005][2];
multiset<sss> p;
void init() {
	p.insert({0, 9999999999999999});
	p.insert({0, 9999999999999999});
	p.insert({n + 1, -9999999999999999});
	p.insert({n + 1, -9999999999999999}); //防止访问越界
	for (long long i = n; i >= 1; i--) {
		long long ga, gb;
		p.insert({i, h[i]});
		multiset<sss>::iterator q = p.lower_bound({i, h[i]});
		q--;
		long long lid = (*q).id, lh = (*q).he;
		q++;
		q++;
		long long rid = (*q).id, rh = (*q).he;
		q--;
		if (abs(rh - h[i]) >= abs(lh - h[i])) {
			gb = lid;
			q--; q--;
			if (abs(rh - h[i]) < abs((*q).he - h[i])) {
				ga = rid;
			} else {
				ga = (*q).id;
			}
		} else {
			gb = rid;
			q++; q++;
			if (abs((*q).he - h[i]) < abs(lh - h[i])) {
				ga = (*q).id;
			} else {
				ga = lid;
			}
		}
		f[0][i][0] = ga;
		f[0][i][1] = gb;
		da[0][i][0] = abs(h[ga] - h[i]);
		db[0][i][1] = abs(h[gb] - h[i]);
	}
}
pair<long long, long long> w(long long s, long long x) {
	long long p = s;
	long long la = 0;
	long long lb = 0;
	for (int i = 17; i >= 0; i--) {
		if (f[i][p][0] && la + lb + da[i][p][0] + db[i][p][0] <= x) {
			la += da[i][p][0];
			lb += db[i][p][0];
			p = f[i][p][0];
		}
	}
	return {la, lb};
}
int main() {
	cin >> n;
	for (long long i = 1; i <= n; i++) cin >> h[i];
	cin >> x0;
	cin >> m;
	init();
	long long tt = 10;
	for (int i = 1; i <= 17; i++) {
		for (int j = 1; j <= n; j++) {
			for (int k = 0; k <= 1; k++) {
				if (i == 1) {
					f[i][j][k] = f[0][f[0][j][k]][1 - k];
					da[i][j][k] = da[0][f[0][j][k]][1 - k] + da[0][j][k];
					db[i][j][k] = db[0][f[0][j][k]][1 - k] + db[0][j][k];
				} else {
					f[i][j][k] = f[i - 1][f[i - 1][j][k]][k];
					da[i][j][k] = da[i - 1][j][k] + da[i - 1][f[i - 1][j][k]][k];
					db[i][j][k] = db[i - 1][j][k] + db[i - 1][f[i - 1][j][k]][k];
				}
			}
		}
	}
	long double ans = 1.00 * 0x3f3f3f3f;
	long long an = 0;
	for (int i = 1; i <= n; i++) {
		pair<long long, long long> a = w(i, x0);
		long long la = a.first;
		long long lb = a.second;
		if (lb == 0) continue;
		long double d = 1.00 * la / (1.00 * lb);
		if (d < ans) {
			ans = d;
			an = i;
		} else if (d == ans) {
			if (h[an] < h[i]) an = i;
		}
	}
	cout << an << endl;
	long long a, b;
	for (int i = 1; i <= m; i++) {
		cin >> a >> b;
		pair<long long, long long> c = w(a, b);
		cout << c.first << ' ' << c.second << endl;
	}
	return 0;
}

标签:10,le,NOIP2012,Luogu,城市,P1081,long,行驶,text
From: https://www.cnblogs.com/PeppaEvenPig/p/18242763

相关文章

  • Luogu P1784 数独 [ 模板 ] / P1074 靶形数独 题解 [ 蓝 ] [ 深搜 ] [ 剪枝 ] [ 卡常
    数独模板,靶形数独卡了2h,再也不想写数独了。思路显然是对每个格子进行枚举,类似八皇后的方法去做,朴素方法是由\((1,1)\)到\((9,9)\)遍历过去。优化我们人在做数独时,会优先选择已填格数多的行、列、区域,这样可以保证尝试次数少。同样,这一点在本题中也可以应用,但是有两......
  • [lnsyoj283/luoguP1856/IOI1998]矩形周长Picture
    题意原题链接求几个矩形的周长并sol遇到几何图形的**并,都可以使用扫描线思想来解决观察易得,与x轴平行的边和与y轴平行的边相互独立,因此可以扫描两次,分别计算并累加以与x轴平行的边为例:假设有一条平行于x轴的直线从下到上扫描,每当遇到一条边时,若这条边是某个矩形的下边,则在......
  • [DP] LCS例题 Luogu P1439 【模板】最长公共子序列 Luogu P4303 基因匹配
    LuoguP1439【模板】最长公共子序列【模板】最长公共子序列题目描述给出\(1,2,\ldots,n\)的两个排列\(P_1\)和\(P_2\),求它们的最长公共子序列。输入格式第一行是一个数\(n\)。接下来两行,每行为\(n\)个数,为自然数\(1,2,\ldots,n\)的一个排列。输出格式一个数,即......
  • Luogu P2036 [COCI2008-2009 #2] PERKET
    LuoguP2036[COCI2008-2009#2]PERKET#include<bits/stdc++.h>usingnamespacestd;intn,ans=1e9+5;//ans初始化值大于所有可用食材全部使用产生的总酸度和总苦度ints[15],b[15];voiddfs(inttot,intk,intl){//k为当前酸度,l为当前甜度if(to......
  • Luogu P3366 Code
    这道题有2种解法,分别是\(Kruskal\)算法和\(Prim\)算法\(Kruskal\)算法实现方法:从小到大遍历每一条线,如果该线连接的两点已经都在树内则不处理,否则描出这条线使用并查集维护该树代码:#include<bits/stdc++.h>usingnamespacestd;constintN=2e5+5;pair<int,......
  • CSP历年复赛题-P1078 [NOIP2012 普及组] 文化之旅
    原题链接:https://www.luogu.com.cn/problem/P1078题意解读:1~n个国家,每个国家有自己的文化,不同国家文化可以相同,要从起点遍历到终点,已经学习过的文化不能重复学习,已经学习过的文化被某个文化歧视的国家也不能遍历,且不同国家之间有边,边有不同的距离,计算从起点到终点的最短路径。解......
  • B3663 [语言月赛202209] Luogu Academic
    [语言月赛202209]LuoguAcademic题目描述七海在LA群中游走,获得了一个由英文小写字符组成的字符串SSS。七海想要知道,子串luogu在其中出现了多少次。提示:一个字......
  • CSP历年复赛题-P1075 [NOIP2012 普及组] 质因数分解
    原题链接:https://www.luogu.com.cn/problem/P1075题意解读:求n的两个素因子中较大的一个。解题思路:数论的简单题,关键在于要知道一定有一个素因子不超过sqrt(n),而另一个素因子必然大于或等于sqrt(n),这样才能减少枚举时间。100分代码:#include<bits/stdc++.h>usingnamespaces......
  • [lnsyoj336/luoguP2894/USACO08FEB]Hotel
    题意原题链接给定只包含\(0\)和\(1\)的序列\(a\),支持两种操作:查询\(a\)中最靠左的连续\(x\)个元素均为\(0\)的子串,输出子串的左端点,并将这个子串的所有元素置为\(1\)将\(a\)中以\(x\)开始,长度为\(d\)的子串的所有元素置为\(0\)初始时\(a\)的所有值都为\(0\)sol区间修改,区......
  • Smart - Luogu —— 智能的洛谷
    目录安装Stylus谷歌Edge安装Smart-Luogu使用尾声安装Styluslink点击推荐下载,获取crx文件谷歌先点击右上角三个点,再点击扩展程序,然后点击管理扩展程序,进入管理扩展界面,把开发者模式选上,把crx文件拖入即可Edge先点击右上角三个点,再点击扩展,然后点击管理扩展程序,进入......