P8679 [蓝桥杯 2019 省 B] 填空问题 题解
题目传送门
欢迎大家指出错误并联系这个蒟蒻
更新日志
- 2023-05-25 21:02 文章完成
- 2023-05-27 11:34 文章通过审核
- 2023-06-20 21:03 优化了文章代码格式
试题 A :组队
【解析】
本题是一道经典的 DFS 搜索题,每次对各号位的选手进行 DFS,找到各号位上有成绩的选手时再进行进一步搜索即可。
【程序】
#include <bits/stdc++.h>
using namespace std;
int team[20][6];
int max_sum;
bool vis[20];
void dfs(int u, int sum) {
if (u > 5) {
max_sum = max(max_sum, sum);
return;
}
for (int i = 0; i < 20; i++) {
if (!vis[i]) {
vis[i] = true;
dfs(u + 1, sum + team[i][u]);
vis[i] = false;
}
}
}
int main() {
freopen("team.txt", "r", stdin);
for (int i = 0; i < 20; i++) {
for (int j = 0; j < 6; j++) {
cin >> team[i][j];
}
}
dfs(1, 0);
cout << max_sum;
return 0;
}
【答案】
490
试题 B :年号字串
【解析】
该题的 A~Z 相当于二十六进制的 $26$ 个基,因此本题就转换成将 $2019$ 转成二十六进制数的问题。
【程序】
#include <bits/stdc++.h>
using namespace std;
char ch[26];
char ans[5];
int a, n = 2019;
int main() {
for (int i = 0; i < 26; i++) {
ch[i] = 'A' + i;
}
while (n) {
int t = n % 26;
n = n / 26;
if (t == 0) {
t += 26;
}
ans[a++] = ch[t - 1];
}
for (int i = a - 1; i >= 0; i--) {
printf("%c", ans[i]);
}
return 0;
}
【答案】
BYQ
试题 C :数列求值
【解析】
该数列其实很容易让人联想到斐波那契数列,可以采用计算斐波那契数列的递推法进行计算。
【程序】
#include <bits/stdc++.h>
using namespace std;
int dp[20190324];
int main() {
int i;
dp[0] = dp[1] = dp[2] = 1;
for (i = 3; i < 20190324; i++) {
dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % 10000;
}
printf("%d", dp[i - 1]);
return 0;
}
【答案】
4659
试题 D :数的分解
【解析】
本题可以枚举 $3$ 个数字,但是如果 $3$ 个数字都从 $1$ 枚举到 $2019$,则程序就会变得很复杂,我们应该主要解决以下 $2$ 个问题:
1、三数之和等于 $2019$。
2、解决重复情况。
对于情况 $1$,要满足 $i+j+k=2019$,其实 $i$ 和 $j$ 一旦确定,$k$ 的值就已经确定了,所以利用该式,定义的 $3$ 个变量可以变成 $i$、$j$、$2019-i-j$。
对于情况 $2$,要想使得 $3$ 个数字不重复,则只需要将这 $3$ 个数排序,保证排序后的序列是唯一的即可。
【程序】
#include <bits/stdc++.h>
using namespace std;
int judge(int a) {
while (a != 0) {
int t = a % 10;
if (t == 2 || t == 4) {
return 0;
}
a = a / 10;
}
return 1;
}
int main() {
int sum = 0;
for (int i = 1; i < 2019 / 3 + 1; i++) {
if (judge(i)) {
for (int j = i + 1; j < 2019 - i - j; j++) {
if (judge(j)) {
if (judge(2019 - i - j)) {
sum++;
}
}
}
}
}
printf("%d", sum);
return 0;
}
【答案】
40785
试题 E :迷宫
【解析】
本题求步数最少的迷宫路径,即求最短路线。利用 DFS 搜索时回溯较多,容易“爆栈”,所以本题使用 BFS 求最优解即可。
【答案】
DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR