第15届蓝桥杯省赛python组A,B,C集合

        过几天就省赛了，一直以来用的是C++，Python蓝桥杯也是刚刚开始准备（虽然深度学习用的都是python，但是两者基本没有任何关系），这两天在做去年题时犯了很多低级错误，因此记录一下以便自己复查

PS：很多问题的实现其实都是基于C++换成python的，因此很多代码显得比较丑，还请见谅。

为了结构清晰，我从Python易错点和2024年题目这两部分进行展开：

2024真题（大部分写了，但有一小部分没有做）：

1.树状数组+思维：6000. 植物生命力 - AcWing题库

思路：

我们反过去考虑，一个点的贡献不就是当前链上的比他大的又不是它的倍数的点的个数吗？这个链怎么保证呢？DFS递归序列不就是一条链吗，因此这点可以通过DFS实现，那怎么查到比他大的数又不是整除的呢？不妨先考虑比他大的，我们在DFS过程中维护树状数组即可，我们再通过枚举它的倍数对整除的进行排除即可。

代码实现：

import sysfrom types import GeneratorType
def bootstrap(f, stack=[]):def wrappedfunc(*args, **kwargs):if stack:return f(*args, **kwargs)else:to = f(*args, **kwargs)while True:if type(to) is GeneratorType:stack.append(to)to = next(to)else:stack.pop()if not stack:breakto = stack[-1].send(to)return toreturn wrappedfuncn,s=map(int,input().split())
a=list(map(int,input().split()))
a=[0]+a
edge=[[] for i in range(n+10)]
tr=[0 for i in range(200010)]
vis=[0 for i in range(200010)]
ans=0
def lowbit(x):return x&-xdef add(pos,v):while pos<=n:tr[pos]+=vpos=pos+lowbit(pos)def get(pos):res=0while pos>0:res+=tr[pos]pos-=lowbit(pos)return res@bootstrap
def dfs(root,fa):global ansglobal nres=get(n)-get(a[root])for i in range(2*a[root],n+1,a[root]):if vis[i]==1:res-=1ans+=resvis[a[root]]=1add(a[root],1)for i in edge[root]:if i==fa:continueyield dfs(i,root)vis[a[root]]=0add(a[root],-1)yield Nonefor _ in range(n-1):u,v=map(int,input().split())edge[u].append(v)edge[v].append(u)dfs(s,-1)
print(ans)

2.trie树链路减法：5999. 最大异或结点 - AcWing题库

思路：如果不管那个不能异或相连的点的话就是一个很板的字典树问题，现在我们的问题就是如何解决这个相连点不能异或的限制。

比较直观的想法就是把那个节点相邻的点从字典树中删除，然后正常操作，最后再恢复，那么如何实现呢？比较巧妙地，我们再新开一个数组来记下树上每个点的出现次数，删除的话就是依次从树链中走下来，走到的节点位置次数-1即可。

代码实现：

import sys
from types import GeneratorType
def bootstrap(f, stack=[]):def wrappedfunc(*args, **kwargs):if stack:return f(*args, **kwargs)else:to = f(*args, **kwargs)while True:if type(to) is GeneratorType:stack.append(to)to = next(to)else:stack.pop()if not stack:breakto = stack[-1].send(to)return toreturn wrappedfunc
ans = 0
ind = 1
n = int(input())
N = 32 * n + 10
w = list(map(int, input().split()))
fa = list(map(int, input().split()))
tr = [[0 for i in range(2)] for i in range(N)]
id = [-1 for i in range(N)]
cnt = [0] * (N + 10)
mp = {}for i in range(n):if fa[i] == -1:continuemp[i] = []mp[i].append(fa[i])mp[fa[i]] = []mp[fa[i]].append(i)def insert(x):global indww = w[x]root = 0for i in range(30, -1, -1):j = ww >> i & 1if tr[root][j] == 0:tr[root][j] = indind += 1root = tr[root][j]cnt[root] += 1id[root] = xdef remove(x):root = 0for i in range(30, -1, -1):j = x >> i & 1cnt[tr[root][j]] -= 1root = tr[root][j]@bootstrap
def query(x, root, len):global ansif len == -1:ans = max(ans, w[x] ^ w[id[root]])yield Nonei = w[x] >> len & 1if cnt[tr[root][1 - i]] > 0:yield query(x, tr[root][1 - i], len - 1)else:yield query(x, tr[root][i], len - 1)yield Nonefor i in range(n):insert(i)
for i in range(n):for k in mp[i]:remove(w[k])query(i, 0, 30)for k in mp[i]:insert(k)print(ans)

3.递推+简单博弈：6001. 砍柴 - AcWing题库

思路：很显然，对于长度X，只要有一个质数使X-它是一个必胜态，X就是先手的必胜态，这可以通过记忆化搜索快速实现

代码实现：

t=int(input())
isp =[1 for i in range(10**5+10)]
pri=[]dp=[-1 for i in range(10**5+10)]def f(x):if dp[x]!=-1:return dp[x]ans=1#只要有一条路到dp[k]=0就可以for i in pri:if i>x:breakif f(x-i)==0:ans=0breakif ans==0:dp[x]=1else:dp[x]=0return dp[x]for i in range(2,10**5+10):if isp[i]:pri.append(i)for j in pri:if i*j>1e5:breakisp[i*j]=0if i%j==0:breakdp[0]=dp[1]=0
dp[2]=dp[3]=1
for i in range(4,10**5+1):dp[i]=f(i)for i in range(t):k=int(input())print(dp[k])

4.思维题：5996. 回文字符串 - AcWing题库

思路：这题比较有意思，首先我们需要发现一个特点：任何一个字符串都是ABC的形式，其中A和C只有l,q,b这些字母，而B则是没有l,q,b的字符串。

想到了这一点，后面就自然而然了：我们可以得到要yes的话的就必须满足（1）或（2）（3）：

（1）B为空

（2）B为回文串

（3）A的逆序串是C的前缀

代码实现：

t=int(input())def jd(k):if k=='l' or k=='q' or k=='b':return 1return 0
for _ in range(t):s=input()s="0"+sl=0r=len(s)for i in range(1,len(s)):if jd(s[i])==0:breakl+=1if l==len(s)-1:print("Yes")continuefor i in range(len(s)-1,0,-1):if jd(s[i])==0:breakr-=1ss=''.join(reversed(s[l+1:r]))if ss!=s[l+1:r]:print("No")continuewhile l>=1 and r<=len(s)-1 and s[l]==s[r]:l-=1r+=1if l==0:print("Yes")else:print("No")

5.模拟：5993. 回文数组 - AcWing题库

思路：我们从两端开始向内收缩，然后简单分类讨论一下即可

代码实现：

n=int(input())
a=[0]+list(map(int,input().split()))
ans=0
for i in range(1,n//2+1):if a[i]==a[n-i+1]:continueelif a[i]>a[n-i+1]:ans+=abs(a[i]-a[n-i+1])if i+1>=n-i+1-1:continueelse:if a[i+1]>a[n-i]:if abs(a[i]-a[n-i+1])>=a[i+1]-a[n-i]:a[i+1]=a[n-i]else:a[i+1]-=abs(a[i]-a[n-i+1])else:ans+=abs(a[i]-a[n-i+1])if i+1>=n-i+1-1:continueelse:if a[i+1]<a[n-i]:if abs(a[i]-a[n-i+1])>=a[n-i]-a[i+1]:a[i+1]=a[n-i]else:a[i+1]+=abs(a[i]-a[n-i+1])
print(ans)

6.结论题：5991. 数字诗意 - AcWing题库

思路：建议大家去按照等比数列写一下数学式子，再带几个数进去，或者建议这种看规律的打一下表，最后就是除了2的幂次方其他都可以，另外有一个小trick就是通过(x-1)&x来快速判断一个数是否为2的幂次

代码实现：

n=int(input())
k=[0]+list(map(int,input().split()))ans=0
def jud(num):if (num-1)&num==0:return 1return 0
for i in range(1,n+1):if jud(k[i])==1:ans+=1
print(ans)

7.最大生成树+动态规划：5997. 吊坠 - AcWing题库

思路：说实话，个人感觉这个题就是这两个知识点硬凑上去。首先我们先求边权，这里看到环很容易想到石子合并破环成链，我们复制一遍然后就是DP了。

求完边权后就是一个典型的最大生成树了

代码实现：

n,m=map(int,input().split())s=[]for i in range(n):s.append(input())s[-1]=s[-1]*2mp=[[-1 for i in range(n+1)] for j in range(n+1)]def calc(x,y):if(mp[x][y]!=-1):return mp[x][y]ans=0dp=[[0 for i in range(2*m+1)] for j in range(2*m+1)]for i in range(1,2*m+1):for j in range(1,2*m+1):if s[x][i-1]==s[y][j-1]:dp[i][j]=dp[i-1][j-1]+1else:dp[i][j]=0ans=max(ans,dp[i][j])mp[x][y]=mp[y][x]=min(m,ans)return mp[x][y]for i in range(n):for j in range(n):mp[i][j]=calc(i,j)dis=[-1e9 for i in range(n+1)]
vis=[0 for i in range(n+1)]
dis[0]=0
ans=0
for i in range(n):x=0for j in range(n):if vis[x] or ((not vis[j]) and dis[j]>dis[x]):x=jans+=dis[x]vis[x]=1for y in range(n):dis[y]=max(dis[y],calc(x,y))
print(ans)

8.思维题：6008. 连连看 - AcWing题库

思路：可以发现满足的两点都是在y=x或者y=-x上，因此我们就依次枚举矩形的对角线（不是很准确），然后看看上面有几个相等的元素即可。

代码实现：

g=[[0]*1010 for i in range(1010)]def dg(x,y):cnt=[0]*(1010)if x==n or y==m:return 0while x<=n and y<=m:cnt[g[x][y]]+=1x+=1y+=1res=0for i in range(1,1001):if cnt[i]>1:res+=cnt[i]*(cnt[i]-1)return resdef udg(x,y):cnt=[0]*(1010)if x==n or y==1:return 0while x<=n and y>=1:cnt[g[x][y]]+=1x+=1y-=1res=0for i in range(1,1001):if cnt[i]>1:res+=cnt[i]*(cnt[i]-1)return resif __name__=='__main__':n,m=map(int,input().split())ans=0for i in range(1,n+1):tt=list(map(int,input().split()))for j in range(1,m+1):g[i][j]=tt[j-1]for i in range(1,n+1):ans+=dg(i,1)for i in range(2,m+1):ans+=dg(1,i)for i in range(1,m+1):ans+=udg(1,i)for i in range(2,n+1):ans+=udg(i,m)print(ans)

9.模拟题：6009. 神奇闹钟 - AcWing题库

思路：蓝桥杯一贯的日历问题，大家记住闰年以及2月的日子+细心就没多大问题了

代码实现：

days=[0,31,28,31,30,31,30,31,31,30,31,30,31]def is_leap(y):return y%400==0 or y%4==0 and y%100!=0def dayofmonth(y,m):if m==2:return 28+is_leap(y)return days[m]def bd(y,m,d):yy,mm,dd=1970,1,1res=0while yy!=y:res+=365+is_leap(yy)yy+=1while mm!=m:res+=dayofmonth(yy,mm)mm+=1res+=d-1return resdef get(y,m,d,h,mi):res=bd(y,m,d)*24*60res+=60*hres+=mireturn resdef nextday(k):y,m,d,h,mi,s=1970,1,1,0,0,0while k>=(365+is_leap(y))*24*60:k-=(365+is_leap(y))*24*60y+=1while k>=dayofmonth(y,m)*24*60:k-=dayofmonth(y,m)*24*60m+=1while k>=24*60:k-=24*60d+=1h=k//60mi=k%60print("%d-%02d-%02d %02d:%02d:%02d"%(y,m,d,h,mi,s))t=int(input())
for _ in range(t):s1,s2,s3=input().split()y,m,d=map(int,s1.split('-'))h,mi,s=map(int,s2.split(":"))x=int(s3)k=get(y,m,d,h,mi)k-=k%xnextday(k)

10.分类讨论：6010. 蓝桥村的真相 - AcWing题库

思路：从一开始就最多只有四种情况：101，110，011，000，然后依次讨论即可

代码实现：

t=int(input())
for _ in range(t):n=int(input())if n%3==0:print(2*n)else:print(n)

11.并查集：6012. 缴纳过路费 - AcWing题库

代码实现：

n,m,l,r=map(int,input().split())
fa1=[i for i in range(n+10)]
siz1=[1 for i in range(n+10)]
fa2=[i for i in range(n+10)]
siz2=[1 for i in range(n+10)]
def find(x):if x==fa1[x]:return xfa1[x]=find(fa1[x])return fa1[x]
def find1(x):if x==fa2[x]:return xfa2[x]=find1(fa2[x])return fa2[x]
def merge(x,y):if find(x)==find(y):returnsiz1[find(y)]+=siz1[find(x)]fa1[find(x)]=find(y)
def merge1(x,y):if find1(x)==find1(y):returnsiz2[find1(y)]+=siz2[find1(x)]fa2[find1(x)]=find1(y)
for i in range(m):u,v,w=map(int,input().split())if w<=r:merge(u,v)if w<l:merge1(u,v)
ans=0
for i in range(1,n+1):if find(i)==i:ans+=(siz1[i]-1)*siz1[i]//2if find1(i)==i:ans-=(siz2[i]-1)*siz2[i]//2
print(ans)

12.思维+分类讨论：6013. 纯职业小组 - AcWing题库

思路：这题感觉出的还蛮好的。我们先进行离散化：这里用去重+排序+二分。然后我们先判断可不可以：对于每一个//3求和并和k比较即可。

当判断可以后，我们再原问题进行转化（因为直接求k个的最小比较麻烦）：等价于求k-1个的最大数+1

接下来，对于<=2的我们就直接全取，对于>2的：假设是一个类别中为001001...（只是为了方便解释，实际上是同一个）我们先全部取2，现在就是1001....然后分3组：

（1）最后是1

（2）最后是10

  (3) 最后是100

显然(3)最理想，(2)其次，(1)最后，有几个（3）呢？就是(c[i]-2)//3的求和，（1）（2）通过（c[i]-2)%3可以得到。最后答案按照这个思路求即可

代码实现：

def makearray(length):return [0 for i in range(length)]t=int(input())
N=2*10**5+10
a=makearray(N)
b=makearray(N)
c=makearray(N)def bseek(arr,val):l,r=0,len(arr)-1while l<r:mid=(l+r)//2if arr[mid]>val:r=midelif arr[mid]<val:l=mid+1else:return midreturn l
for _ in range(t):n,k=map(int,input().split())k-=1for i in range(n):aa,bb=map(int,input().split())a[i]=aab[i]=bbc[i]=0sa=a[:n]#set会改变顺序！！！！！！sa=list(set(sa))sa.sort()# for i in range(len(sa)):#     print(sa[i],end=" ")#     print()for i in range(n):c[bseek(sa,a[i])]+=b[i]res=summ=0d=[0,0,0]count=kcnt=0for i in range(0,len(sa)):summ+=c[i]//3if c[i]<=2:res+=c[i]else:res+=2cnt+=((c[i]-2)//3)d[(c[i]-2)%3]+=1if summ<k:print(-1)continuecnt=min(cnt,k)res+=cnt*3k-=cntfor i in range(2,0,-1):tx=min(d[i],k)k-=txres+=tx*iprint(res+1)

易错点：

1.递归不能太深：

该问题来源于植物生命力这题，正常的DFS递归只得到了70%的分，原因在于递归太深了

一般求树、图的问题，涉及到的递归深度一般1e5的数量级，而python的默认递归深度为1000

怎么解决呢？我们可以通过装饰器来把递归改成迭代的形式，听上去很难，但是可以直接当成一个模板来记，这样就AC了，但是可能会MLE（目前还没有遇到这种情况）

具体方法如下：

py装饰器强行DFS，突破递归深度限制_灵神的codeforce账号-CSDN博客

按照上面博客写的套到自己DFS上就可以啦

2.Python中reverse方法返回的迭代器，如果要变成string可以参考第四题的写法：

3.时刻注意for中左闭右开的原则，第五题我的循环for(1,n//2)一直没检查出来（我太菜了）

4.python中set会把原来有序的列表打乱，所以应该是先去重再排序

5.函数体用到外面的变量记得先声明全局变量