自动搬运

查看原文

来自洛谷，原作者为

	cirrationaler 学术一点。

搬运于2025-08-24 22:41:23，当前版本为作者最后更新于2023-05-23 22:43:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

试题 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 \sim 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$ 个问题：

• 三数之和等于 $2019$。
• 解决重复情况。

对于情况 $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