题目涉及算法：
- 数的计算：动态规划；
- 最大公约数和最小公倍数问题：质因数分解；
- 求先序排列：递归；
- 装箱问题：动态规划（纯0-1背包问题）
数的计算
题目链接：https://www.luogu.org/problem/P1028
这道题目可以用动态规划进行求解。
我们令 (f[i]) 表示自然数为 (i) 能够生成的数的个数，则：
(f[i] = 1 + sum_{j=1}^{n/2} f[j])
实现代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
int n, f[maxn];
int main() {
cin >> n;
for (int i = 1; i <= n; i ++) {
f[i] = 1;
for (int j = 1; j <= i/2; j ++)
f[i] += f[j];
}
cout << f[n] << endl;
return 0;
}
最大公约数和最小公倍数问题
题目链接：https://www.luogu.org/problem/P1029
这道题目虽然名为“最大公约数和最小公倍数问题”，但其实是一道 质因数分解 的问题。
首先，如果P不能整除Q，那么答案肯定为 (0) ，直接输出 (0) 即可。
其次，我们令 (n = Q/P) ，然后对 (n) 进行质因数分解，假设对 (n) 进行质因数分解的表达式为：
(n = a_1^{b_1} imes a_2^{b_2} imes dots imes a_m^{b_m})
那么我们知道，对于其中的任意一个 (a_i) ，它要么归到 (x0) ，要么归到 (y0) ，不可能有 (1) 个 (a_i) 归到 (x0) ，而另一个 (a_i) 归到 (y0) （因为这个时候他们的最大公约数就变成了 (x0 imes a_i)） ，所以对于这 (m) 个 (a_i) ，他们要么都归到 (x0) ，要么都归到 (y0) ，所以总的方案数就是 (2^m) 。
实现代码如下（代码中我用 (cnt) 来表示不同的质因数个数）：
#include <bits/stdc++.h>
using namespace std;
int n, m, P, Q, cnt;
long long ans = 1;
int main() {
cin >> P >> Q;
if (Q % P) {
puts("0");
return 0;
}
n = Q / P;
m = sqrt(n);
for (int i = 2; i <= m; i ++) {
if (n % i == 0) {
cnt ++;
while (n % i == 0) n /= i;
}
}
if (n > 1) cnt ++;
cout << ( 1LL << cnt ) << endl;
return 0;
}
求先序排列
题目链接：https://www.luogu.org/problem/P1030
这道题目可以用“递归”进行求解。
首先，后续序列的最后一个元素肯定是当前子树的根节点。
我们可以在中序序列里面找到根节点的位置，然后中序序列例根节点左边的子串对应该根节点的左子树，右边的子串对应根节点的右子树。我们递归地进行遍历就可以还原出这棵树。
同时，我们在递归的时候其实也可以直接输出这棵树的先序遍历结果。
实现代码如下：
#include <bits/stdc++.h>
using namespace std;
char zx[10], hx[10]; // zx：中序序列；hx：后序序列
// [L1,R1]对应中序序列的区间范围；
// [L2,R2]对应后序序列的区间范围
void dfs(int L1, int R1, int L2, int R2) {
if (L1 >= R1) {
if (L1 == R1) putchar(zx[L1]);
return;
}
int i;
for (i = L1; i <= R1 && zx[i] != hx[R2]; i ++);
putchar(zx[i]);
int l_len = i - L1, r_len = R1 - i;
dfs(L1, i-1, L2, L2+l_len-1);
dfs(i+1, R1, R2-r_len, R2-1);
}
int main() {
cin >> zx >> hx;
int len = strlen(zx);
dfs(0, len-1, 0, len-1);
return 0;
}
装箱问题
题目链接：https://www.luogu.org/problem/P1049
这道题目是一道纯0-1背包问题。
对于第i件物品，我们令它的体积等于价值，套0-1背包模板能够得到能装进箱子的最大价值。以箱子总体积减去总价值就是箱子的最小的剩余空间。
实现代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 20020;
int n, V, c, f[maxn];
int main() {
cin >> V >> n;
while (n --) {
cin >> c;
for (int i = V; i >= c; i --)
f[i] = max(f[i], f[i-c] + c);
}
cout << V - f[V] << endl;
return 0;
}
作者：zifeiy