2023年7月30日发(作者：)

【预览】蓝桥杯竞赛python算法模板｜蓝桥杯葵花宝典蓝桥杯经典算法模板⽂章⽬录1 ⼆分算法求分界值想看到完整代码模板 请订阅专栏～2 双指针算法2.1 求最长的不包含重复数字的连续⼦序列#

只会遍历整个数组⼀次j=0for i in range(n): while(j<=i and check(j,i)): j-=1 res=max(res,i-j-1)3 排列组合3.1 next_permutation 重排列⼀个序列 ⽣成它的上⼀个序列本代码的原题是luogu的⽕星⼈#

对于12345的序列

最多让我数到54321def nextP(index): global s for t in range(index): if(n<=1): #

如果⼀共的字母⼩于等于1

没什么要⼲的

返回 return for i in range(n-2,-1,-1):

#

从后往前看

找到第⼀个不是降序的数x if(s[i]

for j in range(n-1,-1,-1):

if(s[j]>s[i]): #

从后往前找

找到第⼀个⼤于x的数 s[i],s[j]=s[j],s[i] #

把它们交换 s[i+1:]=sorted(s[i+1:]) #

后⾯按照升序排序 break

break else: if(i==0): ()n=int(input())index=int(input())s=[int(i) for i in input().split()]nextP(index)print(' '.join(map(str,s)))#

没有括号的版本def nextP(index): global s for t in range(index): for i in range(n-2,-1,-1): if s[i]s[i]: s[i],s[j]=s[j],s[i] s[i+1:]=sorted(s[i+1:]) break break else: if i==0: ()n=int(input())index=int(input())s=[int(i) for i in input().split()]if n>1: nextP(index)print(" ".join(map(str,s)))3.3 n个数字/字母的不同排列# n个数字的不同排列from itertools import permutationsn=int(input())s=[i for i in input().split()]for p in permutations(s): print("".join(map(str,p)))# n个字母的不同排列str=list(input().split()) #

根据空格划分开for p in permutations(str): print("".join(p))3.4 n个数字选k个数的组合想看到完整代码模板 请订阅专栏～3.5 在n个数字中选1~n个数的不同组合3.5.1 ⾃⼰写dfs的⽅法想看到完整代码模板 请订阅专栏～4 组合数计算组合数⽤这个公式来计算：Ca=Ca−1+Ca−1 表⽰从a个苹果选择b个苹果 可以把选法（不重合不漏）分为2⼤类1. 包含此苹果Ca−12. 不包含此苹果Ca−1bb−1bbb−1想看到完整代码模板 请订阅专栏～5 快速幂利⽤a201log(k)快速计算出幂（⼆进制的思想）def qpow(a,k,mod): res=1 while(k): if(k&1): #

这⾥是取最后⼀位数 res=res*a%mod k>>=1 #

右移⼀位 a=a*a%mod #

把乘积翻倍 return resn=int(input())for k in range(n): a,k,p=map(int,input().split()) print(qpow(a,k,p))6 求质数6.1 试除法6.2 朴素筛法#

朴素筛法N=1000010n=int(input())st=[0 for i in range(N)] #

记录是否是质数 0表⽰是质数primes[0 for i in range(N)]cnt=0def get_primes(n): #

找出1-n的所有质数并存在primes[]数组中 global cnt,primes for i in range(2,n+1): if(st[i]==0): # i是质数 primes[cnt]=i cnt+=1 for j in range(i+i,n+1,i): st[j]=1get_primes(n)print(cnt)6.3 线性筛质数-只⽤最⼩质因⼦来筛想看到完整代码模板 请订阅专栏～7 约数和约数有关7.1 输出所有的约数想看到完整代码模板 请订阅专栏～7.2 约数的个数想看到完整代码模板 请订阅专栏～7.3 质因⼦分解想看到完整代码模板 请订阅专栏～8 欧⼏⾥得算法8.1 欧⼏⾥得#

简单的最⼤公约数def gcd(a,b): if b==0: return a return gcd(b,a%b)8.2 最⼩公倍数最⼩公倍数=两整数的乘积/最⼤公约数想看到完整代码模板 请订阅专栏～9 图和树有关9.1 建图⽅法#

建⽴邻接表N=100010e=[0 for i in range(N)] #

存放的是各边的到达结点的号ne=[0 for i in range(N)] # next指针数组

存放的邻接表的下⼀个节点的位置h=[-1 for i in range(N)] #

头指针数组

指向这个结点的相邻结点(存放头结点在e中的index)w=[0 for i in range(N)] #

边的权值# dis数组存的是到达对应index结点的最短距离idx=0def add(a,b,c): global idx,e,ne,h,w e[idx]=b w[idx]=c ne[idx]=h[a] h[a]=idx idx+=1#

访问某⼀个点的邻边的时候t=h[a]while(t!=-1): node=e[t] #

⼀定要去e[t]才是真的点

不然只是⼀个下标 #

对这个node进⾏⼀波操作 t=ne[t]9.2 最短路算法9.2.1 单源最短路-dijkstradijkstra算法必须规定起点（1）朴素dijkstra不常⽤ 背诵下⾯优化的dijkstra⽐较好#

朴素

使⽤邻接矩阵存N=510g=[[float('inf') for i in range(N)] for j in range(N)]st=[False for i in range(N)]dist=[float('inf') for i in range(N)]def dijkstra(start,end): #

从点start⾛到点end的路径 global dist,st,g dist[start]=0 for i in range(n): #

遍历从start开始的n个点 t=-1 for j in range(1,n+1): if(st[j]==False and (t==-1 or dist[t]>dist[j])): # t==-1

表⽰是遇到的第⼀个点 dist[t]>dist[j]表⽰要更新当前路径最短的点 t=j if(t==end): #

最短路已经更新到了end break #

如果要寻找到所有点的最短路不知道还要不要break st[t]=True

想看到完整代码模板 请订阅专栏～（2）堆优化dijkstra想看到完整代码模板 请订阅专栏～9.2.2 多源汇最短路-SPFA算法SPFA是bellman-ford的改进版SPFA算法可以算出从起点到任何点的最短路想看到完整代码模板 请订阅专栏～9.3 最⼩⽣成树算法最⼩⽣成树算法在⽆向图上使⽤，背下来kruskal就可以了9.3.1 kruskal最⼩⽣成树想看到完整代码模板 请订阅专栏～9.3.2 prim最⼩⽣成树不常⽤ ⼀般⽤kruskal想看到完整代码模板 请订阅专栏～9.3.3 拓扑排序想看到完整代码模板 请订阅专栏～10 差分算法想看到完整代码模板 请订阅专栏～11 并查集#

并查集find函数def find(x):

if(x!=p[x]): p[x]=find(p[x])

return p[x]#

并查集union函数for i in range(m):

a,b=map(int,input().split())

pa,pb=find(a),find(b)

if(pa!=pb): p[pa]=pb #

注意这⾥的操作！！12 DFS和BFS12.1 DFS1. 内部搜索（棋盘的结点作为结点）2. 外部搜索（棋盘的状态作为结点）# dfs基本框架def dfs():

12.2 BFS-和最短路有关的问题# bfs基本框架queue=[]([sx,sy]) #

初始结点⼊队while(queue):

front=(0)

...bfs最经典的是最短步数问题，每次向各个⽅向⾛⼀步的时候就step+113 DP背包模版（重点）13.1 01背包（1）⼆维/基本的01背包想看到完整代码模板 请订阅专栏～（2）⼀维的01背包想看到完整代码模板 请订阅专栏～13.2 完全背包（1）朴素完全背包想看到完整代码模板 请订阅专栏～（2）优化的⼆维完全背包想看到完整代码模板 请订阅专栏～（3）优化的⼀维完全背包想看到完整代码模板 请订阅专栏～13.3 多重背包（1）朴素的多重背包想看到完整代码模板 请订阅专栏～（2）⼆进制优化的多重背包想看到完整代码模板 请订阅专栏～13.4 分组背包-类似多重背包想看到完整代码模板 请订阅专栏～14 DP数字三⾓形从下到上更新n=int(input())f=[]for i in range(n): ([int(i) for i in input().split()])for i in range(n-2,-1,-1): #

从n-2(倒数第⼆⾏)到0⾏ for j in range(i+1): #

列内按从左到右

⼀列的数字个数是i+1个 f[i][j]+=max(f[i+1][j],f[i+1][j+1]) #

左下和右下较⼤print(f[0][0])从上到下更新想看到完整代码模板 请订阅专栏～15 DP的LCS模版最长上升⼦序列想看到完整代码模板 请订阅专栏～最长公共⼦序列想看到完整代码模板 请订阅专栏～最长公共上升⼦序列想看到完整代码模板 请订阅专栏～16 记忆化搜索摘花⽣#

摘花⽣dp做法T=int(input())for t in range(T): n,m=map(int,input().split()) f=[[] for j in range(110)] f[0]=[0 for i in range(m+1)] for i in range(1,n+1): f[i]=[0]+[int(i) for i in input().split()] for i in range(1,n+1): for j in range(1,m+1): f[i][j]+=max(f[i-1][j],f[i][j-1]) print(f[n][m])#

摘花⽣记忆化搜索def dfs(x,y): global res,cur dx=[1,0] dy=[0,1] cur+=f[x][y] if(x==n and y==m): res=max(res,cur) return for i in range(2): xx=x+dx[i] yy=y+dy[i] if(xx<1 or yy<1 or xx>=n or yy>=m): continue dfs(xx,yy) cur-=f[x][y]T=int(input())res=0cur=0for t in range(T): n,m=map(int,input().split()) f=[[] for j in range(110)] f[0]=[0 for i in range(m+1)] for i in range(1,n+1): f[i]=[0]+[int(i) for i in input().split()]dfs()

print(res)