题目
说明：点击题目名称即可跳转原题链接 🙂
| 题号 | 题目 | 知识点 | 难度 |
| T1 | 数的计算 | 递推，递归 | 普及- |
| T2 | 最大公约数和最小公倍数问题 | 数学，枚举，gcd | 普及- |
| T3 | 求先序排列 | 字符串，树，递归 | 普及- |
| T4 | 装箱问题 | 动规，背包 | 普及- |
数的计算
思路
- 可以把前几项的序列先手动模拟生成，尝试找到数字之间的规律。
- 1: 1
- 2: 2, 2 1
- 3: 3, 3 1
- 4: 4, 4 2, 4 1, 4 2 1
- 5: 5, 5 2, 5 1, 5 2 1
- 6: 6, 6 3, 6 2, 6 1, 6 3 1, 6 2 1
- 分析发现奇数项结果同上一个偶数项的结果。可以这样理解：项数每加 1，多出来能补左边的数只有 0.5，对补整数没有用，只有项数 + 2，才能有个新的能补的整数，所以答案数据变化都发生在偶数项之间。
- 偶数项每两项多出一个新的 (n / 2) 可补在左边，在上项结果基础上新增数量 f(n / 2)，得到递推公式是 f(n) = f(n – 1) + f (n / 2)。
- 实际上由于奇数项结果等于上一个偶数项，所以递推公式也可以写成 f(n) = f(n – 2) + f (n / 2)。
- 代码具体实现可以用递推，也可以用递归 + 记忆化搜索。
代码
#include <bits/stdc++.h>
using namespace std;
int n, a[1005] = {};
int main(){
cin >> n;
a[1] = 1;
for(int i = 2; i <= n; i++){
if(i % 2) // 奇数项： a[i] = a[i - 1] (同上一个偶数项)
a[i] = a[i - 1];
else // 偶数项： a[i] = a[i - 1] + a[i / 2] (新增 a[i/2])
a[i] = a[i - 1] + a[i / 2];
}
cout << a[n];
return 0;
}
最大公约数和最小公倍数问题
思路
- 数学知识 ： gcd(a, b) * lcm(a, b) = a * b，即 a 和 b 的最大公约数(gcd) 与 最小公倍数(lcm) 的乘积等于 a 与 b 的乘积。
- 可以用辗转相除法递归求两个数的最大公约数，如下：
int gcd(int a, int b){ // 返回 a 和 b 的最大公约数
if(!b) return a;
return gcd(b, a % b);
}
3. 已知 gcd(p, q) = x, lcm(p, q) = y，可以尝试枚举所有 x 的倍数作为 p 的值，再由 gcd(p, q) * lcm(p, q) = p * q 反推 q = gcd(p, q) * lcm(p, q) / p，即 q = x * y / p（这里是整除，向下取整）。
4. 对于枚举的 p 和 q 的值还要检验是否满足题意，即 p * q == x * y 且 gcd(p, q) == x，满足条件的，答案计数加 1。
代码
#include<bits/stdc++.h>
using namespace std;
int x, y, p, q, ans;
int gcd(int a, int b){ // 返回 a 和 b 的最大公约数
if(!b) return a;
return gcd(b, a % b);
}
int main(){
cin >> x >> y;
for(int p = x; p <= y; p += x){ // p：尝试枚举 y 以内 x 的倍数
q = x * y / p; // p * q = x * y
if(p * q == x * y && gcd(p, q) == x){
ans++;
}
}
cout << ans;
return 0;
}
求先序排列
思路
- 后序遍历的最后一个结点为根结点，因此可在中序遍历序列中查找后序遍历的最后一个结点，以此为界，左半边就是左子树，右半边就是右子树，注意在两个序列中划分左右子树的端点计算（详见代码注释）。
- 先序遍历顺序为：根->左->右，因此找到左右子树后，按照先输出根结点，再遍历左子树，最后遍历右子树的顺序访问每个结点即可。
代码
#include <bits/stdc++.h>
using namespace std;
string po, in;
void f(int pl, int pr, int il, int ir){ // pl/r: 后序左/右端点，il/r: 中序左/右端点
if(pl > pr || il > ir){ // 结束条件：左右边界越界（即序列无元素）
return;
}
int k = in.find(po[pr]); // 在中序序列中找出后序终点（根结点）所在下标 k
// 中序：左半子树[il...(k-1)] 根[k] 右半子树[(k+1)...ir]
// 左半子树元素个数：k-1-il+1 = k-il个， 右半子树元素个数：ir-k-1+1=ir-k 个
// 后序：左半子树[pl...(pl+k-il-1)] 右半子树[(pl+k-il)...(pr-1)] 根[pr]
cout << in[k]; // 输出根结点，也可以是 po[pr]
f(pl, pl+k-il-1, il, k-1); // 递归遍历左半子树
f(pl+k-il, pr-1, k+1, ir); // 递归遍历右半子树
}
int main(){
cin >> in >> po; // in:中序 po:后序
int len = in.size();
f(0, len-1, 0, len-1); // 传参：两个序列的左右端点
return 0;
}
装箱问题
思路
- 这个题是一道 01 背包的变形。n 个物品，每个物品有一个体积，背包总容量为 V，要选择若干物品使背包剩余空间尽可能小，由此可分析出对每个物品来说，选择的成本是它的体积，带来的收益也是它的体积。
- 状态定义：dp[i][j] 表示前 i 个物品背包容量为 j 的最大收益。
- 状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j – cost[i]] + cost[i])
- 逆序枚举降维压缩：dp[j] = max(dp[j], dp[j – cost[i]] + cost[i])
- 最后输出 v – dp[v] 为背包最小余量。
代码
#include <bits/stdc++.h>
using namespace std;
int v, n, ans, cost[35], dp[20005];
int main(){
cin >> v >> n;
for(int i = 1; i <= n; i++){
cin >> cost[i];
}
for(int i = 1; i <= n; i++){ // 遍历每一个物品
for(int j = v; j >= cost[i]; j--){ // 逆序枚举背包容量
dp[j] = max(dp[j], dp[j - cost[i]] + cost[i]); // 取选第 i 个物品，和不选第 i 个物品方案中的最大值
}
}
cout << v - dp[v]; // 剩余最小容量
return 0;
}