[C++知识库]第十一届蓝桥杯 2020年省赛真题 (C/C++ 大学A组) 第一场

??打发时间。

#A 跑步训练

本题总分：$5$ 分

问题描述

??小明要做一个跑步训练。
??初始时，小明充满体力，体力值计为 $10000$。如果小明跑步，每分钟损耗 $600$ 的体力。如果小明休息，每分钟增加 $300$ 的体力。体力的损耗和增加都是均匀变化的。
??小明打算跑一分钟、休息一分钟、再跑一分钟、再休息一分钟 …… 如此循环。如果某个时刻小明的体力到达 $0$，他就停止锻炼。
??请问小明在多久后停止锻炼。为了使答案为整数，请以秒为单位输出答案。答案中只填写数，不填写单位。

答案提交

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

3880

#include <stdio.h>

int N = 10000, k = 5, ans = 0, K[2]{ 1, -1};

int main() {
	for (int opt = 1; N > 0; opt ^= 1)
		for (int i = 0; i < 60 && N > 0; i++)
			N += K[opt] * (opt + 1) * k, ++ans;
	if (N < 0) --ans;
	printf("%d", ans);
}

??简单的模拟题。

#B 合并检测

本题总分：$5$ 分

问题描述

??新冠疫情由新冠病毒引起，最近在 $\mathrm{A}$ 国蔓延，为了尽快控制疫情，$\mathrm{A}$ 国准备给大量民众进病毒核酸检测。
??然而，用于检测的试剂盒紧缺。
??为了解决这一困难，科学家想了一个办法：合并检测。即将从多个人（ $k$ 个）采集的标本放到同一个试剂盒中进行检测。如果结果为阴性，则说明这 $k$ 个人都是阴性，用一个试剂盒完成了 $k$ 个人的检测。如果结果为阳性，则说明至少有一个人为阳性，需要将这 $k$ 个人的样本全部重新独立检测（从理论上看，如果检测前 $k?1$ 个人都是阴性可以推断出第 $k$ 个人是阳性，但是在实际操作中不会利用此推断，而是将 $k$ 个人独立检测），加上最开始的合并检测，一共使用了 $k+1$ 个试剂盒完成了 $k$ 个人的检测。
??$\mathrm{A}$ 国估计被测的民众的感染率大概是 $1$%，呈均匀分布。请问 $k$ 取多少能最节省试剂盒？

答案提交

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

10

朴素解法

#include <stdio.h>

int N = 10000, ans = 100;

int calc(int k) { return N / k + N / 100 * k; }

int main() {
	for (int i = 1; i < 100; ++i)
		if (calc(i) < calc(ans)) ans = i;
	printf("%d", ans);
}

??设 $N$ 为民众人数，然后暴力枚举 $[1,100)$ 这个区间就行，因为 $k\ge 100$ 时，每个人都要重新做一遍检测，答案必不优。

数理分析

??感染人数呈均匀分布，即 p { θ = 某 民 感 染 } = 1 100 p\{\theta = 某民感染\} = \frac 1{100} p{θ=某民感染}=1001?、 p { θ = 某 民 健 康 } = 99 100 p\{\theta = 某民健康\} = \frac {99}{100} p{θ=某民健康}=10099?，

??$k$ 名群众中无有感染者，可以看作为 $k$ 重伯努利试验，其中有感染者的概率为 $\sum _{i=1}^k\left(C_k^i(\frac{1}{100}{)}^i(\frac{99}{100}{)}^{k?i}\right)$，也就说，当 $k$ 取定时，只有 $(\frac{99}{100}{)}^k$ 的分组不用重新检测，所用的试剂盒个数为 $\frac{N}{k}+N(1?(\frac{99}{100}{)}^k)$。

??设函数 $f(x)=\frac{N}{x}+N(1?(\frac{99}{100}{)}^x)$，$N$ 为一个较大常数，$f^{\prime }(x)=?\frac{N}{x^2}?N\ln \frac{99}{100}(\frac{99}{100}{)}^x=?N(x^{?2}+\ln \frac{99}{100}(\frac{99}{100}{)}^x)$，大致能看出 $f(x)$ 在 $[1,100)$ 的极小值在 $(10,11)$ 之间，可以说 $10$、$11$ 都是对的。

??但赛委组怎么考虑这道题的，我就不得而知了。

#C 分配口罩

本题总分：$10$ 分

问题描述

??某市市长获得了若干批口罩，每一批口罩的数目如下：（如果你把以下文字复制到文本文件中，请务必检查复制的内容是否与文档中的一致。在试题目录下有一个文件 mask.txt，内容与下面的文本相同）

9090400
8499400
5926800
8547000
4958200
4422600
5751200
4175600
6309600
5865200
6604400
4635000
10663400
8087200
4554000

??现在市长要把口罩分配给市内的 2 所医院。由于物流限制，每一批口罩只能全部分配给其中一家医院。市长希望 2 所医院获得的口罩总数之差越小越好。请你计算这个差最小是多少？

答案提交

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

2400

#include <stdio.h>

int n, i, cnt, sum, ans = 0x3F3F3F3F, A[1000];

int abs(int a) { return a > 0 ? a : -a; }

int main() {
	freopen("mask.txt", "r", stdin);
	while (~scanf("%d", &A[n])) sum += A[n++];
	for (int k = 1 << n; --k;) {
		for (cnt = i = 0; i < n; ++i)
			if (k >> i & 1) cnt += A[i];
		if (abs(sum - 2 * cnt) < ans) ans = abs(sum - 2 * cnt);
	}
	printf("%d", ans);
}

??$n$ 比较小，可以直接枚举所有可能的分配，当 $n$ 大了可以尝试在 $\mathrm{m}\mathrm{a}\mathrm{p}$ 上做个背包 $\mathrm{d}\mathrm{p}$，但写起来可能有点恶心，这里就不实现了。

#D 矩阵

本题总分：$10$ 分

问题描述

??把 $1～2020$ 放在 $2\times 1010$ 的矩阵里。要求同一行中右边的比左边大，同一 列中下边的比上边的大。一共有多少种方案？
??答案很大，你只需要给出方案数除以 $2020$ 的余数即可。

答案提交

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

1340

动态规划

// 等会写

勾长公式

??将 $2\times 1010$ 的矩阵看作杨表，则其方案数有勾长公式$$\dim {\pi }_{\lambda }=\frac{n!}{{\prod }_{x\in Y(\lambda )}\mathrm{h}\mathrm{o}\mathrm{o}\mathrm{k}(x)}=\frac{2020!}{1011!1010!}(\mathrm{m}\mathrm{o}\mathrm{d}2020)$$

??由于模数非质、因子较小且连续，故不采用扩展欧几里得求逆元，直接统计质因子质数再将其相乘即可。

#include <bits/stdc++.h>

using namespace std;

map<int, int> factor[2021];

vector<int> primes;

int ans = 1;

int main() {
	for (int i = 2; i <= 2020; ++i) {
		if (!factor[i][0]) {
			primes.push_back(i);
			factor[i][i] = 1;
		}
		for (int p : primes) {
			if (p * i > 2020) break;
			factor[p * i] = factor[i];
            factor[p * i][0] = 1;
			factor[p * i][p]++;
			if (i % p == 0) break;
		}
	}
	for (int i = 1; i <= 1010; ++i)
		for (auto &p : factor[i]) factor[2020][p.first] -= p.second;
    for (int i = 1012; i < 2020; ++i)
        for (auto &p : factor[i]) factor[2020][p.first] += p.second;
    for (auto &p : factor[2020]) 
        for (int i = 0; i < p.second; ++i) if (p.first) ans = ans * p.first % 2020;
    printf("%d", ans);
}

??上当了，应该用扩欧的。

??当然，如果会点 $\mathrm{P}\mathrm{y}\mathrm{t}\mathrm{h}\mathrm{o}\mathrm{n}$ 的话：

ans = 1
for i in range(1, 1011):
    ans = ans * (i + 1011) // i
print(ans % 2020)

#E 完美平方数

本题总分：$15$ 分

问题描述

??如果一个整数本身是完全平方数，它的每一位组成数字也是完全平方数，我们就称它是完美平方数。

??前几个完美平方数是 $0、1、4、9、49、100、144??$

??即第 $1$ 个完美平方数是 $0$，第 $2$ 个是 $1$，第 $3$ 个是 $4$，$??$

??那么，第 $2020$ 个完美平方数是多少？

答案提交

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

1499441040

#include <stdio.h>

int N = 2020, ans = 0;

bool check(int n) { return !n || n == 1 || n == 4 || n == 9; }

int main() {
    while  (N) {
        bool flag = 1;
        for (int n = ans * ans; n; n /= 10)
            if(!check(n % 10)) flag = 0;
        if (flag) --N;
        if (N) ans++;
    }
    printf("%d", ans * ans);
}

??设答案与 $N=2020$ 的关系为 $f(N)$，则对于几种常见的枚举对象，它们的复杂度是。

??$O(f(N))$，枚举 $1～f(x)$ 中的每一个数。

??$O(4^{\log f(N)})$，枚举 $1～f(x)$ 中的能被 $0,1,4,9$ 组合成的数。

??$O(\sqrt{f(N)})$，枚举 $1～f(x)$ 中的完全平方数。

??对于第一种，它的运行耗时显然不是我们所能接受，对于第二种则需要我们对于答案的特征，如它的位数有着快速准确的判断，来避免在调试程序花费不必要的时间。

??总之保持对时间复杂度的敏感程度，至少可以避免你选择到最差解。

#F 解码

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

问题描述

??小明有一串很长的英文字母，可能包含大写和小写。
??在这串字母中，有很多连续的是重复的。小明想了一个办法将这串字母表达得更短：将连续的几个相同字母写成字母 $+$ 出现次数的形式。
??例如，连续的 $5$ 个 $\mathrm{a}$ ，即 $\mathrm{a}\mathrm{a}\mathrm{a}\mathrm{a}\mathrm{a}$ ，小明可以简写成 $\mathrm{a}5$ （也可能简写成 $\mathrm{a}4\mathrm{a}$ 、 $\mathrm{a}\mathrm{a}3\mathrm{a}$ 等）。
??对于这个例子：$\mathrm{H}\mathrm{H}\mathrm{H}\mathrm{e}\mathrm{l}\mathrm{l}\mathrm{l}\mathrm{l}\mathrm{l}\mathrm{o}\mathrm{o}$ ，小明可以简写成 $\mathrm{H}3\mathrm{e}\mathrm{l}5\mathrm{o}2$。为了方便表达，小明不会将连续的超过 $9$ 个相同的字符写成简写的形式。
??现在给出简写后的字符串，请帮助小明还原成原来的串。

输入格式

??输入一行包含一个字符串。

输出格式

??输出一个字符串，表示还原后的串。

测试样例₁

Input：
H3el5o2

Output：
HHHellllloo

评测用例规模与约定

??对于所有评测用例，字符串由大小写英文字母和数字组成，长度不超过 $100$。
??请注意原来的串长度可能超过 $100$。

#include <stdio.h>

char s[2020];

int main() {
    scanf("%s", s);
    for (int i = 0; s[i]; ++i) {
        if (s[i] > '9') putchar(s[i]);
        else while (s[i]-- > '1') putchar(s[i - 1]);
    }
}

??签到。

#G 走方格

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

问题描述

??在平面上有一些二维的点阵。
??这些点的编号就像二维数组的编号一样，从上到下依次为第 $1$ 至第 $n$ 行，从左到右依次为第 $1$ 至第 $m$ 列，每一个点可以用行号和列号来表示。
??现在有个人站在第 $1$ 行第 $1$ 列，要走到第 $n$ 行第 $m$ 列。
??只能向右或者向下走。
??注意，如果行号和列数都是偶数，不能走入这一格中。
??问有多少种方案。

输入格式

??输入一行包含两个整数 $n,m$。

输出格式

??输出一个整数，表示答案。

测试样例₁

Input：
3 4

Output：
2

评测用例规模与约定

??对于所有评测用例，$1\le n\le 30,1\le m\le 30$。

#include <stdio.h>

int n, m, dp[50][50] = {0, 1};

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (i & 1 || j & 1) dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    printf("%d", dp[n][m]);
}

??二连签到。

#H 整数小拼接

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

问题描述

??给定一个长度为 $n$ 的数组 $A_1,A_2,?,A_n$。你可以从中选出两个数 $A_i$ 和 $A_j$ ($i$ 不等于 $j$) ，然后将 $A_i$ 和 $A_j$ 一前一后拼成一个新的整数。例如 $12$ 和 $345$ 可以拼成 $12345$ 或 $34512$ 。注意交换 $A_i$ 和 $A_j$ 的顺序被视为 $2$ 种拼法，即便是 $A_i=A_j$ 时。
??请你计算有多少种拼法满足拼出的整数小于等于 $K$。

输入格式

??第一行包含 $2$ 个整数 $n$ 和 $K$。
??第二行包含 $n$ 个整数 $A_1,A_2,?,A_n$。

输出格式

??输出一个整数，表示答案。

测试样例₁

Input：
4 33
1 2 3 4

Output：
8

评测用例规模与约定

??对于 $30$% 的评测用例，$1\le n\le 1000,1\le K\le 10^8,1\le A_i\le 10^4$。
??对于所有评测用例，$1\le n\le 100000,1\le K\le 10^{10},1\le A_i\le 10^9$。

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

long long K, ans, A[100010];

int n;

int main() {
    scanf("%d %lld", &n, &K);
    for (int i = 0; i < n; ++i)
        scanf("%d", &A[i]);
    std::sort(A, &A[n]);
    for (int i = 0; i < n; ++i) {
        long long k = 1;
        while (A[i] >= k) k *= 10;
        long long *find = std::upper_bound(A, &A[n], K / k - (K % k < A[i]));
        if (find > &A[i]) --ans;
        ans += find - A;
    }
    printf("%lld", ans);
}

??签到三连。

??$\mathrm{S}\mathrm{T}\mathrm{L}$ 好用的想转 $\mathrm{C}$。

#I 超级胶水

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

问题描述

??小明有 $n$ 颗石子，按顺序摆成一排，他准备用胶水将这些石子粘在一起。
??每颗石子有自己的重量，如果将两颗石子粘在一起，将合并成一颗新的石子，重量是这两颗石子的重量之和。
??为了保证石子粘贴牢固，粘贴两颗石子所需要的胶水与两颗石子的重量乘积成正比，本题不考虑物理单位，认为所需要的胶水在数值上等于两颗石子重量的乘积。
??每次合并，小明只能合并位置相邻的两颗石子，并将合并出的新石子放在原来的位置。
??现在，小明想用最少的胶水将所有石子粘在一起，请帮助小明计算最少需要多少胶水。

输入格式

??输入的第一行包含一个整数 $n$，表示初始时的石子数量。
??第二行包含 $n$ 个整数 $w_1,w_2,\dots ,w_n$?，依次表示每颗石子的重量。

输出格式

??输出一行包含一个整数，表示最少需要的胶水数。

测试样例₁

Input：
3
3 4 5

Output：
47

测试样例₂

Input：
8
1 5 2 6 3 7 4 8

Output：
546

评测用例规模与约定

??对于 $20$% 的评测用例，$1\le n\le 15$。
??对于 $60$% 的评测用例，$1\le n\le 100$。
??对于 $80$% 的评测用例，$1\le n\le 1000$。
??对于所有评测用例，$1\le n\le 100000,1\le w_i\le 1000$。

// 歇会

#J 网络分析

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

问题描述

??小明正在做一个网络实验。
??他设置了 $n$ 台电脑，称为节点，用于收发和存储数据。
??初始时，所有节点都是独立的，不存在任何连接。
??小明可以通过网线将两个节点连接起来，连接后两个节点就可以互相通信了。两个节点如果存在网线连接，称为相邻。
??小明有时会测试当时的网络，他会在某个节点发送一条信息，信息会发送到每个相邻的节点，之后这些节点又会转发到自己相邻的节点，直到所有直接或间接相邻的节点都收到了信息。所有发送和接收的节点都会将信息存储下来。一条信息只存储一次。
??给出小明连接和测试的过程，请计算出每个节点存储信息的大小。

输入格式

??输入的第一行包含两个整数 $n,m$，分别表示节点数量和操作数量。节点从 $1$ 至 $n$ 编号。
??接下来 $m$ 行，每行三个整数，表示一个操作。
??如果操作为 $1ab$，表示将节点 $a$ 和节点 $b$ 通过网线连接起来。当 $a=b$ 时，表示连接了一个自环，对网络没有实质影响。
??如果操作为 $2pt$，表示在节点 $p$ 上发送一条大小为 $t$ 的信息。

输出格式

??输出一行，包含 $n$ 个整数，相邻整数之间用一个空格分割，依次表示进行完上述操作后节点 $1$ 至节点 $n$ 上存储信息的大小。

测试样例₁

Input：
4 8
1 1 2
2 1 10
2 3 5
1 4 1
2 2 2
1 1 2
1 2 4
2 2 1

Output：
13 13 5 3

评测用例规模与约定

??对于 $30$% 的评测用例，$1\le n\le 20，1\le m\le 100$。
??对于 $50$% 的评测用例，$1\le n\le 100，1\le m\le 1000$。
??对于 $70$% 的评测用例，$1\le n\le 1000，1\le m\le 10000$。
??对于所有评测用例，$1\le n\le 10000，1\le m\le 100000，1\le t\le 100$。

// 歇会