[C++知识库]第十三届蓝桥杯大赛软件赛决赛（C/C++ 大学B组）

?? 更新中…

试题 A: 2022

本题总分：$5$ 分

【问题描述】

??将 $2022$ 拆分成 $10$ 个互不相同的正整数之和，总共有多少种拆分方法？

??注意交换顺序视为同一种方法，例如 $2022=1000+1022$ 和 $2022=1022+1000$ 就视为同一种方法。

【答案提交】

??这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个由大写字母组成的字符串，在提交答案时只填写这个字符串，填写多余的内容将无法得分。

379187662194355221

k 部分互异分拆数

??定义 $p{d}_{k}n$ 为 $n$ 分拆成 $k$ 个不同的部分的方案数，即下列方程$：$$$n=r_1+r_2+?+r_k,r_1>r_2>?>r_k\ge 1$$??的解的数量，两边同时减去 $k$$：$$$n?k=d_1+d_2+?+d_k,d_1>d_2>?>d_k\ge 0，$$??由于 $d_i$ 互异，故仅能有一个部分为 $0$，以此为界，划分成$：$$$\begin{gathered} n?k=d_1+d_2+?+d_{k?1}+0,d_1>d_2>?>d_k\ge 0， \\ n?k=g_1+g_2+?+g_k,g_1>g_2>?>g_k\ge 1， \end{gathered}$$??两部分，显然有递推式$：$$$p{d}_{k}n=p{d}_{k?1}(n?k)+p{d}_k(n?k).$$

#include <stdio.h>

const int N = 2022, k = 10;

long long pd[N + 1][k + 1]{1};

int main() {
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= k; ++j)
            if (i >= j) pd[i][j] = pd[i - j][j] + pd[i - j][j - 1];
    printf("%lld", pd[N][k]);
}

??上来就这么劲爆的吗，难度

试题 B: 钟表

本题总分：$5$ 分

【问题描述】

??在 $12$ 小时制的钟表中，有分针、时针、秒针来表示时间。记分针和时针之间的夹角度数为 $A（0\le A\le 180）$、分针和秒针之间的夹角度数为 $B（0\le B\le 180）$。而恰好在 $s$ 时 $f$ 分 $m$ 秒时，满足条件 $A=2B$ 且 $0\le s\le 6；0\le f<60；0\le m<60$，请问 $s,f,m$ 分别是多少。

??注意时针、分针、秒针都围绕中心匀速转动。

??提交格式为三个由一个空格隔开的整数，分别表示 $s,f,m$。如 $31158$ 表示 $3$ 点 $11$ 分 $58$ 秒。

【答案提交】

??这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为三个由一个空格隔开的整数，在提交答案时只填写为三个由一个空格隔开的整数，填写多余的内容将无法得分。

4 48 0

??为了一定程度上的运算简便，这里周角为 $60$ 度，

??然后 $\mathrm{B}\mathrm{F}$ 就完了。

#include <stdio.h>

double fabs(double x) { return x > 0 ? x : -x; }

double abs(double angle) {
    angle = fabs(angle);
    if (angle > 30) return 60 - angle;
    return angle;
}

int main() {
    for (int s = 0; s <= 6; ++s)
        for (int f = 0; f < 60; ++f)
            for (int m = 0; m < 60; ++m) {
                double second = m;
                double minute = f + second / 60;
                double hour = (s * 60 + minute) / 12;
                double B = abs(minute - second);
                double A = abs(minute - hour);
                if (fabs(A - 2 * B) < 1e-10)
                    printf("%d %d %d\n", s, f, m);
            }
}

??还好我的好 $\mathrm{b}\mathrm{r}\mathrm{o}$ 告诉我 $000$ 是作废答案，

??不然我就直接填了。

??其实也可以类似程序中计算角度的过程来列出三元方程组，算的还快一点。

试题 C: 卡牌

时间限制: $1.0\mathrm{s}$?内存限制: $256.0\mathrm{M}\mathrm{B}$?本题总分：$10$ 分

【问题描述】

??这天，小明在整理他的卡牌。

??他一共有 $n$ 种卡牌，第 $i$ 种卡牌上印有正整数数 $i(i\in [1,n])$，且第 $i$ 种卡牌现有 $a_i$ 张。

??而如果有 $n$ 张卡牌，其中每种卡牌各一张，那么这 $n$ 张卡牌可以被称为一套牌。小明为了凑出尽可能多套牌，拿出了 $m$ 张空白牌，他可以在上面写上数i，将其当做第 $i$ 种牌来凑出套牌。然而小明觉得手写的牌不太美观，决定第 $i$ 种牌最多手写 $b_i$ 张。

??请问小明最多能凑出多少套牌？

【输入格式】

??输入共 $3$ 行，第一行为两个正整数 $n,m$。

??第二行为 $n$ 个正整数 $a_1,a_2,?,a_n$。

??第三行为 $n$ 个正整数 $b_1,b_2,?,b_n$。

【输出格式】

??一行，一个整数表示答案。

【样例输入】

4 5
1 2 3 4
5 5 5 5

【样例输出】

3

【样例说明】

??这 $5$ 张空白牌中，拿 $2$ 张写 $1$，拿 $1$ 张写 $2$，这样每种牌的牌数就变为了 $3,3,3,4$，可以凑出 $3$ 套牌，剩下 $2$ 张空白牌不能再帮助小明凑出一套。

【评测用例规模与约定】

??对于 $30\%$ 的数据，保证 $n\le 2000$；
??对于 $100\%$ 的数据，保证 $n\le 2\times 10^5;a_i,b_i\le n;m\le n^2$ 。

#include <stdio.h>

const int N = 2 * 1e5;

int n, A[N], B[N];

long long m;

int main() {
    scanf("%d %lld", &n, &m);
    for (int i = 0; i < n; ++i) scanf("%d", A + i);
    for (int i = 0; i < n; ++i) scanf("%d", B + i);
    int l = 0, r = 2 * n;
    while (l < r) {
        int flag = 1, mid = l + r + 1 >> 1;
        long long buf = m;
        for (int i = 0; i < n; ++i) {
            if (A[i] >= mid) continue;
            if (A[i] + B[i] < mid || mid - A[i] > buf) {
                flag = 0;
                break;
            }
            buf -= mid - A[i];
        }
        if (flag) l = mid; else r = mid - 1;
    }
    printf("%d", l);
}

??二分判定答案的模板。

试题 D: 最大数字

时间限制: $1.0\mathrm{s}$?内存限制: $256.0\mathrm{M}\mathrm{B}$?本题总分：$10$ 分

【问题描述】

??给定一个正整数 $N$。你可以对 $N$ 的任意一位数字执行任意次以下 $2$ 种操作$：$

??$1.$ 将该位数字加 $1$。如果该位数字已经是 $9$，加 $1$ 之后变成 $0$。
??$2.$ 将该位数字减 $1$。如果该位数字已经是 $0$，减 $1$ 之后变成 $9$。

??你现在总共可以执行 $1$ 号操作不超过 $A$ 次，$2$ 号操作不超过 $B$ 次。

??请问你最大可以将 $N$ 变成多少？

【输入格式】

??第一行包含 $3$ 个整数$：$$N,A,B$。

【输出格式】

??一个整数代表答案。

【样例输入】

123 1 2

【样例输出】

933

【样例说明】

??对百位数字执行 $2$ 次 $2$ 号操作，对十位数字执行 $1$ 次 $1$ 号操作。

【评测用例规模与约定】

??对于 $30\%$ 的数据，$1\le N\le 100;0\le A,B\le 10$
??对于 $100\%$ 的数据，$1\le N\le 10^{17};0\le A,B\le 100$

#include <stdio.h>

char N[20];

long long ans = 0;

int A, B;

inline int min(int a, int b) { return a < b ? a : b; }

void dfs(int i, long long val) {
    if (N[i]) {
        int a = min(A, '9' - N[i]);
        A -= a;
        dfs(i + 1, val * 10 + N[i] + a - '0');
        A += a;
        if (N[i] - '0' < B) {
            int b = N[i] - '0' + 1;
            B -= b;
            dfs(i + 1, val * 10 + 9);
            B += b;
        }
    } else if (val > ans) ans = val;
}

int main() { scanf("%s %d %d", N, &A, &B), dfs(0, 0), printf("%lld", ans); }

??看一眼数据范围就知道，贪心暴搜。

试题 E: 出差

时间限制: $1.0\mathrm{s}$?内存限制: $256.0\mathrm{M}\mathrm{B}$?本题总分：$15$ 分

【问题描述】

??$\mathrm{A}$ 国有 $N$ 个城市，编号为 $1?\mathrm{N}$。小明是编号为 $1$ 的城市中一家公司的员工，今天突然接到了上级通知需要去编号为 $\mathrm{N}$ 的城市出差。

??由于疫情原因，很多直达的交通方式暂时关闭，小明无法乘坐飞机直接从城市 $1$ 到达城市 $\mathrm{N}$，需要通过其他城市进行陆路交通中转。小明通过交通信息网，查询到了 $M$ 条城市之间仍然还开通的路线信息以及每一条路线需要花费的时间。

??同样由于疫情原因，小明到达一个城市后需要隔离观察一段时间才能离开该城市前往其他城市。通过网络，小明也查询到了各个城市的隔离信息。（由于小明之前在城市 $1$，因此可以直接离开城市 $1$，不需要隔离）

??由于上级要求，小明希望能够尽快赶到城市 $\mathrm{N}$，因此他求助于你，希望你能帮他规划一条路线，能够在最短时间内到达城市 $\mathrm{N}$。

【输入格式】

??第 $1$ 行$：$两个正整数 $N,M$，$N$ 表示 $\mathrm{A}$ 国的城市数量，$M$ 表示未关闭的路线数量

??第 $2$ 行$：$$N$ 个正整数，第 $i$ 个整数 $C_i$ 表示到达编号为 $i$ 的城市后需要隔离的时间

??第 $3?M+2$ 行$：$每行 $3$ 个正整数，$u,v,c$，表示有一条城市 $u$ 到城市 $v$ 的双向路线仍然开通着，通过该路线的时间为 $c$

【输出格式】

??第 $1$ 行$：$$1$ 个正整数，表示小明从城市 $1$ 出发到达城市 $\mathrm{N}$ 的最短时间（到达城市 $\mathrm{N}$，不需要计算城市 $\mathrm{N}$ 的隔离时间）

【样例输入】

4 4
5 7 3 4
1 2 4
1 3 5
2 4 3
3 4 5

【样例输出】

13

【样例说明】

??$[1(5)]??4??[2(7)]$
???$||$
???$||$
???$53$
???$||$
???$||$
??$[3(3)]??5??[4(4)]$

??路线 $1$$：$$1?>2?>4$，时间为 $4+7$(隔离)$+3=14$
??路线 $2$$：$$1?>3?>4$，时间为 $5+3$(隔离)$+5=13$

【评测用例规模与约定】

??对于 $100\%$ 的数据，$1\le N\le 1000,1\le M\le 10000,1\le C_i\le 200,1\le u,v\le N,1\le c\le 1000$

#include <stdio.h>
#include <utility>
#include <queue>

const int N = 1e3 + 1, M = 4 * 1e4 + 9;

int linked[M], next[M], ver[M], val[M], cur = 0;

inline void link(int u, int v, int k) { ++cur, next[cur] = linked[u], linked[u] = cur, ver[cur] = v, val[cur] = k; }

std::priority_queue<std::pair<int, int>> q;

int n, m, u, v, c, C[N], dist[N];

bool visited[N];

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d", C + i), dist[i] = 0x3f3f3f3f;
    C[1] = 0;
    while (m--) {
        scanf("%d %d %d", &u, &v, &c);
        link(u, v, C[u] + c);
        link(v, u, C[v] + c);
    }
    dist[1] = 0;
    q.push({0, 1});
    while (q.size()) {
        u = q.top().second, q.pop();
        if (visited[u]) continue;
        visited[u] = 1;
        for (cur = linked[u]; cur; cur = next[cur])
            if (dist[ver[cur]] > dist[u] + val[cur]) {
                dist[ver[cur]] = dist[u] + val[cur];
                q.push({-dist[ver[cur]], ver[cur]});
            }
    }
    printf("%d", dist[n]);
}

??模板 $\times 3$。

试题 F: 费用报销

时间限制: $1.0\mathrm{s}$?内存限制: $256.0\mathrm{M}\mathrm{B}$?本题总分：$15$ 分

【问题描述】

??小明在出差结束后返回了公司所在的城市，在填写差旅报销申请时，粗心的小明发现自己弄丢了出差过程中的票据。

??为了弥补小明的损失，公司同意小明用别的票据进行报销，但是公司财务要求小明提交的票据中任意两张的日期差不小于 $K$ 天，且总金额不得超过实际差旅费用 $M$。

??比如财务要求 $K=7$ 时，若小明提交了一张 $1$ 月 $8$ 日的票据，小明就不能提交 $1$ 月 $2$ 日至 $1$ 月 $14$ 日之间的其他票据，$1$ 月 $1$ 日及之前和 $1$ 月 $15$ 日及之后的票据则可以提交。

??公司的同事们一起给小明凑了 $N$ 张票据，小明现在想要请你帮他整理一下，从中选取出符合财务要求的票据，并使总金额尽可能接近 $M$。

??需要注意，由于这些票据都是同一年的，因此 $12$ 月底的票据不会影响到 $1$ 月初票据的提交。这一年不是闰年。

【输入格式】

??第 $1$ 行$：$$3$ 个整数，$N,M,K$

??第 $2?N+1$ 行$：$每行 $3$ 个整数 $m_i,d_i,v_i$，第 $i+1$ 行表示第 $i$ 张票据时间的月份 $m_i$ 和日期 $d_i$，$v_i$ 表示该票据的面值

【输出格式】

??第 $1$ 行$：$$1$ 个整数，表示小明能够凑出的最大报销金额

【样例输入】

4 16 3
1 1 1
1 3 2
1 4 4
1 6 8

【样例输出】

10

【样例说明】

??选择 $1$ 月 $3$ 日和 $1$ 月 $6$ 日的票据

【评测用例规模与约定】

??对于 $100\%$ 的评测用例，$1\le N\le 1000,1\le M\le 5000,1\le K\le 50,1\le m_i\le 12,1\le d_i\le 31,1\le v_i\le 400$
??日期保证合法。

#include <stdio.h>
#include <algorithm>
#include <utility>

const int max_N = 1e3 + 1, max_M = 5 * 1e3 + 1;

const int offset[]{ 0, 0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334 };

std::pair<int, int> bill[max_N];

bool dp[max_N][max_M]{1};

int N, M, K, m, d, v;

int main() {
    scanf("%d %d %d", &N, &M, &K);
    for (int i = 1; i <= N; ++i)
        scanf("%d %d %d", &m, &d, &v),
        bill[i] = {offset[m] + d, v};
    std::sort(bill + 1, bill + N + 1);
    for (int i = 1, k = 0; i <= N; ++i) {
        while (bill[i].first - bill[k + 1].first >= K) ++k;
        for (int j = M; j >= bill[i].second; --j)
            dp[i][j] = dp[i - 1][j] | dp[k][j - bill[i].second];
        for (int j = bill[i].second - 1; ~j; --j) dp[i][j] = dp[i - 1][j];
    }
    for (int i = M; ~i; --i)
        if (dp[N][i]) {
            printf("%d", i);
            return 0;
        }
}

??模板 $\times 4$，还是 $0$ - $1$ 背包。

试题 G: 故障

时间限制: $1.0\mathrm{s}$?内存限制: $256.0\mathrm{M}\mathrm{B}$?本题总分：$20$ 分

【问题描述】

??在软件或系统开发中，我们会遇到各种各样的故障。为了从故障现象反推故障原因，工程师们会总结一种叫做相关性矩阵的二维表格，来表示故障原因与故障现象之间的关系。比如$：$

$+???+???+???+???+???+???+$
$||1|2|3|4|5|$
$+???+???+???+???+???+???+$
$|\mathrm{A}||\mathrm{x}|\mathrm{x}|\mathrm{x}||$
$+???+???+???+???+???+???+$
$|\mathrm{B}|\mathrm{x}||\mathrm{x}|||$
$+???+???+???+???+???+???+$
$|\mathrm{C}||||\mathrm{x}|\mathrm{x}|$
$+???+???+???+???+???+???+$

??其中每行表示一种故障原因，每一列表示一种故障现象。该矩阵表示故障原因 $A$ 可能产生故障现象 $2、3、4$，故障原因 $B$ 可能产生故障现象 $1、3$。

??在实际开发过程中，如果出现了故障原因，工程师就可以根据故障现象，去计算每种故障原因产生的概率，并按照概率大小对故障原因进行排查，以达到快速定位故障原因的目的。

??现在，我们假设系统开发中同一时间只会出现一种故障原因，并且故障原因引起各故障现象是独立事件。举个例子来说$：$

??假设系统现在发生了故障原因 $A$，有 $\frac{1}{3}$ 的概率出现故障现象 $2$，有 $\frac{1}{4}$ 的概率出现故障现象 $3$，有 $\frac{1}{2}$ 的概率出现故障现象 $4$。由于 $3$ 种现象是独立发生的，因此有 $\frac{1}{2\times 3\times 4}$ 的概率同时出现故障 $2、3、4$。

??约定若相关性矩阵中没有 $‘\mathrm{x}’$ 记号，则表示该故障原因一定不会产生某故障现象，比如故障原因 $A$，一定不会产生故障现象 $1$。

??根据历史经验数据，我们统计得到了每一种故障原因出现的概率以及每一种故障原因对应的故障现象产生概率。

??现在已知系统出现的故障现象，求问各个故障原因发生的概率。

【输入格式】

??第 $1$ 行$：$$2$ 个正整数 $N,M$，$N$ 表示故障原因的个数（编号 $1?N$），$M$ 表示故障现象的个数（编号 $1?M$）

??第 $2$ 行$：$$N$ 个整数，第 $i$ 个数表示故障原因 $i$ 产生的概率 $P_i$.

??第 $3?N+2$ 行$：$每行 $M+1$ 个整数，第 $i+1$ 行第 $j$ 个整数 $P_{ij}$ 表示故障原因 $i$ 出现故障现象 $j$ 的概率（百分比）$.$

??第 $N+3$ 行$：$$1$ 个正整数 $K$，表示目前出现的故障现象数量

??第 $N+4$ 行$：$$K$ 个正整数，依次为当前出现的故障现象编号，不会重复

【输出格式】

??第 $1?N$ 行$：$按概率从高到低输出每种故障原因及其可能的概率，若出现概率相同则优先输出编号小的故障原因。第 $1$ 个数为故障原因编号，第 $2$ 个数为故障概率（百分比），保留 $2$ 位小数。

【样例输入】

3 5
30 20 50
0 50 33 25 0
30 0 35 0 0
0 0 0 25 60
1
3

【样例输出】

2 56.89
1 43.11
3 0.00

【评测用例规模与约定】

??对于所有测试用例，$1\le N\le 40,1\le M\le 20,0\le P_i\le 100，\Sigma (P_i)=100，0\le P_{ij}\le 100$

出门恰个小烤肉