第十一届蓝桥杯python大学A组国赛真题

第十一届蓝桥杯python大学组国赛

试题A:美丽的2.........................................................................................................1

试题B:合数个数.............................................1

试题C:阶乘约数.............................................2

试题D:本质上升序列.........................................3

试题E:畸蛇...............................................4

试题F:天干地支.............................................4

试题G:重复字符串...........................................5

试题H:答疑.................................................6

题I：补给....................................................8

试题J:蓝跳跳...............................................10

试题A:美丽的2

【问题描述】

小蓝特别喜欢2,今年是公元2020年，他特别高兴。

他很好奇，在公元1年到公元2020年(包含)中，有多少个年份的数位中包含数字2?

if_name_==1_main_'：

count=0

foriinrange(l,2021):

if'2'instr(i):

count+=1

print(count)

试题B：合数个数

【问题描述】

一个数如果除了1和自己还有其他约数，则称为一个合数。例如：1,2,3不是合数，4,6是合数。

请问从1到2020一共有多少个合数。

if_name_==1_main_

count=0

#temp=0

foriinrange(l,2O21):

temp=0

forjinrange(2,i//2+l)：

ifi%j==0:

count+=1

break

print(count)

试题c：阶乘约数

【问题描述】

定义阶乘n!=1X2X3X•••Xno

请问100!(100的阶乘)有多少个约数。

思路：惟一分解定理

在数惟一分解定理亦称算术基本定理，是数论的重要定理之一。该定理断言：任何一个大于1的整数n都可以分解成若干

个素因数的连乘积，如果不计各个素因数的顺序，那么这种分解是惟一的，即若n>1,则有

n=PlP2…Pm，(1)

其中PlSp25.SPm皆素数，上式常商记为

n=p»r…p『,⑵

其中，P/P2<…<除皆素数，皿1=1,2，…，k)皆正整数，(2)式称为n的标准分解式，又称为质因数分解式、素数暮分解式

等，若(2)式成立，贝M的任一正因数d都可表成

♦=—・.•孙,(3)

的形式，其中5邛2,k).利用标准分解式(可有素数零分解表)容易写出任二正整数的最大公因数.即若有

m=p;琮*…p?,n=pfi谤…琢*，其中3出Pj20(1=1,2,...»k),则(tn,n)=p?或…,这里产mln(0j,㈤

(i=1.2，…，k),把一个给定的充分大的期数分解成它的标准分解式，不仅具有理论意义，而且具有实际应用价值，但这是

一个十分困难的工作，即使借助于电子计算机也要花费惊人的时间，算术基本定理早在欧几里得(Euclid)的《几何原本》第9卷

命题20中已有陈述，1801年，高斯(C.F.Gauss)又重新提出，并给出证明⑴。

约数个数=(al+1)(a2+1)...(ak+1)

也就是说我们需要求出100!阶乘的所有质数；但是太大太多，一定是不好求的；所以我们改为求

每个因数的质数，然后记录数量就可以。

if_name_=='_main_':

die={}

sums二1

foriinrange(2,100):

pri=True

forjinrange(2,i//2+l):

ifi%j==0:

pri=False

break

ifpri:

dic[i]=1

foriinrange(2,101):

temp=i

forjindie.keys():

whiletemp%j==0:

temp//=j

dic[j]+=1

forvaluesindie.values():

sums*=values

print(sums)

#结果

39001250856960000

试题D:本质上升序列

【问题描述】

小蓝特别喜欢单调递增的事物。

在一个字符串中，如果取出若干个字符，将这些字符按照在字符串中的顺序排列后是单调递增的,

则成为这个字符串中的一个单调递增子序列。

例如，在字符串lanqiao中，如果取出字符n和q,则nq组成一个单调递增子序列。类似的单

调递增子序列还有Inq、i、ano等等。

小蓝发现，有些子序列虽然位置不同，但是字符序列是一样的，例如取第二个字符和最后一个字符

可以取到ao,取最后两个字符也可以取到ao。小蓝认为他们并没有本质不同。

对于一个字符串，小蓝想知道，本质不同的递增子序列有多少个？

例如，对于字符串lanqiao,本质不同的递增子序列有21个。它们分别是I、n、q、i、。、In、

an、lq、aq、nq、ai>lo>ao>no、io、Inq、anq、Ino、ano、aio。

请问对于以下字符串（共200个小写英文字母，分四行显示）：（如果你把以下文字复:制到文本

文件中，请务必检查复制的内容是否与文档中的一致。在试题目录下有一个文件inc.txt,内容与

下面的文本相同）

tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf

iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij

gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad

vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl

本质不同的递增子序列有多少个？

试题E:玩具蛇

【问题描述】

小蓝有一条玩具蛇，一共有16节，上面标着数字1至16。每一节都是一个正方形的形状。相邻

的两节可以成直线或者成90度角。

小蓝还有一个4x4的方格盒子，用于存放玩具蛇，盒子的方格上依次标着字母A到P共16个

字母。

小蓝可以折叠自己的玩具蛇放到盒子里面。他发现，有很多种方案可以将玩具蛇放进去。

下图给出了两种方案：

请帮小蓝计算一下，总共有多少种不同的方案。如果两个方案中，存在玩具蛇的某一节放在了盒子

的不同格子里，则认为是不同的方案。

试题F:天干地支

【问题描述】

古代中国使用天干地支来记录当前的年份。

天干一共有十个，分别为：甲(j话)、乙(yi)、丙(bing)、丁(ding)＞戊

(wu)s己(jT)、庚(geng)辛(xTn)、壬(0n)、癸(guT)。

地支一共有十二个，分别为：子(zi)、丑(chou).寅(yin).卯(mao).辰(ch6n).巳

(si)、午(wCi)、未(w6i)、申(shen)、酉(ybu)、戌(xU)、亥(h2i)。

将天干利地支连起来，就组成了一个天干地支的年份，例如：用子。2020年是庚子年。

每过一年，天干和地支都会移动到下一个。例如2021年是辛丑年。

每过60年，天干会循环6轮，地支会循环5轮,所以天干地支纪年每60年轮回一次。例如1900

年，1960年，2020年都是庚子年。

给定一个公元纪年的年份，请输出这一年的天干地支年份。

【输入格式】

输入一行包含一个正整数，表示公元年份。

【输出格式】

输出一个拼音，表示天干地支的年份，天干和地支都用小写拼音表示(不表示声调)，之间不要加

入任何多余的字符。

【样例输入】

2020

【样例输出】

gengzi

【评测用例规模与约定】

对于所有评测用例，输入的公元年份为不超过9999的正整数。

#2020年是庚子

#以2020,1960,1900任意一个为基准

if_name_=='_main_

t=[",,,"xin","ren","guiH,"jia",,yi","bingM,"dingM,"wu","ji'\"geng"]

d=["n,Hyou",,'xu","haiH,"zi1',nchou","yin","mao",Hchenn,"siM,"wu","wei","shen"]

a=10

b=4

year=int(input())

ifyear-2020>=0:

foriinrange(year-2020):

a=(a+1)%10

b=(b+1)%12

else:

foriinrange(2020-year):

a+=-1ifa>1elsea+8

print(a)

b+=-1ifb>1elseb+10

#print(b)

print(t[a]+d[b])

试题G:重复字符串

【问题描述】

如果一个字符串S恰好可以由某个字符串重复K次得到，我们就称S是K次重复字串。例如

<,abcabcabc^^可以看作是Mabc"重复3次得到，所以"abcabcabc”是3次重复字符串。

同理,'aaaaaaM既是2次重复字符串、又是3次重复字符串和6次重复字符串。

现在给定一个字符串S,请你计算最少要修改其中几个字符，可以使S变为一个K次字符串？

【输入格式】

输入第一行包含一个整数Ko

第二行包含一个只含小写字母的字符串So

【输出格式】

输出一个整数代表答案。如果S无法修改成K次重复字符串，输出1o

【样例输入】

2

aabbaa

【样例输出】

2

【评测用例规模与约定】

对于所有评测用例，1wK0100000,1<|S|<100000o其中|SI表示S的

长度。

试题H:答疑

【问题描述】

有n位同学同时找老师答疑。每位同学都预先估计了自己答疑的时间。

老师瓦以安排答疑的顺序，同学们要依次进入老师办公室答疑。

一位同学答疑的过程如下：

首先土入办公室，编号为i的同学需要si毫秒的时间。

然后同学问问题老师解答，编号为i的同学需要ai毫秒的时间。

答疑完成后，同学很高兴，会在课程群里面发一条消息，需要的时间可以忽略。

最后同学收拾东西离开办公室，需要ei毫秒的时间。一般需要10秒、

20秒或30秒，即ei取值为10000,20000或30000.

一位同学离开办公室后，紧接着下一位同学就可以进入办公室了。

答疑从0时刻开始。老师想合理的安排答疑的顺序，使得同学们在课程群

里面发消息的时刻之和最小

【输入格式】

输入第一行包含一个整数n,表示同学的数量。

接下来n行，描述每位同学的时间。其中第i行包含三个整数si,ai,ei,意

义如上所述。

【输出格式】

输出一个整数，表示同学们在课程群里面发消息的时刻之和最小是多少。

【样例输入】

3

100001000010000

200005000020000

300002000030000

【样例输出】

280000

【样例说明】

按照1,3,2的顺序答疑，发消息的时间分别是20000,80000,180000o

【评测用例规模与约定】

对于30%的评测用例，1Vn£20。

对于60%的评测用例,1rnM200o

对于所有评测用例，11000,10sis60000,1<ai<1000000,eie{10000,20000,30000},

即ei一定是10000、20000、30000之一。

#思路：啥啥啥，我都不明白这个题为什么会出在H序号上？原本以为上一个同学发消息，下一个

同学就可以走了同时上一个同学也在走出教室。

结果：给的示例意思是：

首先按照132的顺序答疑进行排序

al,a2,a3表示第一位同学的siaiei,以此类推

3

a2a3

100001000010000

blb2b3

300002000030000

clc2c3

200005000020000

si表示第一位同学的发消息的时间，以此类推

si=al+a2

s2=bl+b2+(al+a2+a3)

s3=cl+c2+(al+a2+a3)+(bl+b2+b3)

if_name_=='_main—':

sums=0

temp-0

count=int(inputO)

re=[]

1st=[list(map(int,inputO.split()))foriinrange(count)]

foriinrange(count):

re.append([1st[i][O]+lst[i][1],lst[i][2]])

rc.sort()

print(re)

foriinrange(count):

ifi==0:

temp+=re[i][0]

sums+=temp

else:

temp+=re[i][0]+re[i-l][1]

sums+二temp

print(sums)

题I：补给

【问题描述】

小蓝是一个直升飞机驾驶员，他负责给山区的n个村庄运送物资。每个月，他都要到每个村庄至

少一次，可以多于一次，将村庄需要的物资运送过去。每个村庄都正好有一个直升机场，每茂个村

庄之间的路程都正好是村庄之间的直线距离。

由于直升机的油箱大小有限，小蓝单次飞行的距离不能超过Do每个直升机场都有加油站，可以

给直升机加满油。每个月，小蓝都是从总部出发，给各个村庄运送完物资后回到总部。如果方便，

小蓝中途也可以经过总部来加油。

总部位于编号为1的村庄。请问，要完成一个月的任务，小蓝至少要飞行多长距离？

【输入格式】

输入的第一行包含两个整数n.。，分别表示村庄的数量和单次飞行的距离。

接下来〃行描述村庄的位置，其中第i行两个能数.%力，表示编号为i的

村庄的坐标。村庄i和村庄j之间的距离为，«-勺）2+9一口）2。|

【输出格式】

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

【输出格式】

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

【样例输入】

410

11

55

15

51

【样例输出】

16.00

【样例说明】

四个村庄形成一个正方形的形状。

【样例输入】

46

11

45

85

111

【样例输出】

28.00

【样例说明】

补给顺序为1T2T31413T2-1。

【评测用例规模与约定】

对于所有评测用例，1$n&20,1&xi,yi