代码收藏家技术教程 21天前

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求解的问题，一般是求方案数，或者求最值。

***注意考虑边界***