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