2020 第十一届蓝桥杯大赛软件赛省赛（第一场），C/C++大学B组题解

第1题 —— 跑步训练 （5分）

• 题目：

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

• 首先求每秒的消耗，然后模拟跑步休息的过程即可
• 答案是3880

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n = 10000;
    int v = 600/60;
    int minues = 0;
    while(n){
        if(n-600<0){
            cout<<minues*60+n/v<<"\n";
            return 0;
        }
        n -= 600;
        n += 300;
        minues += 2;
    }
    return 0;
}

第2题 —— 纪念日 （5分）

• 题目：

2020 年7 月1 日是中国共产党成立99 周年纪念日。
中国共产党成立于1921 年7 月23 日。
请问从1921 年7 月23 日中午12 时到2020 年7 月1 日中午12 时一共包含多少分钟？

• 直接excel

• 也可以枚举每一年，手动判断闰年累加

#include<bits/stdc++.h>
using namespace std;

int main(){
    int res = 0;
    for(int i = 1922; i <= 2020; i++){
        if(i%400==0 || (i%100!=0&&i%4==0))res += 366;
        else res += 365;
    }
    res -= 22;
    cout<<res*24*60;
    return 0;
}

• 答案 52038720

第3题 —— 合并检测 （10分）

• 题目

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

• 感染率为1，设测试人员为100，则1人感染，当k可以被100整除时则100/k+k，不可以被100整除则100/k+k+1。暴力枚举1-100，更新最小的k。
• 答案是10

#include<bits/stdc++.h>
using namespace std;

int main(){
    int kk, res = 100;
    for(int k = 1; k <= 100; k++){
        if(100%k==0){
            int t = 100/k+k;
            if(t<res)kk=k, res=t;
        }else{
            int t = 100/k+k+1;
            if(t<res)kk=k,res=t;
        }
    }
    cout<<kk<<"\n";
    return 0;
}

第4题 —— REPEAT程序 （10分）

• 题目：

附件 prog.txt 中是一个用某种语言写的程序。
其中 REPEAT k 表示一个次数为 k 的循环。循环控制的范围由缩进表达，从次行开始连续的缩进比该行多的（前面的空白更长的）为循环包含的内容。
例如如下片段：
REPEAT 2:
 A = A + 4
  REPEAT 5:
  REPEAT 6:
   A = A + 5
  A = A + 7
 A = A + 8
A = A + 9
该片段中从 A = A + 4 所在的行到 A = A + 8 所在的行都在第一行的循环两次中。
REPEAT 6: 所在的行到 A = A + 7 所在的行都在 REPEAT 5: 循环中。
A = A + 5 实际总共的循环次数是 2 × 5 × 6 = 60 次。
请问该程序执行完毕之后，A 的值是多少？

• 把repeat换成for模拟即可。
• 答案是403

#include<bits/stdc++.h>
using namespace std;

int main(){
    int res = 0;
    for(int i = 0; i < 2; i++){
        res += 4;
        for(int j = 0; j < 5; j++){
            for(int k = 0; k < 6; k++){
                res += 5;
            }
            res += 7;
        }
        res += 8;
    }
    res += 9;
    cout<<res<<"\n";
    return 0;
}

第5题 —— 矩阵 （15分）

• 题目

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

• 令fij表示第一行放了i个数，第二行放了j个数时的方案数。

初始状态为两行一个数字都不放f00算一种方案。
转移时考虑把当前数第i+j个数，放到第一行或第二行，对应的+=fi-1j或fij-1即可。

• 也可以考虑放了一个数以后，下一个数一定放在右边或下面一行，且下面一行满足所有时刻数量要小于第一行的，不然后面就会有数不得不被放到第一行去。
• 答案：1340

#include<bits/stdc++.h>
using namespace std;
int f[1020][1020];

int main(){
    f[0][0] = 1;
    for(int i = 0; i <= 1010; i++){
        for(int j = 0; j <= 1010; j++){
            if(j+1 <= i)f[i][j] += f[i-1][j]%2020;
            if(j>0)f[i][j] += f[i][j-1]%2020;
        }
    }
    cout<<f[1010][1010];
    return 0;
}

第6题 —— 整除序列 （15分）

• 题目：

有一个序列，序列的第一个数是n，后面的每个数是前一个数整除2，请输
出这个序列中值为正数的项。

• 每次除2就行，即可开ll

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

int main(){
    LL n;  cin>>n;
    while(n){
        cout<<n<<" ";
        n /= 2;
    }
    return 0;
}

第7题 —— 解码 （20分）

• 题目

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

• 对于输入的字符串模拟即可

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

int main(){
    string s;  cin>>s;
    for(int i = 0; i < s.size(); i++){
        if(isalpha(s[i]) && isdigit(s[i+1])){
            cout<<string(s[i+1]-'0', s[i]);
            i++;
        }else{
            cout<<s[i];
        }
    }
    return 0;
}

第8题 —— 走方格 （20分）

• 题目：

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

• 只能向下或向右走，所以转移为左边或上面的加起来，状态fij为到ij的方案数。
• 对于行号列号为偶数，不能走的点，直接加个if不加上去就行

#include<bits/stdc++.h>
using namespace std;
int f[110][110];

int main(){
    int n, m;  cin>>n>>m;
    for(int i = 1; i <= n; i++)f[i][1] = 1;
    for(int i = 1; i <= m; i++)f[1][i] = 1;
    for(int i = 2; i <= n; i++){
        for(int j = 2; j <= m; j++){
            if(i%2==0 && j%2==0)continue;
            f[i][j] = f[i-1][j]+f[i][j-1];
        }
    }
    cout<<f[n][m];
    return 0;
}

第9题 —— 整数拼接 （25分）

• 题目

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

• 考虑若a，b拼接，a放在前面，则产生的新的a最后也就*10^20，最后20个数，即将n的范围乘20以后，可以得到所有的数，问题转化为20000个数选两个相加%k==0， 可以直接预处理出%k的余数，枚举对于每个数（指定后缀长度）后，相加能得到的k的倍数的个数累加即可。
• 预处理 cntlen 表示满足 a[i] ∗ 10^len % k = x 的 i 的个数
• 对于每个 a[j] ，找满足 a[i] ∗ 10^len(a[j]) % k = ( k − a[j] % k ) % k 的 i 的个数即可

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn = 1e5+10;

LL a[maxn];
LL p[20], cnt[20][maxn];

int main(){
    LL n, k;  cin>>n>>k;
    for(int i=1; i <= n; i++)cin>>a[i];
    for(int i = 1; i < 20; i++)p[i]=p[i-1]*10%k;
    for(int i = 1; i <= n; i++){//对于每个数
        for(int len = 0; len < 20; len++){//分别乘1~20以后,%k的余数
            cnt[len][a[i]*p[len]%k]++;
        }
    }
    LL res = 0;
    for(int i = 1; i <= n; i++){
        for(int len=0; len<20; len++)cnt[len][a[i]*p[len]%k]--;//自己不能放到自己前面
        int len = to_string(a[i]).size();
        res += cnt[len][((k-a[i])%k+k)%k]; //a[i]放在后面，len为长度,k-a[i]的个数
        for(int len=0; len<20; len++)cnt[len][a[i]*p[len]%k]++;
    }
    cout<<res<<"\n";
    return 0;
}

第10题 —— 网络分析 （25分）

• 题目

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

• n个点，有些点相连，从某点发信息，能联通的点信息+1，求m次操作以后，每个点的信息大小
• 并查集板子
• 对于每次联通块加一个值，如果遍历出所有的联通块，可能会超时，所以可以打个懒标记lazy，每次合并前把每个节点的值都更新一下即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn = 1e5+10;

int n, m;
int v[maxn], lazy[maxn]; 

int fa[maxn+10];
void init(int n){for(int i = 0; i <= n; i++)fa[i]=i;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x, int y){
    x=find(x);y=find(y);
    if(x!=y){
        for(int i = 1; i <= n; i++){//合并前把每个节点的值都更新一下,pushdown
            v[i] += lazy[find(i)];
        }
        memset(lazy,0,sizeof(lazy));
        fa[x]=y;
    }
}

int main(){
    cin>>n>>m;
    init(maxn-10);
    for(int i = 1; i <= m; i++){
        int a, b, c;  cin>>a>>b>>c;
        if(a==1){
            merge(b,c);
        }else{
            lazy[find(b)] += c;//联通块b+=c, 延迟更新
        }
    }
    for(int i = 1; i <= n; i++){
        cout<<v[i]+lazy[find(i)]<<" ";
    }
    return 0;
}