题目涉及算法：
- 奖学金：结构体排序；
- 纪念品分组：贪心；
- 守望者的逃离：动态规划；
- Hanoi 双塔问题：递推。
奖学金
题目链接：https://www.luogu.org/problem/P1093
这道题目就是一道简单的结构体排序。
实现代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 330;
struct Student {
int id, x, y, z;
} a[maxn];
int n;
bool cmp(Student a, Student b) {
if (a.x+a.y+a.z != b.x+b.y+b.z) return a.x+a.y+a.z > b.x+b.y+b.z;
if (a.x != b.x) return a.x > b.x;
return a.id < b.id;
}
int main() {
cin >> n;
for (int i = 0; i < n; i ++) {
cin >> a[i].x >> a[i].y >> a[i].z;
a[i].id = i + 1;
}
sort(a, a+n, cmp);
for (int i = 0; i < 5; i ++)
cout << a[i].id << " " << a[i].x+a[i].y+a[i].z << endl;
return 0;
}纪念品分组
题目链接：https://www.luogu.org/problem/P1094
本体涉及算法：贪心。
我们从小到大遍历每个元素（将这个元素作为较小的元素），找到最大的那个与其相加的不超过w的那件物品凑成一对；剩下的就单独作为一件。使用双指针法实现。
实现代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 30030;
int w, n, a[maxn], cnt;
int main() {
cin >> w >> n;
for (int i = 0; i < n; i ++) cin >> a[i];
sort(a, a+n);
int i = 0, j = n-1;
while (i < j) {
if (a[i] + a[j] <= w) { i ++; j --; cnt ++; }
else { j --; cnt ++; }
}
if (i == j) cnt ++;
cout << cnt << endl;
return 0;
}守望者的逃离
题目链接：https://www.luogu.org/problem/P1095
本题主要涉及算法：动态规划。
我们需要知道的是：一开始如果给我的魔法值 \(\ge 10\) ，那么无论如何我都会优先选择使用魔法。
所以一开始就是循环使用贪心直到我的剩余魔法值 \(\lt 10\) 为止。
那么在这种情况下，我只有三种策略走下一步：
- 跑步：消耗1秒，前进17米；
- 休息：消耗1秒，回复4点魔法值；
- 闪烁（在魔法值 \(\ge 10\) 的前提下）：消耗1秒，前进60米，消耗10点魔法值。
所以，如果我设 \(f[i][j]\) 表示当前在第i秒结束时，我剩余的魔法值有j点的情况下，我行走的最大距离。则， \(f[i][j]\) 应该是如下三者的最大值：
- \(f[i-1][j] + 17\) ：表示从前一秒跑步到这一秒；
- \(f[i-1][j-4]\) ：表示休息了一秒（需满足 \(j \ge 4\) ）；
- \(f[i-1][j+10]\) ：表示使用魔法到这一秒（需满足 \(j \ge 10\) ）。
实现代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 300030;
int M, S, T, f[maxn][14];
int main() {
cin >> M >> S >> T;
for (int i = 0; i <= T; i ++)
for (int j = 0; j <= 13; j ++)
f[i][j] = -1;
int s = 0, id = 0;
while (M >= 10 && id <= T) {
s += 60;
M -= 10;
id ++;
if (s >= S) {
puts("Yes");
cout << id << endl;
return 0;
}
}
if (id > T) {
puts("No");
cout << T*60 << endl;
return 0;
}
f[id][M] = s;
for (int i = id+1; i <= T; i ++) {
for (int j = 0; j <= 13; j ++) {
int tmp1 = 0; // running
if (f[i-1][j] != -1) tmp1 = f[i-1][j] + 17;
int tmp2 = 0; // take rest
if (j >= 4 && f[i-1][j-4] != -1) tmp2 = f[i-1][j-4];
int tmp3 = 0; // use magic
if (j+10 <= 13 && f[i-1][j+10] != -1) tmp3 = f[i-1][j+10] + 60;
int tmp = max(tmp1, max(tmp2, tmp3));
if (tmp > 0) f[i][j] = tmp;
if (f[i][j] >= S) {
puts("Yes");
cout << i << endl;
return 0;
}
}
}
puts("No");
s = 0;
for (int i = 0; i <= 13; i ++) s = max(s, f[T][i]);
cout << s << endl;
return 0;
}Hanoi 双塔问题
题目链接：
这道题目相信做过递归经典问题——汉诺塔问题——的同学应该都能够直接推导出递推公式。
Hanoi它问题的递推公式是：\(f[i] = 2 \times f[i-1] + 1\) ；
而我们这里也能够很轻松推导出双塔问题的地推公式就是：
\(f[i] = 2 \times f[i-1] + 2\)
但是因为数据量比较大，所以需要使用高精度。
实现代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int a[maxn], b[maxn], c[maxn], n, t;
void init() {
a[0] = 2;
n = 1;
}
void solve() {
for (int i = 0; i < n; i ++) a[i] *= 2;
a[0] += 2;
for (int i = 0; i < n; i ++) {
a[i+1] += a[i] / 10;
a[i] %= 10;
}
if (a[n]) n ++;
}
int main() {
cin >> t;
init();
while (--t) solve();
for (int i = n-1; i >= 0; i --) cout << a[i];
cout << endl;
return 0;
}作者：zifeiy