十一届蓝桥杯B组7月比赛题解
sdxjzsq
2020-07-20 00:36:13
# 写在前面
发现蓝桥杯7月这次省赛一等奖特别少，翟老板痛失省一，做了做题发现是真的难...
故写此题解学习总结。
参考链接：[Java实现第十一届蓝桥杯C/C++ 大学 B 组大赛软件类省赛](https://www.cnblogs.com/a1439775520/p/13258301.html#index9)
# A
## 题目
试题 A: 跑步训练
本题总分：5 分
【问题描述】
小明要做一个跑步训练。
初始时，小明充满体力，体力值计为 10000。如果小明跑步，每分钟损耗
600 的体力。如果小明休息，每分钟增加 300 的体力。体力的损耗和增加都是
均匀变化的。
小明打算跑一分钟、休息一分钟、再跑一分钟、再休息一分钟……如此循
环。如果某个时刻小明的体力到达 0，他就停止锻炼。
请问小明在多久后停止锻炼。为了使答案为整数，请以秒为单位输出答案。
答案中只填写数，不填写单位。
【答案提交】
这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个
整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
## 答案
3880（秒为单位好坑啊，而且最后剩下能量还能跑剩下多少秒的...）
```cpp
#include <cstdio>
int main()
{
int n = 10000, tot = 0;
while (1)
{
if (n >= 600) n -= 600, ++tot;
else break;
n += 300, ++tot;
}
printf("%d", tot * 60 + n / 10);
}
```
# E
## 题目
试题 E: 矩阵
本题总分：15 分
【问题描述】
把 1 ∼ 2020 放在 2 × 1010 的矩阵里。要求同一行中右边的比左边大，同一
列中下边的比上边的大。一共有多少种方案？
答案很大，你只需要给出方案数除以 2020 的余数即可。
【答案提交】
这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个
整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
## 答案
1340
令 $f[i][j]$ 表示已经填了 $i$ 个数，其中第一行填了 $j$ 个数的方案数，那么只要保证第二行填数的个数 $i-j<=j$ 就可以保证性质
因此得到动态转移方程 $f[i][j]=f[i-1][j]+f[i-1][j-1]$ (分别表示数字 $i$ 填到了第二行和第一行)
``` cpp
#include <cstdio>
const int maxn = 2050;
int f[maxn][maxn], n = 2020;
int main()
{
f[1][1] = 1;
for (int i = 2; i <= n; ++i)
for (int j = i / 2 + i % 2; j <= i; ++j)
f[i][j] = (f[i - 1][j - 1] + f[i - 1][j]) % n;
printf("%d", f[n][n/2]);
return 0;
}
```
# I
## 题目
试题 I: 整数拼接
时间限制: 1.0s 内存限制: 256.0MB 本题总分：25 分
【问题描述】
给定义个长度为 $n$ 的数组 $A_1, A_2, \cdots , 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, \cdots , A_n$ 。
【输出格式】
一个整数代表答案。
【样例输入】
```
4 2
1 2 3 4
```
【样例输出】
```
6
```
【评测用例规模与约定】
对于 30% 的评测用例，1 ≤ n≤ 1000, 1 ≤ K ≤ 20, 1 ≤ Ai ≤ 10^4。
对于所有评测用例，1 ≤ n≤ 10^5，1 ≤ K≤ 105，1 ≤ Ai ≤ 10^9。
## 题解
[蓝桥杯省赛B组 整数拼接](https://www.luogu.com.cn/blog/xjzsq/lan-qiao-bei-xing-sai-b-zu-zheng-shuo-pin-jie)
# J
## 题目
[Acwing 2069. 网络分析](https://www.acwing.com/problem/content/2071/)
## 分析
开始只想到了并查集+暴力判断是否在并查集内加信息值，后来看题解了解了类似于分块里面的tag操作，也就是把tag打到父亲上，等需要合并的时候再暴力下放标记，就能过了。思路好难，代码好简单...
## code
```cpp
#include <cstdio>
using namespace std;
const int maxn = 1e5 + 7;
int n, m, fa[maxn], tag[maxn], infor[maxn];
int find(int x) { return fa[x] = fa[x] == x ? x : find(fa[x]); }
inline void pushdown(int x)
{
for (int i = 1; i <= n; ++i)
if (find(i) == x) infor[i] += tag[x];
tag[x] = 0;
}
inline int unions(int x, int y)
{
x = find(x), y = find(y);
if (x == y) return 1;
if (tag[x]) pushdown(x);
if (tag[y]) pushdown(y);
fa[x] = y;
return 1;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) fa[i] = i;
for (int opt, a, b; m--;) scanf("%d%d%d", &opt, &a, &b), opt == 1 ? unions(a, b) : tag[find(a)] += b;
for (int i = 1; i <= n; ++i) printf("%d ", infor[i] + tag[find(i)]);
return 0;
}
```