P8679 [蓝桥杯 2019 省 B] 填空问题 题解

• 题目传送门

试题 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()
{
    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