抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

一方の笔记本

The only source of knowledge is experience.

博客

随笔

朋友

归档

关于

算法分析与设计第三次作业题解

算法学习题解课业

发布于：2021年10月11日

次浏览

题目发布于2021年10月11日零点。

Problem A

题目描述

我们有\(n\)根的木棍。现在从这些木棍中切割出来\(m\)条长度相同的木棍，问这\(m\)根木棍最长有多长？

题解

实际上就是切绳子的问题，直接贴代码。注意\(r\)要足够大，\(l\)最好不要取负数

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
#include <vector>
#include <iostream>
using namespace std;
bool isOk(vector<int>&length, int mid, int k) {
	for (int i = 0; i < length.size(); i++) {
		k -= length[i] / mid;
	}
	return k <= 0;
}

int main() {
	int n, k;
	cin >> n >> k;
    vector<int> length(n);
	int max_len = 0;
	for (int i = 0; i < n; i++) {
		double temp;
		cin >> temp;
		length[i] = temp * 100;
		max_len = max(max_len, length[i]);
	}
	int l = 1, r = 1000000000;
	int ans = 0;
	while (l <= r) {
		int mid = (l + r) / 2;
		if (isOk(length, mid, k)) {
			ans = max(mid, ans);
			l = mid + 1;
		}
		else {
			r = mid - 1;
		}
	}
	cout << fixed << setprecision(2);
	cout << ans / 100.0 << endl;
	return 0;
}

Problem B

题目描述

有一条河，河中间有一些石头，已知石头的数量和相邻两块石头之间的距离。现在可以移除一些石头，问最多移除\(m\)块石头后（首尾两块石头不可以移除），相邻两块石头之间的距离的最小值最大是多少。

输入数据

第一行输入两个数字，\(n(2 \leq n \leq 1000)\)为石头的个数，\(m(0 \leq m \leq n-2)\)为可移除的石头数目，随后\(n-1\)个数字，表示顺序和相邻两块石头的距离\(d(d \leq 1000)\)。

题解

这个题乍看很迷惑，事实上这个题可以用二分查找进行解决。逆向思考，判断任意两块石头之间的距离均大于等于\(d\)时，移除石头数\(f(d)\)是否满足\(f(d) \leq m\)。直接使用 vector 可以避免用 list 删除时的各种麻烦。

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
#include <bits/stdc++.h>
using namespace std;
bool valid(int mid, vector<int>& stones, int m);
int main() {
	int n, m;
	int _max = 0;
	cin >> n >> m;
	vector<int> stones(n + 1, 0);
	for (int i = 2; i <= n; i++) {
		int temp;
		cin >> temp;
		stones[i] = stones[i - 1] + temp;
	}
	int l = 0, r = 100000000;
	while (l < r - 1) {
		int mid = (l + r) / 2;
		if (valid(mid, stones, m)) {
			l = mid;
		}
		else {
			r = mid;
		}
	}
	cout << l << endl;
	return 0;
}
/*
我的思路：
逐个遍历stones，遇到小的就优先和后面的合并
总保证当前指针的位置之前都是合法的
*/
bool valid(int mid, vector<int>&stones, int m) {
	int count = 0, back = 2, fr = 1;
	while (back < stones.size()) {
		int d = stones[back] - stones[fr];
		while (d < mid) {
			back++;
			count++;
			if (count > m) {
				return false;
			}
			if (back == stones.size()) {
				return fr != 1;
			}
			d = stones[back] - stones[fr];
		}
		fr = back;
		back++;
	}
	return true;
}

Problem C

题目描述

楼梯有n阶，可以一步上一阶、两阶或三阶，问有多少种不同的走法。由于答案很大，模\(10^9+7\)输出。

题解

动态规划可解的题目，比较基础。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int main(){
	int n;
	cin >> n;
	vector<long long> dp(4, 0);//dp(n + 1, 0)平台会报runtime error
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 4;
	for (int i = 4; i <= n; i++) {
		//dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % MOD;
		long long tmp = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % MOD;
		dp.emplace_back(tmp);
	}
	cout << dp[n] << endl;
	return 0;
}

Problem D

题目描述

一个快递公司要将\(n\)个包裹分别送到\(n\)个地方，并分配给邮递员小K一个事先设定好的路线，小K需要开车按照路线给的地点顺序相继送达，且不能遗漏一个地点。小K得到每个地方可以签收的时间段，并且也知道路线中一个地方到下一个地方的距离。若到达某一个地方的时间早于可以签收的时间段，则必须在这个地方停留至可以签收，但不能晚于签收的时间段，可以认为签收的过程是瞬间完成的。 为了节省燃料，小K希望在全部送达的情况下，车的最大速度越小越好，就找到了你给他设计一种方案，并求出车的最大速度最小是多少。

输入数据

第1行为一个正整数\(n(n<2×10^4)\)，表示需要运送包裹的地点数。

下面 n 行，第 i+1 行有 3 个正整数\(x_i,y_i,s_i\)， 表示按路线顺序给出第\(i\)个地点签收包裹的时间段为\([x_i,y_i]\)，即最早为距出发时刻\(x_i\)，最晚为距出发时刻\(y_i\)，从前一个地点到达第\(i\)个地点距离为 \(s_i\)，且保证路线中\(x_i\)递增。

可以认为\(s1\)为出发的地方到第\(1\)个地点的距离，且出发时刻为\(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
#include <bits/stdc++.h>
using namespace std;
const double eps = 0.00001;
bool valid(vector<int>& x, vector<int>& y, vector<int>& s, long double mid);
int main() {
	int n;
	cin >> n;
	vector<int> x(n), y(n), s(n);
	long double ans = 0.0;
	for (int i = 0; i < n; i++) {
		cin >> x[i] >> y[i] >> s[i];
	}
	long double l = 1, r = 1e9;
	while (r -l >= eps) {
		long double mid = (l + r) / 2;
		if (valid(x, y, s, mid)) {
			ans = mid;
			r = mid;
		}
		else {
			l = mid;
		}
	}
	cout << fixed << setprecision(2);
	cout << ans << endl;
	return 0;
}

bool valid(vector<int>& x, vector<int>& y, vector<int>& s, long double mid) {
	int n = x.size();
	long double t = 0.0;
	for (int i = 0; i < n; i++) {
		t += s[i] / mid;
		t = (t < x[i] ? x[i] : t);
		if (t > y[i]) {
			return false;
		}
	}
	return true;
}

Problem E

题目描述

有ABC三根杆和一些圆盘，开始的时候圆盘从小到大摞在A杆上，小盘在上大盘在下，规定如果圆盘p摞在圆盘q上面，那么\(r_p \leq r_q\)，\(r_p\)和\(r_q\)为p和q的半径。 现在有若干个圆盘，半径从\(1\)到\(n\)，半径为\(i\)的圆盘有\(i\)个，每次操作可以移动一个圆盘，问把所有圆盘从A杆移动到C杆上最少需要几次操作。 由于最终答案可能很大，所以答案对\(10^9+7\)取模输出。

题解

汉诺塔升级版，对于汉诺塔而言，初始状态A柱上从上往下数第\(i\)个盘子共需要被移动\(2^{n-i}\)次；对于该问题而言，初始状态A柱上从上往下数第\(i\)个盘子共需要被移动\(i * 2^{n-i}\)次，用快速幂求解就行。

值得注意的是，快速幂中 x 要取 long long 才够用。

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
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;

using ll = long long;

ll fast_pow(int x, int y) {
	long long ans = 1;
	while (y) {
		if (y & 1) {
			ans = (ans * x) % MOD;
		}
		x = ((x % MOD) * (x % MOD)) % MOD;
		y >>= 1;
	}
	return ans % MOD;
}
int main() {
	int n;
	cin >> n;
	ll ans = 0;
	for (int r = 1; r <= n; r++) {
		ans = (ans + (r * fast_pow(2, n - r) % MOD)) % MOD;
	}
	cout << ans << endl;
	return 0;
}

评论