蓝桥杯常见算法模板（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    passl,r = #初始化，一般最边界ans = #初始化while l <= r:    mid = (l+r)//2    if check(mid):        ans = mid        l = mid + 1#二选一，视题目以及自己定义条件            else:        r = mid - 1

2.浮点数二分（考不到）

def check():    passl,r = #初始化eps = 1e-4while r - 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 sumdef 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] += cN = 1010def 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] += cn, 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结尾的最长上升子序列#并且初始为1dp = [0] + [1]*nfor 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结尾的最长上升子序列#并且初始为1dp = [[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 < wi:            dp[i][j] = dp[i-1][j]        else:            dp[i][j] = max(dp[i-1][j],dp[i-1][j-wi] + vi)#滚动数组优化#只用到一维 由于每一项与上一行的前一项有关，故需要从后向前更新#并且if 选项不再需要（只有一维）n,v = map(int,input().split())dp = [0]*(v+1)for i in range(1,n+1):    wi,vi = map(int,input().split())    for j in range(v,wi-1):        dp[j] = max(dp[j],dp[j-wi]+vi)

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 < wi:            dp[i][j] = dp[i-1][j]        else:            dp[i][j] = max(dp[i-1][j],dp[i][j-wi] + vi)#滚动数组优化#只用到一维 由于每一项与左边一项有关，故需要从前向后更新#并且if 选项不再需要n,v = map(int,input().split())dp = [0]*(v+1)#和零一背包区别只在更新方向for i in range(1,n+1):    wi,vi = map(int,input().split())    for j in range(wi,v+1):        dp[j] = max(dp[j],dp[j-wi]+vi)

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 < w:                dp[i%2][j] = max(dp[i%2][j],dp[(i-1)%2][j])            else:                dp[i%2][j] = max(dp[i%2][j],dp[(i-1)%2][j],dp[(i-1)%2][j-w] + v)print(dp[N%2][V])

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 dequedef 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 osimport 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 == rootyN,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 <= n:        tree[x] += y        x += lowbit(x)#ans += 走过的点 知道走到最右def query(x):    ans = 0    while x:        ans += tree[x]        x -= lowbit(x)    return ansn = int(input())a = [0] + list(map(int,input().split()))tree = [0]*(n+1)q = int(input())for i in range(q):    op,l,r = map(int,input().split())    if op == 1:        add(l,r)    else:        print(query(l)-query(r-1))

3.树的直径

import osimport sys# 请在此输入您的代码n = int(input())G = [[] for i in range(n + 1)]for _ in range(n - 1):    p, q, d = map(int, input().split())    G[p].append((q, d))    G[q].append((p, d))# d数组表示每个点的深度d = [0] * (n + 1)def dfs(u, fa):    global S    if d[u] > 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] = 0dfs(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,y = y,x    #利用倍增方法    #p[x][i] 表示从x节点向上走2^i步    for i in range(20,-1,-1):        if deep[p[x][i]] >= 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  PriorityQueueINF = 1e18def 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 = 1e18n,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] = 0for 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 = 1e9d = [INF]*(n+1)d[1] = 0for 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 dequedef 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 gcdfrom 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 = 12num2 = 18result = gcd(num1, num2)print(f"最大公约数为: {result}")#2.同余 暴力res = 1n = 10000mod = 10007for i in range(1,n+1):    res = (res *i) %modprint(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 False    for i in range(2, int(n**0.5) + 1):        if n % i == 0:            return False    return True#快速幂#递归def ksm(a, b):    """快速幂算法，计算 a 的 b 次幂"""    if b == 0:        return 1    # 递归计算 a^(b//2)    ans = ksm(a, b//2)        # 将结果平方    ans = ans * ans        # 如果 b 是奇数，则再乘以一个 a    if b % 2 == 1:        ans = ans * a    return ans#递推 两种算法效率相同 ***二进制拆分def ksm(a,b,mod):    res = 1    while b:        if b&1:            res = (res*a)%mod        a = a*a        b >> 1    return res

本文链接：https://www.kjpai.cn/news/2024-04-19/160208.html，文章来源：网络cs，作者：亙句，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！