[数据结构与算法]2020年第十届蓝桥杯省级考试题目

目录

蓝桥杯2020年第十一届省赛真题-成绩分析

蓝桥杯2020年第十一届省赛真题-回文日期

题目描述

蓝桥杯2020年第十一届省赛真题-荒岛探测

题目描述

蓝桥杯2020年第十一届省赛真题-字串排序

题目描述

蓝桥杯2020年第十一届省赛真题-单词分析

题目描述

蓝桥杯2020年第十一届省赛真题-数字三角形

题目描述

????????蓝桥杯2020年第十一届省赛真题-子串分值和

题目描述

蓝桥杯2020年第十一届省赛真题-装饰珠

题目描述

蓝桥杯2020年第十一届省赛真题-平面切分

题目描述?

蓝桥杯2020年第十一届省赛真题-作物杂交

题目描述

蓝桥杯2020年第十一届省赛真题-成绩统计

题目描述

蓝桥杯2020年第十一届省赛真题-成绩分析

题目描述

小蓝给学生们组织了一场考试，卷面总分为100 分，每个学生的得分都是一个0 到100 的整数。请计算这次考试的最高分、最低分和平均分。

输入

输入的第一行包含一个整数n，表示考试人数。

接下来n 行，每行包含一个0 至100 的整数，表示一个学生的得分。

输出

输出三行。

第一行包含一个整数，表示最高分。

第二行包含一个整数，表示最低分。

第三行包含一个实数，四舍五入保留正好两位小数，表示平均分。

样例输入复制

7

80

92

56

74

88

99

10

样例输出复制

99

10

71.29

提示

对于50% 的评测用例， 1 ≤ n ≤ 100。

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

n = int(input())

l = []

s = 0

for i in range(n):

a = int(input())

l.append(a)

s = a + s

s = s/n

print(max(l))

print(min(l))

print('{:.2f}'.format(s))

蓝桥杯2020年第十一届省赛真题-回文日期

题目描述

2020 年春节期间，有一个特殊的日期引起了大家的注意：2020年2月2日。因为如果将这个日期按“yyyymmdd” 的格式写成一个8 位数是20200202，

恰好是一个回文数。我们称这样的日期是回文日期。

有人表示20200202 是“千年一遇” 的特殊日子。对此小明很不认同，因为不到2年之后就是下一个回文日期：20211202 即2021年12月2日。

也有人表示20200202 并不仅仅是一个回文日期，还是一个ABABBABA型的回文日期。对此小明也不认同，因为大约100 年后就能遇到下一个ABABBABA 型的回文日期：21211212 即2121 年12 月12 日。算不上“千年一遇”，顶多算“千年两遇”。

给定一个8 位数的日期，请你计算该日期之后下一个回文日期和下一个ABABBABA型的回文日期各是哪一天。

输入

输入包含一个八位整数N，表示日期。

输出

输出两行，每行1 个八位数。第一行表示下一个回文日期，第二行表示下

一个ABABBABA 型的回文日期。

样例输入复制

20200202

样例输出复制

20211202

21211212

提示

对于所有评测用例，10000101 ≤ N ≤ 89991231，保证N 是一个合法日期的8位数表示。

、

题目描述

对于一个字符串S，我们定义S 的分值 f(S) 为S中恰好出现一次的字符个数。例如f (”aba”) = 1，f (”abc”) = 3, f (”aaa”) = 0。

现在给定一个字符串S[0…n-1]（长度为n），请你计算对于所有S的非空子串S[i…j](0 ≤ i ≤ j < n)， f (S[i… j]) 的和是多少。

输入

输入一行包含一个由小写字母组成的字符串S。

输出

输出一个整数表示答案。

样例输入复制

ababc

样例输出复制

21

提示

样例说明：

子串f值：

a ? ? 1

ab ? ?2

aba ? 1

abab ?0

ababc 1

?b ? ?1

?ba ? 2

?bab ?1

?babc 2

? a ? 1

? ab ?2

? abc 3

? ?b ?1

? ?bc 2

? ? c 1

蓝桥杯2020年第十一届省赛真题-荒岛探测

题目描述

科学家小蓝来到了一个荒岛，准备对这个荒岛进行探测考察。小蓝使用了一个超声定位设备来对自己进行定位。为了使用这个设备，小蓝需要在不同的点分别安装一个固定的发射器和一个固定的接收器。小蓝手中还有一个移动设备。定位设备需要从发射器发射一个信号到移动设备，移动设备收到后马上转发，最后由接收器接收，根据这些设备之间传递的时间差就能计算出移动设备距离发射器和接收器的两个距离，从而实现定位。

小蓝在两个位置已经安装了发射器和接收器，其中发射器安装在坐标 ( xA , yA ) (xA, yA) (xA,yA)，接收器安装在坐标 (xB?, yB ) (xB, yB) (xB?,yB)。小蓝的发射器和接收器可能在岛上，也可能不在岛上。小蓝的定位设备设计有些缺陷，当发射器到移动设备的距离加上移动设备到接收器的距离之和大于L 时，定位设备工作不正常。当和小于等于L 时，定位设备工作正常。为了安全，小蓝只在定位设备工作正常的区域探测考察。

已知荒岛是一个三角形，三个顶点的坐标分别为 ( x1 , y1 ) (x1, y1) (x1,y1), ( x2 , y2 ) (x2, y2) (x2,y2), (x3, y3 ) (x3, y3) (x3,y3)。请计算，小蓝在荒岛上可以探测到的面积有多大？

输入

输入的第一行包含五个整数，分别为xA、yA、xB、xB、L

第二行包含六个整数，分别为x1、y1、x2 、y2、 x3、 y3

输出

输出一行，包含一个实数，四舍五入保留2位小数，表示答案。

考虑到计算中的误差，只要你的输出与参考输出相差不超过0.01即可得分。

样例输入复制

10 6 4 12 12

0 2 13 2 13 15

样例输出复制

39.99

提示

荒岛的形状和定位设备工作正常的区域如下图所示，蓝色的三角形表示荒岛，红色的曲线围成的区域为定位设备工作正常的区域。

当输出为39.98、39.99或 40.00时可以得分。

对于所有评测用例，保证发射器的两个坐标不同，-1000<=xA,yA,xB,yB<=1000,-1000<=x1,y1,x2,y2,x3,y3<=1000,-1000<=L<=1000

蓝桥杯2020年第十一届省赛真题-字串排序

题目描述

小蓝最近学习了一些排序算法，其中冒泡排序让他印象深刻。在冒泡排序中，每次只能交换相邻的两个元素。小蓝发现，如果对一个字符串中的字符排序，只允许交换相邻的两个字符，则在所有可能的排序方案中，冒泡排序的总交换次数是最少的。

例如，对于字符串 lan 排序，只需要 1 次交换。对于字符串 qiao 排序，

总共需要 4 次交换。小蓝找到了很多字符串试图排序，他恰巧碰到一个字符串，需要 V 次交换，可是他忘了把这个字符串记下来，现在找不到了。

请帮助小蓝找一个只包含小写英文字母且没有字母重复出现的字符串，对该串的字符排序，正好需要 V 次交换。如果可能找到多个，请告诉小蓝最短的那个。如果最短的仍然有多个，请告诉小蓝字典序最小的那个。请注意字符串中可以包含相同的字符。

输入

输入的第一行包含一个整数V，小蓝的幸运数字。

输出

题面要求的一行字符串。

样例输入复制

4

样例输出复制

bbaa

蓝桥杯2020年第十一届省赛真题-单词分析

题目描述

小蓝正在学习一门神奇的语言，这门语言中的单词都是由小写英文字母组成，有些单词很长，远远超过正常英文单词的长度。小蓝学了很长时间也记不住一些单词，他准备不再完全记忆这些单词，而是根据单词中哪个字母出现得最多来分辨单词。

现在，请你帮助小蓝，给了一个单词后，帮助他找到出现最多的字母和这个字母出现的次数。

输入

输入一行包含一个单词，单词只由小写英文字母组成。

输出

输出两行，第一行包含一个英文字母，表示单词中出现得最多的字母是哪个。如果有多个字母出现的次数相等，输出字典序最小的那个。

第二行包含一个整数，表示出现得最多的那个字母在单词中出现的次数。

样例输入复制

lanqiao

样例输出复制

a

2

提示

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

蓝桥杯2020年第十一届省赛真题-数字三角形

题目描述

上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。

路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。

输入

输入的第一行包含一个整数N(1<N≤100)，表示三角形的行数。下面的 N行给出数字三角形。数字三角形上的数都是 0至 100之间的整数。

输出

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

样例输入复制

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

样例输出复制

27

蓝桥杯2020年第十一届省赛真题-子串分值和

题目描述

对于一个字符串S，我们定义S 的分值 f(S) 为S中恰好出现一次的字符个数。例如f (”aba”) = 2，f (”abc”) = 3, f (”aaa”) = 1。

现在给定一个字符串S[0…n-1]（长度为n），请你计算对于所有S的非空子串S[i…j](0 ≤ i ≤ j < n)， f (S[i… j]) 的和是多少。

输入

输入一行包含一个由小写字母组成的字符串 S。

输出

输出一个整数表示答案。

样例输入复制

ababc

样例输出复制

28

提示

样例说明：

子串f值：

a ? ? 1

ab ? ?2

aba ? 1

abab ?0

ababc 1

?b ? ?1

?ba ? 2

?bab ?1

?babc 2

? a ? 1

? ab ?2

? abc 3

? ?b ?1

? ?bc 2

? ? c 1

蓝桥杯2020年第十一届省赛真题-装饰珠

题目描述

在怪物猎人这一款游戏中，玩家可以通过给装备镶嵌不同的装饰珠来获取相应的技能，以提升自己的战斗能力。

已知猎人身上一共有 6件装备，每件装备可能有若干个装饰孔，每个装饰孔有各自的等级，可以镶嵌一颗小于等于自身等级的装饰珠(也可以选择不镶嵌)。装饰珠有M种，编号1至M，分别对应M种技能，第i种装饰珠的等级为 Li，只能镶嵌在等级大于等于 Li的装饰孔中。

对第 i种技能来说，当装备相应技能的装饰珠数量达到 Ki个时，会产生 Wi(Ki)

?的价值。镶嵌同类技能的数量越多，产生的价值越大，即 Wi(Ki?1)<Wi(Ki)。但每个技能都有上限 Pi(1≤Pi≤7)，当装备的珠子数量超过 Pi时，只会产生 Wi(Pi)的价值。

对于给定的装备和装饰珠数据，求解如何镶嵌装饰珠，使得 6件装备能得到的总价值达到最大。

输入

输入的第1至6行，包含6件装备的描述。其中第i的第一个整数Ni表示第i件装备的装饰孔数量。后面紧接着Ni个整数，分别表示该装备上每个装饰孔的等级 L(1≤L≤4)。第7行包含一个正整数M，表示装饰珠(技能)种类数量。第8至 M+7行，每行描述一种装饰珠(技能)的情况。每行的前两个整数 Lj(1≤Lj≤4)和 Pj(1≤Pj≤7)分别表示第j种装饰珠的等级和上限。接下来 Pj个整数，其中第 k个数表示装备该中装饰珠数量为 k时的价值 Wj(k)。

输出

输出一行包含一个整数，表示能够得到的最大价值。

样例输入复制

1 1

2 1 2

1 1

2 2 2

1 1

1 3

3

1 5 1 2 3 5 8

2 4 2 4 8 15

3 2 5 10

样例输出复制

20

提示

样例说明：

按照如下方式镶嵌珠子得到最大价值 20，括号内表示镶嵌的装饰珠的种类编号：

1: (1)

2: (1) (2)

3: (1)

4: (2) (2)

5: (1)

6: (2)

4颗技能 1装饰珠，4颗技能2装饰珠 W1(4)+W2(4)=5+15=20。

蓝桥杯2020年第十一届省赛真题-平面切分

题目描述?

平面上有N条直线，其中第 i 条直线是y=Ai?x+Bi。请计算这些直线将平面分成了几个部分。

输入

第一行包含一个整数 N。以下N行，每行包含两个整数 Ai,Bi。

输出

一个整数代表答案。

样例输入复制

3

1 1

2 2

3 3

样例输出复制

6

提示

对于50的评测用例，1≤N≤4, ?10≤Ai,Bi≤10。对于所有评测用例，1≤N≤1000, ?100000≤Ai,Bi≤100000。

蓝桥杯2020年第十一届省赛真题-作物杂交

题目描述

作物杂交是作物栽培中重要的一步。已知有N种作物(编号1至N)，第i种作物从播种到成熟的时间为Ti。作物之间两两可以进行杂交，杂交时间取两种中时间较长的一方。

如作物A种植时间为5天，作物B种植时间为7天，则AB杂交花费的时间为7天。作物杂交会产生固定的作物，新产生的作物仍然属于N种作物中的一种。

初始时，拥有其中 M种作物的种子(数量无限，可以支持多次杂交)。同时可以进行多个杂交过程。

求问对于给定的目标种子，最少需要多少天能够得到。

如存在4种作物 ABCD，各自的成熟时间为5天、7天、3天、8天。初始拥有AB两种作物的种子，目标种子为D，已知杂交情况为A×B→C，A×C→D。

则最短的杂交过程为：

第1天到第 7天(作物B的时间)，A×B→C。

第8天到第12天(作物 A的时间)，A×C→D。花费12天得到作物D的种子。

输入

输入的第 1行包含4个整数N,M,K,T，N表示作物种类总数(编号 1至 N)，M表示初始拥有的作物种子类型数量，K表示可以杂交的方案数，T表示目标种子的编号。第2行包含N个整数，其中第i个整数表示第i种作物的种植时间 Ti(1≤Ti≤100)。第3行包含 M个整数，分别表示已拥有的种子类型 Kj(1≤Kj≤M)，Kj两两不同。第4至K+3行，每行包含3个整数A,B,C，表示第 A类作物和第B类作物杂交可以获得第C类作物的种子。

输出

输出一个整数，表示得到目标种子的最短杂交时间。

样例输入复制

6 2 4 6

5 3 4 6 4 9

1 2

1 2 3

1 3 4

2 3 5

4 5 6

样例输出复制

16

提示

样例说明：

第 1天至第5天，将编号1与编号2的作物杂交，得到编号3的作物种子。第6天至第10天，将编号1与编号3的作物杂交，得到编号4的作物种子。第6天至第9天，将编号2与编号3的作物杂交，得到编号5的作物种子。第11天至第16天，将编号4与编号5的作物杂交，得到编号6的作物种子。总共花费16天。

评测用例规模与约定

对于所有评测用例，1≤N≤2000, 2≤M≤N, 1≤K≤100000, 1≤T≤N, 保证目标种子一定可以通过杂交得到。

蓝桥杯2020年第十一届省赛真题-成绩统计

题目描述

小蓝给学生们组织了一场考试，卷面总分为100分，每个学生的得分都是一个0到100的整数。如果得分至少是?60分，则称为及格。如果得分至少为85分，则称为优秀。

请计算及格率和优秀率，用百分数表示，百分号前的部分四舍五入保留整数。

输入

输入的第一行包含一个整数n，表示考试人数。接下来 n行，每行包含一个 0至 100的整数，表示一个学生的得分。

输出

输出两行，每行一个百分数，分别表示及格率和优秀率。百分号前的部分四舍五入保留整数。

样例输入复制

7

80

92

56

74

88

100

0

样例输出复制

71%

43%