十一届蓝桥杯B组7月比赛题解

2020-07-20 00:36:13


写在前面

发现蓝桥杯7月这次省赛一等奖特别少,翟老板痛失省一,做了做题发现是真的难...
故写此题解学习总结。
参考链接:Java实现第十一届蓝桥杯C/C++ 大学 B 组大赛软件类省赛

A

题目

试题 A: 跑步训练 本题总分:5 分

【问题描述】

小明要做一个跑步训练。

初始时,小明充满体力,体力值计为 10000。如果小明跑步,每分钟损耗

600 的体力。如果小明休息,每分钟增加 300 的体力。体力的损耗和增加都是

均匀变化的。

小明打算跑一分钟、休息一分钟、再跑一分钟、再休息一分钟……如此循

环。如果某个时刻小明的体力到达 0,他就停止锻炼。

请问小明在多久后停止锻炼。为了使答案为整数,请以秒为单位输出答案。

答案中只填写数,不填写单位。

【答案提交】

这是一道结果填空题,你只需要算出结果后提交即可。本题的结果为一个

整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

答案

3880(秒为单位好坑啊,而且最后剩下能量还能跑剩下多少秒的...)

#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$ 填到了第二行和第一行)

#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组 整数拼接

J

题目

Acwing 2069. 网络分析

分析

开始只想到了并查集+暴力判断是否在并查集内加信息值,后来看题解了解了类似于分块里面的tag操作,也就是把tag打到父亲上,等需要合并的时候再暴力下放标记,就能过了。思路好难,代码好简单...

code

#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;
}