CC++描述第十一届蓝桥杯省赛CC++大学B组第一场(2020.7.5) 题目+题解

比眉伴天荒 2023-02-23 12:08 36阅读 0赞

### 文章目录 ###

*   *  写在前面
     *  试题 A: 指数计算
     *  试题 A 题解
     *  试题 B: 解密
     *  试题 B 题解
     *  试题 C: 跑步训练
     *  试题 C 题解
     *  试题 D: 合并检测
     *  试题D 题解
     *  试题 E: REPEAT 程序
     *  试题 F: 分类计数
     *  试题F 题解
     *  试题 G: 整除序列
     *  试题G 题解
     *  试题 H: 走方格
     *  试题H 题解
     *  试题 I: 字符串编码
     *  试题I 题解
     *  试题 J: 整数小拼接
     *  试题J题解

## 写在前面 ##

>  写在前面：大家好！我是`ACfun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

> 本文转载自[亓官劼][Link 1]

## 试题 A: 指数计算 ##

本题总分：5 分

【问题描述】

7 月 1 日是建党日，从 1921 年到 2020 年，Communist Party of China已经带领中国人民走过了 99 年。

请计算：7 ^ 2020 mod 1921，其中 A mod B 表示 A 除以 B 的余数。

【答案提交】

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

## 试题 A 题解 ##

第一题`大数问题`直接打开机器上的Python环境，直接算。

print((7**2020)%1921)

答案为：`480`

## 试题 B: 解密 ##

本题总分：5 分

【问题描述】

小明设计了一种文章加密的方法：对于每个字母 c，将它变成某个另外的  
字符 Tc。下表给出了字符变换的规则：

例如，将字符串 YeRi 加密可得字符串 EaFn。小明有一个随机的字符串，加密后为EaFnjISplhFviDhwFbEjRjfIBBkRyY（由 30 个大小写英文字母组成，不包含换行符），请问原字符串是多少？

（如果你把以上字符串和表格复制到文本文件中，请务必检查复制的内容  
是否与文档中的一致。在试题目录下有一个文件 str.txt，第一行为上面的字符  
串，后面 52 行依次为表格中的内容。）

【答案提交】

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

## 试题 B 题解 ##

这里如果有src.txt这个文件的话，可以直接写个Python程序，读入后输入EaFnjISplhFviDhwFbEjRjfIBBkRyY，找出原字符即可。

这里我没那个文件，就直接复制表格了，粘贴的时候发现还是一行一行的来的，不过没关系，这个字符串直接处理了就好了，Python程序为：

s = 'aynlAYNLbxogBXOGcmpoCMPOddquDDQUearfEARFfcssFCSSgitzGITZhkupHKUPinvwINVWjtwbJTWBkjxrKJXRlhyeLHYEmqzvMQZV'
    dir = { }
    for i in range(len(s)):
        if(i%2 == 1):
            dir[s[i]] = s[i-1]
    a = 'EaFnjISplhFviDhwFbEjRjfIBBkRyY'
    for item in a:
        print(dir[item],end='',sep='')

答案为：`YeRikGSunlRzgDlvRwYkXkrGWWhXaA`

## 试题 C: 跑步训练 ##

本题总分：10 分

【问题描述】

小明要做一个跑步训练。初始时，小明充满体力，体力值计为 10000。如果小明跑步，每分钟损耗600 的体力。如果小明休息，每分钟增加 300 的体力。体力的损耗和增加都是均匀变化的。

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

环。如果某个时刻小明的体力到达 0，他就停止锻炼。  
 请问小明在多久后停止锻炼。为了使答案为整数，请以秒为单位输出答案。

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

【答案提交】

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

## 试题 C 题解 ##

这里可以口算：答案为：`3880`

10000 / (600-300) == 33.33
    33*(600-300) = 9900
    10000 - 9900 + 300 = 400 < 600
    所以时间为32*2*60 + 400/10 = 3880

也可以写程序模拟:

energy = 10000
    min = 0
    second = 0
    while(energy):
        min += 1
        if min % 2 == 1:
            if energy > 600 :
                energy -= 600
            else:
                min -= 1
                second = energy/10
                energy = 0
        else:
            energy += 300
        if energy <= 0:
            break
    print(min*60+second)

答案：`3380`

## 试题 D: 合并检测 ##

本题总分：10 分

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

A 国估计被测的民众的感染率大概是 1%，呈均匀分布。请问 k 取多少能最节省试剂盒？

【答案提交】

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

## 试题D 题解 ##

这题数学问题
    设总人数为pop,感染率p,每次k人，总市级数sum
    sum = ([pop/k]+1)*(1+k*p(k+1))
    这里的[pop/k]+1)即pop/k向上取整
    [pop/k]+1)这里由于pop数量较大，所以这里向上取整的1可以忽略，这里直接取了pop/k，即
    sum = (pop/k)*(1+kp(k+1))
    将p代入sum = (pop/k)*(1+k*0.01(k+1))
    sum求导 = (pop/k)(0.01k-1/k)
    可得当k = 10时，sum取最小值
    所以K = 10

答案：`10`

## 试题 E: REPEAT 程序 ##

本题总分：15 分

【问题描述】

附件 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 的值是多少？

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

## 试题 F: 分类计数 ##

时间限制: 1.0s 内存限制: 512.0MB 本题总分：15 分

【问题描述】

输入一个字符串，请输出这个字符串包含多少个大写字母，多少个小写字  
母，多少个数字。

【输入格式】

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

【输出格式】

输出三行，每行一个整数，分别表示大写字母、小写字母和数字的个数。

【样例输入】

1+a=Aab

【样例输出】

【评测用例规模与约定】

对于所有评测用例，字符串由可见字符组成，长度不超过 100。

## 试题F 题解 ##

C/C++描述程序为：

#include <iostream>
    using namespace std;
    int main(){ 
        string in;
        cin>>in;
        int num_digital,num_capital,num_lowercase;//数字，大写字母，小写字母的数量
        num_capital = num_digital = num_lowercase = 0;
        int len_in = in.length();
        for(int i = 0;i < len_in;i++){ 
            if(in[i] <= '9' && in[i] >= '0')
                num_digital++;
            if((in[i] <= 'Z' && in[i] >= 'A'))
                num_capital++;
            if(in[i] <= 'z' && in[i] >= 'a')
                num_lowercase++;
        }
        cout<<num_capital<<endl<<num_lowercase<<endl<<num_digital;
        return 0;
    }

## 试题 G: 整除序列 ##

时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分

【问题描述】

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

【输入格式】

输入一行包含一个整数 n。

【输出格式】

输出一行，包含多个整数，相邻的整数之间用一个空格分隔，表示答案。

【样例输入】

【样例输出】

20 10 5 2 1

【评测用例规模与约定】

对于 80% 的评测用例，1 ≤ n ≤ 109。

对于所有评测用例，1 ≤ n ≤ 1018。

## 试题G 题解 ##

签到题

#include <iostream>
    using namespace std;
    int main(){ 
        int n;
        cin>>n;
        while(n){ 
            cout<<n<<" ";
            n/=2;
        }
        return 0;
    }

## 试题 H: 走方格 ##

时间限制: 1.0s 内存限制: 512.0MB 本题总分：20 分

【问题描述】

在平面上有一些二维的点阵。这些点的编号就像二维数组的编号一样，从上到下依次为第 1 至第 n 行，从左到右依次为第 1 至第 m 列，每一个点可以用行号和列号来表示。现在有个人站在第 1 行第 1 列，要走到第 n 行第 m 列。只能向右或者向下走。

注意，如果行号和列数都是偶数，不能走入这一格中。

问有多少种方案。

【输入格式】

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

【输出格式】

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

【样例输入】

3 4

【样例输出】

【样例输入】

6 6

【样例输出】

【评测用例规模与约定】

对于所有评测用例，1 ≤ n ≤ 30, 1 ≤ m ≤ 30。

## 试题H 题解 ##

数据量小直接暴力搜

#include <iostream>
    #include <vector>
    using namespace std;
    int main(){ 
        int n,m;
        cin>>n>>m;
        vector<vector<int>> dp(n+1,vector<int>(m+1));
        for(int i = 1;i <= n;i++){ 
            dp[i][1] = 1;
        }
        for (int j = 1; j <= m; ++j) { 
            dp[1][j] = 1;
        }
        for(int i = 2;i <= n;i++){ 
            for (int j = 2; j <= m; ++j) { 
                if(i%2==0 && j%2==0)
                    continue;
                else
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        cout<<dp[n][m];
        return 0;
    }

## 试题 I: 字符串编码 ##

时间限制: 1.0s 内存限制: 512.0MB 本题总分：25 分

【问题描述】

小明发明了一种给由全大写字母组成的字符串编码的方法。对于每一个大写字母，小明将它转换成它在 26 个英文字母中序号，即 A → 1, B → 2, … Z →26。

这样一个字符串就能被转化成一个数字序列：比如 ABCXYZ → 123242526。

现在给定一个转换后的数字序列，小明想还原出原本的字符串。当然这样的还原有可能存在多个符合条件的字符串。小明希望找出其中字典序最大的字符串。

【输入格式】

一个数字序列。

【输出格式】

一个只包含大写字母的字符串，代表答案

【样例输入】

123242526

【样例输出】

LCXYZ

【评测用例规模与约定】

对于 20% 的评测用例，输入的长度不超过 20。

对于所有评测用例，输入的长度不超过 200000。

## 试题I 题解 ##

#include <iostream>
    #include <vector>
    using namespace std;
    int main(){ 
        string in ;
        cin>>in;
        int len = in.length();
        string re = "";
        int flag_1;//第一位为1
        int flag_2;//第一位为2
        flag_1 = flag_2 = 0;
        for(int i = 0;i < len;i++){ 
            if(flag_1){ 
                int mid = int(in[i-1]-'0')*10+int(in[i]-'0');
                re += char(mid+'A'-1);
                flag_1 = 0;
                continue;
            }
            if(flag_2){ 
                if(in[i]<='6'){ 
                    int mid = int(in[i-1]-'0')*10+int(in[i]-'0');
                    re += char(mid+'A'-1);
                    flag_2 = 0;
                } else{ 
                    re += char(in[i-1] - '0' +'A'-1);
                    re += char(in[i] - '0' +'A'-1);
                    flag_2 = 0;
                }
                continue;
            }
            if(in[i] >= '3')
                re += char(in[i] - '0' + 'A' - 1);
            if(in[i] == '1' ){ 
                if(i+2<=len-1 && in[i] == '0'){ 
                    re += char(in[i] - '0' + 'A' - 1);
                    continue;
                }
                flag_1 = 1;
            }
            if(in[i] == '2'){ 
                if(i+2<=len-1 && in[i] == '0'){ 
                    re += char(in[i] - '0' + 'A' - 1);
                    continue;
                }
                flag_2 = 1;
            }
        }
        cout<<re;
        return 0;
    }

## 试题 J: 整数小拼接 ##

时间限制: 1.0s 内存限制: 512.0MB 本题总分：25 分

【问题描述】

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

请你计算有多少种拼法满足拼出的整数小于等于 K。

【输入格式】

第一行包含 2 个整数 n 和 K。

第二行包含 n 个整数 A1, A2, · · · , An。

【输出格式】

一个整数代表答案。

【样例输入】

4 33

1 2 3 4

【样例输出】

【评测用例规模与约定】

对于 30% 的评测用例，1 ≤ N ≤ 1000, 1 ≤ K ≤ 108, 1 ≤ Ai ≤ 104。

对于所有评测用例，1 ≤ N ≤ 100000，1 ≤ K ≤ 1010，1 ≤ Ai ≤ 109。

## 试题J题解 ##

#include <iostream>
    #include <vector>
    #include <cmath>
    using namespace std;
    int get_len(int n){ 
       int len = 1;
       n/=10;
       while (n){ 
           len++;
           n/=10;
       }
       return len;
    }
    
    typedef struct ds{ 
       int data;
       int len;
    }ds;
    
    bool cmp(ds a,ds b){ 
       if(a.len < b.len)
           return 1;
       else
           return 0;
    }
    int main(){ 
       int n;
       long long int k;
       cin>>n>>k;
       int mid = k;
       int len_k = 0;
       while (mid){ 
           len_k++;
           mid/=10;
       }
       vector<ds> store;
       for (int i = 0; i < n; ++i) { 
           // 蓝桥杯中long long int 读取需要使用%I64d
           scanf("%d",&mid);
           int len_mid = get_len(mid);
           if(len_mid < len_k)
               store.push_back({ mid,len_mid});
       }
       // 按长度从下到大排序
       sort(store.begin(),store.end(),cmp);
       int i = 0,num=0;
       // 找出长度小于k长度1/2的，之前全排列
       while (store[i].len < len_k/2){ 
           num++;
           i++;
       }
       // 去除前num个
       for(int j = 0; j < num;j++)
           store.erase(store.begin());
       int sum = 0;
       if(num){ 
           sum = 1;
           while (num){ 
               sum *= num;
               num--;
           }
       }
    
       int len_store = store.size();
       // 下面剩下程度为len_k/2 到len_k -1的，直接暴力吧
       for (int i = 0; i < len_store; ++i) { 
           for (int j = 0; j < i; ++j) { 
               mid = store[i].data*pow(10,store[j].len) + store[j].data;
               if(mid<k)
                   sum++;
           }
           for (int j = i+1; j < len_store; ++j) { 
               mid = store[i].data*pow(10,store[j].len) + store[j].data;
               if(mid<k)
                   sum++;
           }
       }
       cout<<sum;
       return 0;
    }

[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[Link 1]: https://blog.csdn.net/qq_43422111?t=1