第十五届蓝桥杯PythonB组省赛

瑆琉

这届比赛的题目数量总共有八道，比之前少了两道，而且Python组题目的难度比去年下降了不少，同时也是所有组里面难度最低的。不知道是不是为了照顾参赛的选手水平。去年Python组的题太难了，我到现在还有好几道不会的题🫢😥。A：穿越时空之门考察：字符串、枚举解题思路从1枚举到2024，遇到符合条件的数就计数器加一，最后输出计数器即可。代码ans=0defcheck(x):#判断是否符合条件s1,s2=sum(int(i)foriinbin(x)[2:]),0whilex:s2+=x%4x//=4returns1==s2foriinrange(1,2025):ans+=check(i)print(ans)#63'运行运行最后答案为：63B：数字串个数考察：容斥原理、快速幂取余解题思路根据条件一：该数字串只能由数字1~9组成。根据条件二：要减去不包含数字3或7的。用容斥原理做，集合总大小为：9^10000，减去两个8^10000，由于多减了一个两个都不含的，再加上一个7^10000。快速幂取模可以用Python的内置函数pow实现。代码mod=10**9+7#157509472print((pow(9,10000,mod)-2*pow(8,10000,mod)+pow(7,10000,mod))%mod)'运行运行最后答案为：157509472C：连连看考察：枚举解题思路由于要寻找横纵坐标差的绝对值相同的格子对的数量，所以有左上、右上、左下、右下四个方向。但是在顺序枚举的过程只需要找两个方向就够了，要不然枚举到后面格子的时候会产生重复判断。代码n,m=map(int,input().split())a=[list(map(int,input().split()))for_inrange(n)]ans=0foriinrange(1,n):#枚举左上方向forjinrange(1,m):forkinrange(1,min(i,j)+1):ifa[i][j]==a[i-k][j-k]:ans+=2foriinrange(n-1):#枚举左下方向forjinrange(1,m):forkinrange(1,min(n-i,j+1)):ifa[i][j]==a[i+k][j-k]:ans+=2print(ans)测试样例样例一输入：32122332输出：6'运行运行样例二输入：33323232323输出：20'运行运行D：神奇闹钟考察：时间处理解题思路可以使用Python标准库中的datetime模块来解决此题。本题中的输入是标准的iso格式日期时间，所以可以直接解析为datetime对象。计算上一次响的时间：用总的分钟数减去对时间间隔求余的余数得到上次响的分钟数，再加上起始时间，转化为datetime对象，最后输出即可。代码fromdatetimeimport*bg=datetime.fromisoformat('1970-01-0100:00:00')for_inrange(cin(0)):date,time,dif=input().split()dt=datetime.fromisoformat(date+''+time)nows=int((dt-bg).total_seconds())//60#分钟数nows-=nows%int(dif)print(bg+timedelta(minutes=nows))测试样例样例一输入：22016-09-0718:24:33102037-01-0501:40:4330输出：2016-09-0718:20:002037-01-0501:30:00E：蓝桥村的真相考察：分类讨论、找规律解题思路分别讨论一个村民的断言为假话、真话和后面的村民的断言为假话、真话的情况。再往后的村民的断言真假都可以通过前面的断言真假推断出来。 再往后就是之前的重复了。注意上面前三个分支需要村民个数为3的倍数才行，这时“假”的个数为2n；如果不为3的倍数，则只有最后一个情况符合条件，这时“假”的个数为n。代码for_inrange(cin(0)):n=int(input())print(n*(1+(n%3==0)))F：魔法巡游考察：哈希表、DP解题思路用一个哈希表统计上一个包含'0'、'2'、'4'的符石作为序列末尾的最长序列长度。最后输出序列最大值即可。代码cin=lambda:list(map(int,input().split()))n,s,t=int(input()),cin(),cin()dig1,dig2=defaultdict(int),defaultdict(int)digs=('0','2','4')foriinrange(n):num1,num2=str(s[i]),str(t[i])d1,d2=dict(dig1.items()),dict(dig2.items())fordindigs:ifdinnum2anddind1:dig2[d]=max(dig2[d],d1[d]+1)fordindigs:ifdinnum1:ifdind2:dig1[d]=max(dig1[d],d2[d]+1)else:dig1[d]=1print(max(max(dig1[d],dig2[d])fordindigs))测试样例样例一输入：512639358142442049902404652输出：4'运行运行样例二输入：5222222222222222222222222222222输出：5'运行运行G：缴纳过路费考察：缩点、并查集、DFS解题思路分析：由于要满足路径中最贵的一次收费在[L,R]区间内，所以收费大于R的路径是一定不可以经过的，而对于收费小于L的路径可以经过，但是不能让整条路径的收费全部小于L，要不然路径的最大值也小于L了。对此，我们要：将所有小于L的边连接的点缩成一个点（缩点），并记录缩后的点数（就是记录有多少个点缩成了这一个点），大于R的边则直接舍弃（不加到图中）。然后再搜索满足条件的点对的数量，比如：有3个点缩成的点A和2个点缩成的点B之间有一条[L,R]之间的边，那么就有2x3=6个点对。示意图如下： 对应的点对分别为：(1,4)、(1,5)、(2,4)、(2,5)、(3,4)、(3,5)。怎么实现缩点呢？并查集！将所有小于L的边连接的点用并查集来合并，让集合的根作为合并后的新点。注意记录集合的大小（也就是新点是由多少旧点合并来的）。最后使用 DFS 累加点对数量。比如点A是由3个旧点合并而来，与其连通的有2个新点，对应5个旧点，那么以A为第一个坐标的点对就有3x(8-3)对。注意累加的点对有重复（(1,2)、(2,1)是同一对），最后要除以二。代码cin=lambda:list(map(int,input().split()))n,m,l,r=cin()e=[set()for_inrange(n+1)]#s[i]==i表示i为新点，sz[i]表示新点i的大小s,sz=list(range(n+1)),[1]*(n+1)deffind(x):ifs[x]==x:returnxs[x]=find(s[x])returns[x]edges=[cin()for_inrange(m)]foru,v,winedges:ifw>r:continuesu,sv=find(u),find(v)ifw