蓝桥杯常见算法模板（Python组）
目录
（图片来源网络，侵删）
1.二分
1.整数二分（二分答案）：
2.浮点数二分（考不到）
2.前缀和、差分
1.前缀和
一维：
二维：
2.差分
一维：
二维：
3.贪心
4.线性DP
1.最长上升子序列（子序列问题一般下标从一开始）
2.最长公共子序列
3.常见背包模型
1.0-1背包
2.完全背包
3.多重背包
4.混合背包
5.二维费用背包
6.分组背包
5.搜索
1.DFS
模板：
1.子集问题
2.全排列问题
2.BFS
6.数据结构
1.并查集
2.树状数组
3.树的直径
4.LCA最近公共祖先
7.图论
1.最短路径问题
1.dijkstra算法
2.Floyd算法
3.Bellman-Ford算法
3.拓朴排序
8.数论
1.二分
1.整数二分（二分答案）：
！关键是判断是否有单调性 以及如和确定mid是否合法
**常用于最大值最小化、最小值最大化(求最值时也可以考虑)**
#check函数最重要也最难写
def check(x):
#判断x是否合法，合法True，否则False
pass
l,r = #初始化，一般最边界
ans = #初始化
while l = eps:
mid = (l+r)/2
if check(mid):
r = mid#二选一
else:
l = mid
2.前缀和、差分
1.前缀和
一维：
**用于求 区间和 O(1) 算法**
n = int(input())
a = list(map(int,input().split()))
def pre(a):
sum = [0]*n
sum[0] = a[0]
for i in range(1,n):
sum[i] = sum[i-1] + a[i]
return sum
def qiuhe(l,r,sum):
if l == 0:
return sum[0]
else:
return sum[r] - sum[l-1]
二维：
n,m = map(int,input().split())
a = [[0]*(m+1) for i in range(n+1)]
sum = [[0]*(m+1) for i in range(n+1)]
for i in range(1,n+1):
a[i] = [0] + list(map(int,input().split()))
for i in range(1,n+1):
for j in range(1,m+1):
sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + a[i][j]
def qiuhe(x1,y1,x2,y2,sum):
#左下角加左上角-两外两个角（有三个角移位）
return sum[x2][y2] - sum[x1-1][y1] - sum[x2][y1-1] + sum[x1-1][y1-1]
2.差分
一维：
对差分数组求前缀和是原数组
n = int(input())
a = list(map(int,input().split()))
d = [0]*(n)
d[0] = a[0]
for i in range(1,n):
d[i] = a[i] - a[i-1]
#区间增加数 复杂度O（1）
def xiugai(l,r,x):
d[l] += x
d[r + 1] -= x
#对差分数组求前缀和复原数组 不能同时进行修改查询
a[0] = d[0]
for i in range(1,n):
a[i] = a[i-1] + d[i]
二维：
#构造差分数组
n,m =map(int,input().split())
a = [[0]*(m+1) for i in range(n+1)]
diff = [[0]*(m+1) for i in range(n+1)]
for i in range(1,n+1):
a[i] = [0] + list(map(int,input().split()))
#构造差分数组
for i in range(1,n+1):
for j in range(1,m+1):
diff = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]
#原矩阵要增加值 复杂度O(1)
def xiugai(x1,y1,x2,y2,c):
diff[x1][y1] += c
diff[x1][y2 + 1] -= c
diff[x2 + 1][y1] -= c
diff[x2 + 1][y2 + 1] += c
N = 1010
def insert(x1, y1, x2, y2, c):
b[x1][y1] += c
b[x2 + 1][y1] -= c
b[x1][y2 + 1] -= c
b[x2 + 1][y2 + 1] += c
n, m, q = map(int, input().split())
a = [[0] * N for _ in range(N)]
b = [[0] * N for _ in range(N)]
for i in range(1, n + 1):
a[i][1:] = map(int, input().split())
for i in range(1, n + 1):
for j in range(1, m + 1):
insert(i, j, i, j, a[i][j])
while q > 0:
q -= 1
x1, y1, x2, y2, c = map(int, input().split())
insert(x1, y1, x2, y2, c)
for i in range(1, n + 1):
for j in range(1, m + 1):
b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1]
print(b[i][j], end=" ")
print()
3.贪心
**无具体算法，需仔细分析每一步，思考如何由小问题合成大问题，如何求子问题解**
需仔细分析，一般要用到排序
思想：把整个问题分解成多个步骤，在每个步骤，都选取当前步骤的最优方案，直到所有步骤结束；在每一步，都不考虑对后续步骤的影响，在后续步骤中也不能回头改变前面的选择
4.线性DP
处理DP中的大问题和小问题，有两种思路：自顶向下（Top-Down，先大问题再小问题）、自下而上（Bottom-Up，先小问题再大问题）。
编码实现DP时，自顶向下用带记忆化搜索的递归编码，自下而上用递推编码。两种方法的复杂度是一样的，每个子问题都计算一遍，而且只计算一遍。
能用DP求解的问题，一般是求方案数，或者求最值。
***注意考虑边界***
1.最长上升子序列（子序列问题一般下标从一开始）
#最长上升子序列
a = [0] + list(map(int,input().split()))
n = len(a)
#dp[i]表示以i结尾的最长上升子序列
#并且初始为1
dp = [0] + [1]*n
for i in range(1，n):
for j in range(1,i):
if a[i] > a[j]:
dp[i] = max(dp[i],dp[j] + 1)
print(max(dp))
2.最长公共子序列
#最长公共子序列
n,m = map(int,input().split())
a = [0] + list(map(int,input().split()))
b = [0] + list(map(int,input().split()))
#dp[i]表示以i结尾的最长上升子序列
#并且初始为1
dp = [[0]*(m+1) for i in range(n+1)]
for i in range(1,n+1):
for j in range(1,m+1)
if a[i] == b[i]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j],dp[i][j-1])
print(dp[n][m])
3.最长回文子串
def longest_palindromic_substring(s):
n = len(s)
if n == 0:
return ""
# 创建一个二维数组 dp，其中 dp[i][j] 表示从索引 i 到 j 的子串是否为回文子串
dp = [[False] * n for _ in range(n)]
# 初始化：所有长度为1的子串都是回文串
for i in range(n):
dp[i][i] = True
start, max_len = 0, 1 # 记录最长回文子串的起始位置和长度
# 动态规划递推
for l in range(2, n + 1): # 枚举子串长度
for i in range(n - l + 1): # 枚举子串的起始位置
j = i + l - 1 # 子串的结束位置
if s[i] == s[j]:
if l == 2 or dp[i + 1][j - 1]:
dp[i][j] = True
if l > max_len:
start = i
max_len = l
return s[start:start + max_len]
# 测试
s = input().strip()
print(longest_palindromic_substring(s))
3.常见背包模型
1.0-1背包
n,v = map(int,input().split())
dp = [[0]*(v+1) for i in range(n+1)]
for i in range(1,n+1):
wi,vi = map(int,input().split())
for j in range(v+1):
if j
2.完全背包
n,v = map(int,input().split())
dp = [[0]*(v+1) for i in range(n+1)]
for i in range(1,n+1):
wi,vi = map(int,input().split())
for j in range(v+1):
if j
3.多重背包
n,v = map(int,input().split())
dp = [[0]*(v+1) for i in range(n+1)]
for i in range(1,n+1):
wi,vi,si = map(int,input().split())
for j in range(v+1):
for k in range(min(si,j//wi)):
dp[i][j] = max(dp[i][j],dp[i-1][j-k*wi] + k*vi)
print(dp[n][v])
#优化成一维背包
#二进制拆分 减少第一维数量 可凑成原来数量
n,v = map(int,input().split())
w_v = []
for i in range(n):
wi,vi,si = map(int,input().split())
k = 1
while si>=k:
w_v.append((k*wi,k*vi))
si-=k
k*=2
if si!=0:
w_v.append((si*wi,si*vi))
for i,(w,v) in enumerate(w_v):
for j in range(v,w-1,-1):
dp[j] = max(dp[j],dp[j-w]+v)
4.混合背包
N, V = map(int, input().split())
dp = [0]*(V+1)
for _ in range(N):
w, v ,n= map(int, input().split())
#如果n为0或者n*w大于等于V，说明该物品只能选择一次或者不能选择，因此直接使用01背包的方式更新dp列表
if n==0 or n*w>=V:
for j in range(w,V+1):
dp[j] = max(dp[j], dp[j-w]+v)
#否则，对于每个物品，使用完全背包的方式更新dp列表。
else :
for k in range(n):
for j in range(V,w-1,-1):
dp[j] = max(dp[j], dp[j-w]+v)
print(dp[-1])
5.二维费用背包
N,V,M = map(int,input().split())
dp = [[0]*(M+1) for i in range(V+1)]
for i in range(N):
v,m,w = map(int,input().split())
for j in range(V,v-1,-1):
for k in range(M,m-1,-1):
dp[j][k] =max(dp[j][k],dp[j-v][k-m] + w)
print(dp[V][M])
6.分组背包
N,V = map(int,input().split())
dp = [[0]*(V+1) for i in range(2)]
for i in range(1,N+1):
s =int(input())
for nn in range(s):
w,v = map(int,input().split())
for j in range(V+1):
if j
5.搜索
1.DFS
**必考**
n重循环 = 树状结构 = DFS搜索（通常用到标记数组(连通块必用到)）
每项选择相互独立 则无需递归
模板：
def dfs(depth):
if depth == n:
*********
return
#条件 + 递归 注意参数 有时候答案可通过参数直接传递
1.子集问题
n = int(input())
a = list(map(int,input().split()))
path = []
def dfs(depth):
if depth == n:
print(path)
return
#选
path.append(a[depth])
dfs(depth + 1)
path.pop()
#不选
dfs(depth + 1)
dfs(0)
2.全排列问题
path = []
vis = [0]*(n+1)
def dfs(x):
if x == n :
print(path)
return
for i in range(1,n+1):
if vis[i] == 0:
path.append(i)
vis[i] = 1
dfs(x+1)
#恢复现场
vis[i] = 0
path.pop()
dfs(0)
2.BFS
思想：全面扩散、逐层递进
***用来求最短路（边长相等）***
from collections import deque
def bfs():
result = []
queue = deque()
queue.append(root)
while queue:
u = queue.popleft()
result.append(u)
for v in G[u]:
queue.append(v)
return result
6.数据结构
1.并查集
import os
import sys
#找父亲
def Findroot(x):
if x == p[x]:
return x
p[x] = Findroot(p[x])#路径压缩
return p[x]
#合并两集合
def Merge(x,y):
rootx = Findroot(x)
rooty = Findroot(y)
p[rootx] = rooty
#查询两集合
def Query(x,y):
rootx = Findroot(x)
rooty = Findroot(y)
return rootx == rooty
N,M = map(int,input().split())
p = list(range(N+1))
for i in range(M):
op,x,y = map(int,input().split())
if op == 1:
Merge(x,y)
else:
if Query(x,y):
print("YES")
else:
2.树状数组
***利用树状数组可在log时间内对数组进行
1.区间修改：区间+x
2.单点查询：list[x]
def lowbit(x):
return x&(-x)
#走过的点加y，直到走到最左
def add(x,y):
while x d[S]:
S = u
for v, w in G[u]:
if v == fa:
continue
d[v] = d[u] + w
dfs(v, u)
# S表示最深的点
S = 1
# 从1开始找最深的的
dfs(1, 0)
# 再从S开始找最深的点
d[S] = 0
dfs(S, 0)
print(d[S])
4.LCA最近公共祖先
def dfs(u,fa):
deep[u] + deep[fa] + 1
p[u][0] = fa
for i in range(1,21):
p[u][i] = p[p[u][i-1]][i-1]
for v in G[u]:
if v == fa:
continue
dfs(v,u)
def LCA(x,y):
if deep[x] = deep[y]:
x = p[x][i]
if x == y:
return x
for i in range(20,-1,-1):
if p[x][i] != p[y][i]:
x,y = p[x][i],p[y][i]
return p[x][0]
7.图论
1.最短路径问题
1.dijkstra算法
# 请在此输入您的代码
#优先队列来做，每次出最小的点
from queue import PriorityQueue
INF = 1e18
def dj(s):
#d数组表示每个点到s的最短距离
d = [INF]*(n+1)
#vis表示其是否已经被更新到最短路径
#其第一次出队列可判断其也被更新到到最短路径
vis = [0]*(n+1)
pq = PriorityQueue()
d[s] = 0
pq.put((d[s],s))#起点放入队列
while not pq.empty():
dis,u = pq.get()
if vis[u] :
continue
vis[u] = 1
for v,w in G[u]:
if d[v] > d[u] + w:
d[v] = d[u] + w
pq.put((d[v],v))
for i in range(1,n+1):
if d[i] == INF :
d[i] = -1
return d[1::]
n,m = map(int,input().split())
G = [[] for i in range(n+1)]
for i in range(m):
u,v,w = map(int,input().split())
G[u].append([v,w])
print(*dj(1),sep = " ")
2.Floyd算法
INF = 1e18
n,m,q = map(int,input().split())
#邻接矩阵来存图
#DP表示点到点的最小距离 dp数组其既是邻接矩阵又是优化算法
dp = [[INF]*(n+1) for i in range(n+1)]
for i in range(n+1):
dp[i][i] = 0
for i in range(m):
u,v,w =map(int,input().split())
dp[u][v] = dp[v][u] = min(dp[u][v],w)# 去重边
#Floyd算法
for k in range(1,n+1):
for i in range(1,n+1):
for j in range(1,n+1):
dp[i][j] = min(dp[i][j],dp[i][k]+ dp[k][j])
for i in range(q):
s,e = map(int,input().split())
if dp[s][e] == INF:
print(-1)
else:
print(dp[s][e])
3.Bellman-Ford算法
n,m = map(int,input().split())
c = [0] + list(map(int,input().split()))
#存边 枚举边
e = []
for i in range(m):
u,v,w = map(int,input().split())
e.append([u,v,w])
e.append([v,u,w])
#表示起点到该点的INF最短距离
INF = 1e9
d = [INF]*(n+1)
d[1] = 0
for i in range(n-1):
for u,v,w in e:
if d[v] > d[u] +w:
d[v] = d[u] +w
print(d[n])
3.拓朴排序
借助队列处理为0的点
from collections import deque
def tuopo():
result = []
q = deque()
#筛选入度空的点
for i in range(1,n+1):
if rudu[i] = 0:
q.append(i)
#只要队列不空
while q:
u = q.popleft()
result.append(u)
for v in G[u]:
rudu[v] -= 1
#再次筛选
if rudu[v] == 0
q.append(v)
if len(result) != n:
print("error")
else:
print(*result,sep = " ")
8.数论
from math import gcd
from math import lcm
#1. gcd 最大公因数
# lcm 最小公倍数
#手写
def gcd(a,b):
if b == 0:
return a
return gcd(b,a%b)
def lcm(a,b):
return a*b//gcd(a,b)
#调用库
# 两个整数的最大公约数
num1 = 12
num2 = 18
result = gcd(num1, num2)
print(f"最大公约数为: {result}")
#2.同余 暴力
res = 1
n = 10000
mod = 10007
for i in range(1,n+1):
res = (res *i) %mod
print(res)
#3.向上取整
print((a+b-1)%b)
#4.素数筛选
#***埃氏筛选
def is_prime(x):
vis = [0]*(n+1)
vis[0] = 1
vis[1] = 1
prime = []
for i in range(1,n+1):
if vis[i] == 0:
prime.append(i)
for m in range(i + i,n+1,i):
vis[m] = 1
return prime
#暴力
def is_prime(n):
"""判断一个数是否为素数"""
if n > 1
return res
文章版权声明：除非注明，否则均为主机测评原创文章，转载或复制请以超链接形式并注明出处。
