2020 年 12 月青少年软编等考 C 语言三级真题解析

T1. 完美立方

形如 $a^3 = b^3 + c^3 + d^3$ 的等式被称为完美立方等式。例如 $12^3 = 6^3 + 8^3 + 10^3$ 。

编写一个程序，对任给的正整数 $n$ ，寻找所有的四元组 $(a, b, c, d)$ ，使得 $a^3 = b^3 + c^3 + d^3$ ，其中 $a, b, c, d$ 均大于 $1$ ，小于等于 $n$ ，且 $\le c \le d$ 。

时间限制：1 s
内存限制：64 MB

输入
一个正整数 $n$ ， $\le 100$ 。
输出
每行输出一个完美立方。输出格式为：
```
Cube = a, Triple = (b,c,d)
```
样例输入
```
24
```

样例输出

Cube = 6, Triple = (3,4,5)
Cube = 12, Triple = (6,8,10)
Cube = 18, Triple = (2,12,16)
Cube = 18, Triple = (9,12,15)
Cube = 19, Triple = (3,10,18)
Cube = 20, Triple = (7,14,17)
Cube = 24, Triple = (12,16,20)

思路分析

此题考查枚举算法，属于入门题。

用三层循环分别枚举 $b, c, d$ ，然后求出 $\sqrt[3]{b^3 + c^3 + d^3}$ ，并验证 $a$ 是否为整数即可。

虽然题目没有要求输出顺序，但是观察样例输出，是以 $a$ 从小到大的顺序输出的，所以我们可以调整方案，枚举 $a, b, c$ ，求出 $\sqrt[3]{a^3 - b^3 - c^3}$ ，通过验证 $d^3$ 是否为整数来进行判定，注意 $d$ 应该不小于 $c$ 。

/** Name: T1.cpp* Problem: 完美立方* Author: Teacher Gao.* Date&Time: 2024/11/16 18:41*/#include <cstdio>
#include <cmath>int main()
{int n;scanf("%d", &n);for (int a = 6; a <= n; a++) {for (int b = 2; b <= a - 2; b++) {for (int c = b; c <= a - 1; c++) {int p = a*a*a - b*b*b - c*c*c;int d = cbrt(p);if (d < c) break;if (d*d*d != p) continue;printf("Cube = %d, Triple = (%d,%d,%d)\n", a, b, c, d);}}}return 0;
}

T2. 不定方程求解

给定正整数 $a$ ， $b$ ， $c$ 。求不定方程 $a x + b y = c$ 关于未知数 $x$ 和 $y$ 的所有非负整数解组数。

时间限制：1 s
内存限制：64 MB

输入
一行，包含三个正整数 $a$ ， $b$ ， $c$ ，两个整数之间用单个空格隔开，每个数均不大于 $1000$ 。
输出
一个整数，即不定方程的非负整数解组数。
样例输入
```
2 3 18
```
样例输出
```
4
```

思路分析

此题考查枚举法，属于入门题。

常规思路下，需要两层循环分别枚举 $x, y$ 。我们可以将方程变形为 $b y = c - a x$ ，通过枚举 $x$ ，判定 $c - a x$ 是否为 $b$ 的倍数进行求解，只需要一层循环即可。

/** Name: T2.cpp* Problem: 不定方程求解* Author: Teacher Gao.* Date&Time: 2024/11/17 17:33*/#include <cstdio>int main()
{int a, b, c, tot = 0;scanf("%d%d%d", &a, &b, &c);for (int x = 0; x <= c/a; x++) {int p = c - a * x;if (p % b == 0) {tot++;}}printf("%d", tot);return 0;
}

T3. 分解因数

给出一个正整数 $a$ ，要求分解成若干个正整数的乘积，即 $a_1 \times a_2 \times \cdots \times a_n$ ，并且 $a_1 \le a_2 \le \cdots \le a_n$ ，问不同的分解方法有多少种。

注意： $a = a$ 也是一种分解方法。

时间限制：1 s
内存限制：64 MB

输入
第 $1$ 行是测试数据的组数 $n$ （ $\le n \le 1000$ ），后面跟着 $n$ 行输入。每组测试数据占 $1$ 行，包括一个正整数 $a$ （ $1 < a < 32768$ ）。
输出
$n$ 行，每行输出对应一个输入。输出应是一个正整数，指明不同的分解方法数。
样例输入
```
2
2
20
```
样例输出
```
1
4
```

思路分析

此题考查递归算法，属于基础题。

定义递归函数 $\tt count(a, k)$ 用于求解将 $a$ 分解为不小于 $k$ 的正整数乘积的方法数。当 $a < k$ 时到达递归边界，分解方法数为 $0$ 。

递归过程则是枚举 $k\sim \sqrt{a}$ 的每一个整数，如果检测到某个数 $i$ 是 $a$ 的因子，则递归分解 $a / i$ 。由于此次已经分解出 $i$ 了，为了保证不重复，下一次应从不小于 $i$ 的数中做分解。然后将 $\tt count(a/i,i)$ 的方法数累加到 $res u lt$ 中，由于不做任何分解也算一种分解方法，所以最后返回 $res u lt + 1$ 。对于输入的每一个 $a$ ，调用 $\tt count(a, 2)$ 即为答案。

/** Name: T3.cpp* Problem: 分解因数* Author: Teacher Gao.* Date&Time: 2024/11/17 11:53*/#include<cstdio>int count(int a, int k) {if (a < k) {return 0;}int result = 1;for (int i = k; i*i <= a; i++) {if (a % i == 0) {result += count(a/i, i);}}return result;
}
int main() {int n, a;scanf("%d", &n);while(n--) {scanf("%d", &a);printf("%d\n", count(a, 2));}return 0;
}

T4. 上台阶

楼梯有 $n$ 级台阶，上楼时可以一步上 $1$ 级，也可以一步上 $2$ 级，也可以一步上 $3$ 级，编程计算共有多少种不同的走法。

时间限制：1 s
内存限制：64 MB

输入
输入的每一行包括一组测试数据，即为台阶数 $n$ （ $\le n \le 30$ ）。最后一行为 $0$ ，表示测试结束。
输出
每一行输出对应一行输入的结果，即为走法的数目。最后一行的 $0$ 不用输出。
样例输入
```
1
2
3
4
0
```
样例输出
```
1
2
4
7
```

思路分析

此题考查递推算法，与 2020 年 9 月三级 T4 类似，属于基础题。

根据题目描述，容易得出递推公式 $f_i = f_{i-1} + f_{i-2} + f_{i-3}$ ，其中 $\ge 4$ ，初始条件为 $f_1 = 1$ ， $f_2 = 2$ ， $f_3 = 4$ 。同样由于是多组数据，我们可以将所有可能的答案打表记录，对于每次询问以 $O (1)$ 的时间复杂度给出答案。

/** Name: T4.cpp* Problem: 上台阶* Author: Teacher Gao.* Date&Time: 2024/11/17 11:55*/#include <cstdio>int main()
{long long f[35] = {0, 1, 2, 4};for (int i = 4; i <= 30; i++) {f[i] = f[i-1] + f[i-2] + f[i-3];}int n;while (scanf("%d", &n) && n) {printf("%lld\n", f[n]);}return 0;
}

T5. 田忌赛马

在田忌赛马的故事中，孙膑用自己的下等马对战对手的上等马，自己上等马对阵对手的中等马，自己的中等马对阵对手的下等马，从而赢得了胜利。现在即将进行的是 $n$ 匹马的赛马比赛。双方队伍的马各分为 $n$ 等。已知只有当我方马的等级比对方马等级高 $x$ 等以上（包含 $x$ ）时，我方才可以取得这场比赛的胜利。如果在 $n$ 场比赛中我方胜利数大于对方，则我方取得最终的胜利。现在已知对方这 $n$ 场比赛的出战方案，请计算所有令我方最终获胜的出战方案。

时间限制：1 s
内存限制：64 MB

输入
第一行两个整数， $n$ 和 $x$ ， $\le x \le n \le 9$ 。
第二行 $n$ 个正整数， $a_1, a_2, \cdots, a_n$ 。 $a_i$ 表示第 $i$ 场比赛对方马的等级， $\le i \le n$ 。等级越高越强。
输出
按字典序输出所有我方最终获胜的方案，每个方案一行。每行是 $n$ 个正整数，两两之间以一个空格分隔，第 $i$ 个数表示我方第 $i$ 场比赛马的等级。
样例输入 $1$
```
3 1
3 2 1
```
样例输出 $1$
```
1 3 2
```
样例输入 $2$
```
3 0
3 1 2
```
样例输出 $2$
```
1 2 3
1 3 2
2 1 3
3 1 2
3 2 1
```

思路分析

此题考查搜索与回溯算法，属于基础题。

定义搜索函数 $\tt dfs(k, tot)$ 表示目前安排第 $k$ 场出战的马，已经获胜了 $t o t$ 场。当 $k > n$ 时到达递归边界，若 $t o t > n /2$ 则输出此次搜索到的方案。

递归过程则依次枚举等级为 $1\sim n$ 的所有马匹，若当前找到一匹尚未出战的马，则将其安排为第 $k$ 场出战，将其等级存储在 $t [k]$ 位置，并将其标记为已出战，同时计算第 $k$ 场能否获胜，然后继续递归安排第 $k + 1$ 场出战的马匹。

当递归结束之后，回溯过程需要将当前这匹马标记为未出战，便于搜索其它可行方案。

/** Name: T5.cpp* Problem: 田忌赛马* Author: Teacher Gao.* Date&Time: 2024/11/17 14:31*/#include <cstdio>int n, x;
int a[15], t[15], f[15];void dfs(int k, int tot) {if (k > n) {if (tot > n / 2) {for (int i = 1; i <= n; i++) {printf("%d ", t[i]);}printf("\n");    }return ;}for (int i = 1; i <= n; i++) {if (f[i]) continue;f[i] = 1;t[k] = i;dfs(k+1, tot + (i >= x+a[k]));f[i] = 0;}
}int main()
{scanf("%d%d", &n, &x);for (int i = 1; i <= n; i++)scanf("%d", &a[i]);dfs(1, 0);return 0;
}