蓝桥杯常见算法模板（Python组）_蓝桥杯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 <= r:
    mid = (l+r)//2
    if check(mid):
        ans = mid
        l = mid + 1#二选一，视题目以及自己定义条件
        
    else:
        r = mid - 1

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

def check():
    pass
 
l,r = #初始化
 
eps = 1e-4
while 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 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 < 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 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 <= n:
        tree[x] += y
        x += lowbit(x)
 
#ans += 走过的点 知道走到最右
def query(x):
    ans = 0
    while x:
        ans += tree[x]
        x -= lowbit(x)
    return ans
 
n = 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 os
import 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] = 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,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  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 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