# A:指数计算(5分)

【问题描述】

7月1日是建党日,从1921年到2020年,中国共产党已经带领中国人民走过了99年。 请计算:7^2020 mod 1921,其中A mod B 表示 A 除以 B 的余数。

【答案提交】

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

【解题思路】

拿到这道题,我还想着用写程序的方式去解决,写程序咋写呢,最开始想的就是在7乘的中间进行取余,为此我还找个小数手稿验证了一下,但是结果是不对的,事后想想这样确实不对。最后想到了以前用过分治的方式写过阶层求值,在合并的时候正好可以进行取余运算,正好求解了此问题。其实还有更简单的,使用电脑的计算器就行,考试的时候还是要怎么简单怎么做。

#include<iostream>
using namespace std;
int dfs(int n){
	if(n==1){
		return 7;
	}
	if(n%2==0){
		return (dfs(n/2)*dfs(n/2))%1921;
	}
	else if(n%2!=0){
		return (dfs(n/2)*dfs(n/2)*7)%1921;
	}
}
int main()
{
	cout << dfs(2020);
	return 0;
}

【答案】

480

# B:解密(5分)

【问题描述】

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

字母c Tc 字母c Tc 字母c Tc 字母c Tc
a y n l A Y N L
b x o g B X O G
c m p o C M P O
d d q u D D Q U
e a r f E A R F
f c s s F C S S
g i t z G I T Z
h k u p H K U P
i n v w I N V W
j t w b J T W B
k j x r K J X R
l h y e L H Y E
m q z v M Q Z V

例如,将字符串 YeRi 加密可得字符串 EaFn。 小明有一个随机的字符串,加密后为 EaFnjISplhFviDhwFbEjRjfIBBkRyY (由 30 个大小写英文字母组成,不包含换行符),请问原字符串是多少? (如果你把以上字符串和表格复制到文本文件中,请务必检查复制的内容 是否与文档中的一致。在试题目录下有一个文件 str.txt,第一行为上面的字符 串,后面 52 行依次为表格中的内容。)

【答案提交】

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

【解题思路】

这个问题就比较简单了,就是简单的字符串转换,主要就是搞清楚字符的对应的关系。

#include<iostream>
#include<string>
using namespace std;
int main()
{
	//加密后字符串 
	string str="EaFnjISplhFviDhwFbEjRjfIBBkRyY";
	string s1="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
	string s2="yxmdacikntjhqlgoufszpwbrevYXMDACIKNTJHQLGOUFSZPWBREV";
	for(int i=0;i<str.size();i++){
		int index = s2.find(str[i]);
		cout << s1[index];
	}
	return 0;
}

【答案】

YeRikGSunlRzgDlvRwYkXkrGWWhXaA

# C:跑步训练(10分)

【问题描述】

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

【答案提交】

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

【解题思路】

这题以前也接触过类似的题,思路不难,将速度的单位化为秒,然后一秒钟的走或者休息,直到体力达到0停止。

#include<iostream>
using namespace std;
int main()
{
	int sum=0;
	int n=10000;
	while(n>0){
		int t1=60;
		while(t1--&&n>0){
			n -= 10;
			sum++;
		}
		int t2=60;
		while(t2--&&n>0){
			n += 5;
			sum++;
		}
	}
	cout << sum;
	return 0;
}

【答案】

3880

# D:合并检测(10分)

【问题描述】

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

【答案提交】

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

【解题思路】

这题实际上就是一道数学应用题,主要就是列出解题方程,题意说,A国有1%人感染,也就是说一个人患病的概率是1%,未患病的概率是99%,假如说说k=1时,那么必然消耗1个试剂盒,当k=2时,消耗(0.990.99)1+(0.990.01+0.010.99+0.01*0.01)*3,那么规律也就出来了,k个人全部未患病概率为0.99k,存在患病概率为(1-0.99k),设k个人需要消耗w个试剂盒,可以列出如下的方程,

w=0.99k+(1-0.99k)*(k+1)

那么当不使用此方案时,需要使用k个试剂盒,最省试剂盒也就是w和k值之比最小。

w/k = 1-0.99k+1/k

可是这个k该咋算呢?

当1-0.99k和1/k相等时取最小值。

拿计算器大约算出一个k=11,不知道对不对。

【答案】

11

# E:REPEAT程序(15分)

【问题描述】

附件 prog.txt 中是一个用某种语言写的程序。 下载地址 :附件 prog.txt (opens new window) 其中 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 的值是多少?

【答案提交】

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

【解题思路】

这题暂时还不知道如何做,类似yaml文件的语法,开始准备用word字符替换的,发现有点行不通,结束}不知道该如何替换。

貌似用栈可以解决这个问题,暂时放着。

【答案】

# F:分类计数(15分)

【问题描述】

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

【输入格式】

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

【输出格式】

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

【样例输入】

1+a=Aab

【样例输出】

131

【评测用例规模与约定】

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

【解题思路】

这题就是送分题了,只需要三个if就能解决了,判断出是否是大写字母,小写字母,数字,然后计数即可。

【答案】

#include<iostream>
#include<string>
using namespace std;
int main()
{
	string s;
	cin >> s;
	int length = s.size();
	int x=0,y=0,z=0;
	for(int i=0;i<length;i++){
		if('A'<=s[i]&&s[i]<='Z'){
			x++;
		}
		else if('a'<=s[i]&&s[i]<='z'){
			y++;
		}
		else if('0'<=s[i]&&s[i]<='9'){
			z++;
		}
	}
	cout << x << endl;
	cout << y << endl;
	cout << z;
	return 0;
}

# G:整除序列(20分)

【问题描述】

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

【输入格式】

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

【输出格式】

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

【样例输入】

20

【样例输出】

20 10 5 2 1

【评测用例规模与约定】

对于 80% 的评测用例,1 ≤ n ≤ 109。 对于所有评测用例,1 ≤ n ≤ 1018。

【解题思路】

这道题思路也不难,给出一个数,不断除2,迭代至答案n为0即可。

【答案】

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

# H:走方格(20分)

【问题描述】

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

【输入格式】

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

【输出格式】

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

【样例输入】

3 4

【样例输出】

2

【样例输入】

6 6

【样例输出】

0

【评测用例规模与约定】

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

【解题思路】

这题算是图论里面比较基础一道题,寻找路径的种树,可以用搜索来做,也可以用动态规划。和走台阶也类似,,每一个位置都有两种走法,向右走,向下走,除掉边界和不可到达的点。

建立一个二维数组,不使用0坐标,从1开始算边界,二维数组进行循环,当横纵坐标有一个为1,则说明是边界,设置为1,当横纵坐标是偶数时,说明,此点不可达,设为0,其余位置值为左位置和上位置值之和,解决了此问题。

【答案】

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

# I:字符串编码(25分)

【问题描述】

小明发明了一种给由全大写字母组成的字符串编码的方法。对于每一个大 写字母,小明将它转换成它在 26 个英文字母中序号,即 A → 1, B → 2, … Z → 26。 这样一个字符串就能被转化成一个数字序列: 比如 ABCXYZ → 123242526。 现在给定一个转换后的数字序列,小明想还原出原本的字符串。当然这样 的还原有可能存在多个符合条件的字符串。小明希望找出其中字典序最大的字 符串。

【输入格式】

一个数字序列。

【输出格式】

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

【样例输入】

123242526

【样例输出】

LCXYZ

【评测用例规模与约定】

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

【解题思路】

这道题求字典序最大,也就是说,每次还原字符都找字典序最大的字符例如123有三种情况ABC,LC,AW,它们三个字典序最大的就是LC,类似贪心。主要问题每次怎么选到字典序最大的字符。

【答案】

#include<iostream>
#include<string>
using namespace std;
int main()
{
	string s;
	cin >> s;
	int length = s.size();
	for(int i=0;i<length;i++){
		if((i+1)<length&&((s[i]-'0')*10+(s[i+1]-'0'))<=26){
			cout << (char)('A'+((s[i]-'0')*10+(s[i+1]-'0'))-1);
			i++;
		}
		else{
			cout << (char)('A'+(s[i]-'0')-1);
		}
	}
	return 0;
}

# J:整数小拼接(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

【样例输出】

8

【评测用例规模与约定】

对于 30% 的评测用例,1 ≤ N ≤ 1000, 1 ≤ K ≤ 108, 1 ≤ Ai ≤ 104。 对于所有评测用例,1 ≤ N ≤ 100000,1 ≤ K ≤ 1010,1 ≤ Ai ≤ 109。

【解题思路】

典型的排列问题,直接上八皇后的模板,事实上所有的排列问题,都能用它解决,只需要在排列好两个数的时候,进行拼接,比较大小,计数即可,唯一害怕的就是时间过不了。

【答案】

#include<iostream>
using namespace std;
int n,k,sum=0;
int a[5];
int b[100005];
bool isok(int r){
	for(int i=0;i<r;i++){
		if(a[i]==a[r]){
			return false;
		}
	}
	return true;
}
void dfs(int r){
	if(r==2){
		int w=1;
		while(b[a[1]]/w){
			w *= 10;
		}
		int cache = b[a[0]]*w+b[a[1]];
		if(cache<k){
			sum++;
		}
		return ;
	}
	for(int i=0;i<4;i++){
		a[r]=i;
		if(isok(r)){
			dfs(r+1);
		}
	}
}
int main()
{
	cin >> n >> k;
	for(int i=0;i<n;i++){
		cin >> b[i];
	}
	dfs(0);
	cout << sum;
	return 0;
}

# 参考链接

第十一届蓝桥杯省赛第一场原题 (opens new window)