2022年第十三届蓝桥杯python组国赛

2022年第十三届蓝桥杯python组国赛

填空题

斐波那契与7

小蓝做实验

编程题

取模

内存空间

近似GCD

交通信号

点亮

打折

0W0

替换字符

斐波那契与7

试题A:斐波那契与7

本题总分：5分

【问题描述】

斐波那契数列的递推公式为：F“=EI+F“_2，其中和=-2=1。

请问,斐波那契数列的第1至202202011200项（含）中，有多少项的个位

是7。

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一

个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

CSDH

一开始看到这么多项就知道肯定是不能硬跑的，哪怕只取末尾运算也难以得到结果。

然后就针对末尾项找规律。因为dp[n]的结果只与前两项有关，只要前两项的末位数

的顺序之前出现过，那么这个区间就是重复区间。然后找到每隔60项为一周期，这

里面有8个7

代码：

dp=[lfor_inrange(3)]

chucun=[[l,l]]

res=0

foriinrange(70):

dp[2]=dp[l]+dp[0]

#这里的项数实质从3开始

print(i,dp[2])

s=str(dp[2])

ifs[-l]=='7':

res+=1

s2,s3,s4=str(dp[2]),str(dp[l]),str(dp[0])

if[s4,s3]inchucun:

print(s4,s3)

break

else:

chucun.append([s4,s3])

#print(s4,s3)

#只取尾数,方便计算

dp[l]Jdp[0]=int(s2[-l])Jint(s3[-l])

print(res)

小蓝做实验

试题B:小蓝做实验

本题总分：5分

【问题描述】

小板很N欢科研，他最近做了一个实验得到r一批实验数据，一共是两百

万个正整数。如果按照预期，所仃的实验数据大都应该满足1070X5108。但

是做实验都会仃•些误差，会导致出现•些预期外的数据•，这种误差数据y的

范围是HP<y<10】2。山广小监做实验很可靠，所以他所仃的实验数据中

99.99%以上都是符介预期的。小蓝的所有实验数据都在primes.txt中，现

在他想统计这两门.万个正整数中仃多少个是质数，你能告诉他吗？

【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一

个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。o

思路：

1.观察所有数据可以发现，位数都是1,3,5,7,9o位数为5的数字全部去掉，可

以删去四分之一的数据

2.采用6的余数法，原理就不阐述了，结论是一个质数除余6,结果必然为1或者5

3.在2的基础上，遍历时可以再做两点优化，遍历最大值为根号下该数字，和步长为

2,跳过所有偶数

代码：

defzhishu(num):

ifnum%6!=landnum%6!=5:

returnFalse

foriinrange(3,int(num**0.5)+l,2):

ifnum%i==0:

returnFalse

returnTrue

nums=[]

res=0

withopen('primes.txt')asfp:

试题c：取模

时间限制：10.0s内存限制：512.0VB本题总分：10分

【问题描述】

给定n,m，问是否存在两个不同的数使得10xvy,m且〃modx=

nmody。

【输入格式】

输入包含多组独立的询问。

第一行包含一个整数丁表示询问的组数.

接下来7行每行包含两个整数〃,，〃，用一个空格分隔，表示一组询问。

【输出格式】

输出了行，每行依次对应组询问的结果。如果存在，输出单词SS；如

果不存在，输出单词N。.

【样例输入】

3

12

52

99999

【样例输出】

YesCSDM@Ruoki-

代码：

num=int(input())

foriinrange(num):

n,m=map(int,input().split())

key=l

forxinrange(l,m):

foryinrange(x+l,m+l):

ifn%x==n%y:

print('Yes')

key=0

break

ifkey==0:

break

ifkey==l:

print('No')

内存空间

题目：

小蓝最近总喜欢计算自己的代码中定义的变量占用了多少内存空间。

为了简化问题，变量的类型只有以下三种：

int：整型变量，一个ini型变量占用4Byte的内存空间。

long：长整型变量，一个long型变量占用8Byte的内存空间。

String：字符串变曷，占用空间和字符串长度有关，设字符串长度为L,

则字符串占用LByte的内存空间，如果字符串长度为0则占用0Byte的内存

空间。

定义变量的语句只有两种形式，第一种形式为：

typevarl=valuel,var2=va：ue2…；

定义了若干个type类型变量varl、var2、…，并且用valuel、value2

…初始化，

多个变量之间用'分隔，语句以‘；'结尾，type可能是int、long或

Stringo例如ima=l,b=5,c=6;占用空间为12Byte；longa=l,b=5;

占用空间为16Byte：Stringsl="“，s2="hello"，s3="world";占用空

间为10Byteo

第二种形式为：

type[]arrl=newtypefsizel],arr2=newtype[size2];

定义了若干type类型的一维数组变量arrl、arr2-,且数组的大小为

sizel>size2-,多个变量之间用'，'进行分隔，语句以‘；'结尾，type只可

能是int或long。例如int口al=newint[10];占用的内存空间为40Byte；

long[]al=newlong[10],a2=newlong[10];占用的内存空间为

160Byte(>

已知小蓝有T条定义变量的语句，请你帮他统计下一共占用了多少内

存空间。结果的表示方式为：aGBbYBcKBdB,其中a、b、c、d为统计的

结果,GB、MB、KB、B为单位。优先用大的单位来表示，1GB=1O24MB,

1MB=1O24KB,1KB=1O24B,其中B表示Byle。如果a、b、c、d中的某几个

数字为0,那么不必输出这几个数字及其单位。题目保证一行中只有一句定义

变量的语句，且每条语句都满足题干中描述的定义格式，所有的变量名都是合

法的且均不重复。题目中的数据很规整，和上述给出的例子类似，除了类型后

面有一个空格，以及定义数组时new后面的一个空格之外，不会出现多余的空

格。

【输入格式】

输入的第一行包含一个整数T,表示有T句变量定义的语句。

接下来T行，每行包含一句变量定义语句。

【输出格式】

输出一行包含一个字符串，表示所有语句所占用空间的总大小。

【样例输入1】

1

long[]nums=newlong[131072];

【样例输出1]

1MB

【样例输入2】

4

inta—0,b—0;

longx=0,y=0;

Stringsl="hello“，s2="world”；

long[]arr1=new1ong[100000],arr2=newlong[100000";

【样例输出2】

1MB538KB546B

近似GCD

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

题目:

小蓝有一个长度为n的数组A=(al;a2;;an),数组的子数组被定义为从

原数组中选出连续的一个或多个元素组成的数组。数组的最大公约数指的是数

组中所有元素的最大公约数。如果最多更改数组中的一个元素之后，数组的最

大公约数为g,那么称g为这个数组的近似GCD。一个数组的近似GCD可能

有多种取值。

具体的，判断g是否为一个子数组的近似GCD如下：

1.如果这个子数组的最大公约数就是g,那么说明g是其近似GCD。

2.在修改这个子数组中的一个元素之后(可以改成想要的任何值)，子数

组的最大公约数为g,那么说明g是这个子数组的近似GCD。

小蓝想知道，数组A有多少个长度大于等于2的子数组满足近似GCD的

值为g。

输入格式：

输入的第一行包含两个整数n；g,用一个空格分隔，分别表示数组A的长

度和g的值。

第二行包含n个整数al;a2;...;an,相邻两个整数之间用一个空格分隔。

输出格式：

输出一行包含一个整数表示数组A有多少个长度大于等于2的子数组的近

似GCD的值为go

样例输入：

53

136410

样例输出：

5

思路：

暴力吧，想了很久想不到更好的

最大公约数可以记住这个代码格式，比遍历快很多

代码：

defgongyue(x,y):

a,b=x,y

whileb:

a,b=b,a/b

returna

n,g=map(int,input().split())

nums=list(map(int,input().split()))

res=0

i=0

whilei<len(nums)-l:

j=i+l

key=l

ifnums[i]<gandnums[j]<g:

continue

ifgongyue(nums[i],nums[j])==g:

z=j+l

##nums[zJ建g的倍数

whilez<len(nums)andnums[z]%g==0:

z+=1

res+=z-i

i+=1

else:

ifnums[i]%g==0ornums[j]%g==0:

z=i+2

whilez<len(nums)andnums[z]%g==0:

z+=1

z-=1

res+=z-i

i+=1

else:

i+=1

print(res)

交通信号

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

题目：

LQ市的交通系统可以看成由n个结点和m条有向边组成的有向图。在每

条边上有一个信号灯，会不断按绿黄红黄绿黄红黄...的顺序循环(初始时刚好

变到绿灯)。当信号灯为绿灯时允许正向通行，红灯时允许反向通行，黄灯时不

允许通行。每条边上的信号灯的三种颜色的持续时长都互相独立，其中黄灯的

持续时长等同于走完路径的耗时。当走到一条边上时，需要观察边上的信号灯,

如果允许通行则可以通过此边，在通行过程中不再受信号灯的影响；否则需要

等待，直到允许通行。

请问从结点S到结点t所需的最短时间是多少，如果S无法到达t则输出

-1。

输入格式：

输入的第一行包含四个整数s;t,相邻两个整数之间用一个空格分隔。

接下来m行，每行包含五个整数ui;vi;gi;ri;di,相邻两个整数之间用一个

空格分隔，分别表示一条边的起点，终点，绿灯、红灯的持续时长和距离（黄

灯的持续时长）.

输出格式：

输出一行包含一个整数表示从结点s到达t所需的最短时间。

样例输入：

4414

12126

42115

13111

341991

样例输出：

11

点灵

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

题目：

小蓝最近迷上了一款名为《点亮》的谜题游戏，游戏在一个nn的格子棋

盘上进行，棋楹由黑色和白色两种格子组成，玩家在白色格子上放置灯泡，确

保任意两个灯泡不会相互照射，直到整个棋盘上的白色格子都被点亮（每个谜

题均为唯一解）。灯泡只会往水平和垂直方向发射光线，照亮整行和整列，除非

它的光线被黑色格子挡住。黑色格子上可能有从0到4的整数数字，表示与其

上下左右四个相邻的白色格子共有几个灯泡：也可能没有数字，这表示可以在

上下左右四个相邻的白色格子处任意选择几个位置放置灯泡。游戏的目标是选

择合适的位置放置灯泡，使得整个棋盘上的白色格子都被照亮。

例如，有一个黑色格子处数字为4,这表示它周围必须有4个灯泡，需要

在他的上、下、左、右处分别放置一个灯泡；如果一个黑色格子处数字为2,它

的上下左右相邻格子只有3个格子是白色格子，那么需要从这三个白色格子中

选择两个来放置灯泡；如果一个黑色格子没有标记数字，且其上下左右相邻格

子全是白色格子，那么可以从这4个白色格子中任选出0至4个来放置灯泡。

题目保证给出的数据是合法的，黑色格子周围一定有位置可以放下对应数

量的灯泡。且保证所有谜题的解都是唯一的。

现在，给出一个初始的棋盘局面，请在上面放置好灯泡，使得整个棋盘上

的白色格子被点亮。

输入格式：

输入的第一行包含一个整数n,表示棋盘的大小。

接下来n行，每行包含n个字符，表示给定的棋盘。字符.表示对应的格

子为白色，数字字符0、1、2、3、4表示一个有数字标识的黑色格子，大写字

母X表示没有数字标识的黑色格子。

输出格式：

输出n行，每行包含n个字符，表示答案。大写字母0表示对应的格子包

含灯泡，其它字符的意义与输入相同。

样例输入：

5

2.4

.4.

2.X

样例输出：

...0.

.2040

.040.

.20X.

0....

打折

【问题描述】

小蓝打算采购〃种物品，每种物拈各需要1个。

小蚯所住的位置附近一共有，〃个店铺，每个店铺都出售着各种各样的物

iWlo

第，・家店铺会在第s,天至第ti天打折，折扣率为Pi，对于原件为b的物

品，折后价格为［繇J。其它时间需按原价购买。

小蓝很忙，他只能选择一天的时间去采购这些物品。请问，他最少需要花

多少钱才能买到需要的所有物品。

题目保证小蓝一定能买到需要的所有物乩。C-R

输入格式：

输入的第一行包含两个整数n;m,用一个空格分隔，分别表示物品的个数

和店铺的个数。

接下来依次包含每个店铺的描述。每个店铺由若干行组成，其中第一行包

含四个整数si;ti;pi;ci,相邻两个整数之间用一个空格分隔，分别表示商店优

惠

的起始和结束时间、折扣率以及商店内的商品总数。之后接ci行，每行包含两

个整数aj;bj,用一个空格分隔，分别表示该商店的第j个商品的类型和价格。

商品的类型由1至n编号。

输出格式：

输出一行包含一个整数表示小蓝需要花费的最少的钱数。

样例输入：

22

12891

197

34771

215

样例输出：

101

owo

小蓝很喜欢。W。,他现在有一些字符串，他想将这些字符串拼接起

来，使

得最终得到的字符串中出现尽可能多的。woO

在计算数量时，允许字符重叠，即OWOWO计算为2个，OWOWOWO计

算为

3个。

请算出最优情况下得到的字符串中有多少个OW。。

输入格式：

输入的第i行包含一个整数n,表示小蓝拥有的字符串的数量。

接下来n行，每行包含一个由小写英文字母组成的字符串si。

输出格式：

输出n行，每行包含一个整数，表示前i个字符串在最优拼接方案中可以

得到的owo的数量。

样例输入：

3

OWO

W

OW

样例输出：

1

1

2

思路：

这题感