Python常用算法模板（蓝桥杯）

写在前面

一些可以直接调用的板子我都在下面给出，主要适用于蓝桥杯的Python选手。一些没有固定模板的写法在本文中不列出，如有紧张知识点遗漏，欢迎大家指出。

Python常用算法模板

快读

1. import sys
2. input = sys.stdin.readline

复制代码

影象化

1. from functools import lru_cache
2. @lru_cache(maxsize=None)
3. def dfs(a, b):
4.         pass

复制代码

开递归深度

1. import sys
2. sys.setrecursionlimit(10**5)

复制代码

日期问题

常用库函数：

1. from datetime import datetime # 日期时间
2. from datetime import date # 日期
3. from datetime import time # 时间
4. from datetime import timedelta # 时间间隔

复制代码

有关日期天数的加减：

1. d = datetime(2024, 4, 7) # 设置时间为2024年4月7日
2. delta = timedelta(days=1) # 时间间隔为1天
3. d_new = d + delta # d_new为2024年4月8日

复制代码

获取日期的年代日：

1. d = datetime(2024, 4, 7) # 设置时间为2024年4月7日
2. year = d.year() # 获取年
3. month = d.month() # 获取月
4. day = d.day() # 获取天

复制代码

进制转换

十进制转成其他进制：

1. # 十进制转二进制
2. bin(3) # 0b11
3. # 十进制转八进制
4. oct(8) # 0o10
5. # 十进制转十六进制
6. hex(255) # 0xff

复制代码

其他进制转十进制：

1. # 二进制转十进制
2. print(int('11', 2)) # 3
3. # 八进制转十进制
4. print(int('10', 8)) # 8
5. # 十六进制转十进制
6. print(int('ff', 16)) # 255

复制代码

前缀和模板

一维前缀和：

1. a = [0, 1, 2, 3, 4, 5, 6, 7]
2. prex = [a[0]]
3. for i in range(1, len(a)):
4.     prex.append(prex[-1] + a[i])
5. print(prex) # [0, 1, 3, 6, 10, 15, 21, 28]

复制代码

二维前缀和：

1. n = 3 # 3*3的矩阵
2. a = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
3. prex = [[0] * (n + 1) for _ in range(n + 1)]
4. for i in range(1, n+1):
5.     for j in range(1, n+1):
6.         prex[i][j] = prex[i][j-1] + prex[i-1][j] - prex[i-1][j-1] + a[i][j]
8. print(prex)

复制代码

差分模板

一维差分：

1. a = [0] + [1, 3, 2, 5, 5, 6, 7, 9]
2. diff = [0]
3. for i in range(1, len(a)):
4.     diff.append(a[i] - a[i-1])
5. print(diff) # [0, 1, 2, -1, 3, 0, 1, 1, 2]

复制代码

二维差分：

1. n = 3 # 3*3的矩阵
2. a = [[0, 0, 0, 0], [0, 1, 2, 3], [0, 4, 5, 6], [0, 7, 8, 9]]
3. diff = [[0] * (n+1) for _ in range(n+1)]
4. for i in range(1, n+1):
5.     for j in range(1, n+1):
6.         diff[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]
8. print(diff) # [[0, 0, 0, 0], [0, 1, 1, 1], [0, 3, 0, 0], [0, 3, 0, 0]]

复制代码

在(x1,y1)到(x2,y2)的区间均加d

1. diff[x1][y1] += d
2. diff[x2+1][y2+1] += d
3. diff[x1][y2+1] -= d
4. diff[x2+1][y1] -= d

复制代码

离散化

1. from bisect import bisect_left
2. a = [1000, 2000, 900000, 3000, 4000]
3. def discrete(li):
4.     tmp = sorted(set(a))
5.     new_li = []
6.     for i in range(len(a)):
7.         new_li.append(bisect_left(tmp, a[i]) + 1)
8.     return new_li
10. print(discrete(a)) # [1, 2, 5, 3, 4]

复制代码

二分模板

1. a = [1, 2, 3, 5, 5, 5, 6, 7, 9, 10]
3. def bin_search_right(li, x):
4.     l, r = -1, len(li)
5.     while l + 1 != r:
6.         mid = (l + r) // 2
7.         if li[mid] <= x: l = mid
8.         else: r = mid
9.     return l
11. # 找数组中最右边的值
12. print(bin_search_right(a, 5)) # 5

复制代码

1. a = [1, 2, 3, 5, 5, 5, 6, 7, 9, 10]
3. def bin_search_right(li, x):
4.     l, r = -1, len(li)
5.     while l + 1 != r:
6.         mid = (l + r) // 2
7.         if li[mid] >= x: r = mid
8.         else: l = mid
9.     return r
11. # 找数组中最左边的值
12. print(bin_search_right(a, 5)) # 3

复制代码

埃氏筛模板

1. def get_prime():
2.     N = 100010
3.     flag = [0] * N
4.     for i in range(2, N):
5.         if flag[i] == 0:
6.             for j in range(i+i, N, i):
7.                 flag[j] = 1
8.     prime = []
9.     for i in range(2, N):
10.         if flag[i] == 0: prime.append(i)
11.     return prime
13. print(get_prime())

复制代码

快速幂模板

1. mod = 10**9+7 # 带mod的pow有快速幂功能
2. print(pow(2, 10, mod)) # 1024

复制代码

1. def ksm(x, a): # return x**a
2.     res = 1
3.     while a:
4.         if a&1:
5.             res *= x
6.         a >>= 1
7.         x *= x
8.     return res
10. print(ksm(2, 10)) # 1024

复制代码

KMP算法

1. N = 1000005
2. Next = [0] * N
3. def getNext(p): # 求前缀数组
4.     for i in range(1, len(p)):
5.         j = Next[i]
6.         while j > 0 and p[i] != p[j]:
7.             j = Next[j]
8.         if p[i] == p[j]: Next[i + 1] = j + 1
9.         else: Next[i] = 0
11. def kmp(s, p): # KMP
12.     j = 0
13.     ans = 0
14.     for i in range(0, len(s)):
15.         while j > 0 and s[i] != p[j]:
16.             j = Next[j]
17.         if s[i] == p[j]:
18.             j += 1
19.             ans = max(ans, j)
20.         if j == len(p): return ans
21.     return ans
23. s = input()
24. p = input()
25. getNext(p)
26. print(kmp(s, p))

复制代码

字符串hash

1. n, m = map(int, input().split())
2. a = [0] + list(input())
3. p = 131 # 固定写法防止出现歧义
4. mod = 10**9 + 7
5. h = [0] * (n + 1)
6. for i in range(1, n + 1):
7.     h[i] = (h[i-1] * p + ord(a[i])) % mod
9. def query(l, r):
10.     return (h[r] - h[l-1] * pow(p, (r-l+1), mod)) % mod
12. for _ in range(m):
13.     l1, r1, l2, r2 = map(int, input().split())
14.     if  query(l1, r1) == query(l2, r2):
15.         print('Yes')
16.     else: print('No')

复制代码

矩阵乘法

1. def mutiply(A, B):
2.     n, m = len(A), len(A[0]) # n行m列
3.     _m, k = len(B), len(B[0]) # m行k列
4.     C = [[0] * (k) for i in range(n)]
5.     for i in range(n):
6.         for j in range(k):
7.             for d in range(m):
8.                 C[i][j] += (A[i][d] * B[d][j]) % mod
9.     return C # n行k列

复制代码

gcd与lcm

1. from math import gcd
2. def lcm(a, b):
3.     return a * b // gcd(a, b)
4. print(gcd(4, 16)) # 4
5. print(lcm(4, 16)) # 16

复制代码

唯一分解定理

一个大于1的数N要么为质数，要么可以分解为有限个质数的乘积。

1. def f(n):
2.     factor = []
3.     for i in range(2, n+1):
4.         while n % i == 0:
5.             n //= i
6.             factor.append(i)
7.         if n == 1:
8.             break
9.     return factor
11. print(f(16))

复制代码

结论：因子个数为其每个分解的质数的出现次数+1再相乘
求逆元

1. mod = 10**9 + 7 # mod必须为奇数
2. def inv(x):
3.     return pow(x, mod-2, mod)

复制代码

裴蜀定理

a, b为不全为0的整数，则存在x, y满足：ax + by = gcd(a, b)
并查集

1. def find(x):
2.     if x == p[x]: return x
3.     p[x] = find(p[x]) # 压缩路径
4.     return p[x]
5.    
6. def merge(x, y):
7.     xRoot = find(x)
8.     yRoot = find(y)
9.     p[xRoot] = yRoot
11. def query(x, y):
12.     return find(x) == find(y)

复制代码

树状数组

1. N = 10**9
2. tree = [0] * (N)
3. def lowbit(x):
4.     return x & (-x)
6. def update(x, d):
7.     while x <= N:
8.         tree[x] += d
9.         x += lowbit(x)
10.         
11. def query(x):
12.     ans = 0
13.     while x:
14.         ans += tree[x]
15.         x -= lowbit(x)
16.     return ans

复制代码

Floyd算法

1. n, m = map(int, input().split())
2. dp = [[0x3f3f3f3f] * (n + 1) for _ in range(n + 1)]
3. for _ in range(m):
4.     x, y, z = map(int, input().split())
5.     dp[x][y] = dp[y][x] = min(dp[x][y], z)
7. for k in range(1, n + 1):
8.     for i in range(1, n + 1):
9.         for j in range(1, n + 1):
10.             dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

复制代码

Dijkstra算法

1. from queue import PriorityQueue
2. import sys
3. sys.input = sys.stdin.readline
4. n, m = map(int, input().split())
5. inf = 1<<64
6. g = [[] for _ in range(n + 1)]
7. for _ in range(m):
8.     u, v, w = map(int, input().split())
9.     g[u].append([v, w])
10.    
11. def dijkstra(s):
12.     global r
13.     pq = PriorityQueue() # pq[0]表示下一个要走的最优路
14.     vis = [0] * (n + 1) # 表示某点是否被标记为最优
15.     r = [inf] * (n + 1) # 存的是起点到i的最短路
16.     r[s] = 0 # 起点到起点的距离为0
17.     pq.put([r[s], s]) # 把起点放入优先队列
18.     while pq.qsize() > 0:
19.         now = pq.get()
20.         if vis[now[1]]: continue
21.         vis[now[1]] = 1
22.         for i in g[now[1]]:
23.             v, w = i[0], i[1]
24.             if vis[v]: continue
25.             r[v] = min(r[v], r[now[1]] + w)
26.             pq.put([r[v], v])
28. dijkstra(1)
29. for i in range(1, n + 1):
30.     if r[i] >= inf: print(-1, end = ' ')
31.     else: print(r[i], end = ' ')

复制代码

线段树

单点修改、区间查询

1. def build(id, l, r):
2.     if l == r:
3.         tree[id] = a[l]
4.         return
5.     mid = (l + r) // 2
6.     build(id * 2, l, mid)
7.     build(id * 2 + 1, mid + 1, r)
8.     tree[id] = tree[id * 2] + tree[id * 2 + 1]
9.    
10. def update(pos, v, id, l, r):
11.     if l == r:
12.         tree[id] += v
13.         return
14.     mid = (l + r) // 2
15.     if pos <= mid: update(pos, v, id * 2, l, mid)
16.     else: update(pos, v, id * 2 + 1, mid + 1, r)
17.     tree[id] = tree[id * 2] + tree[id * 2 + 1]
19. def query(L, R, id, l, r):
20.     if L > r or R < l: return 0
21.     if L <= l and r <= R: return tree[id]
22.     mid = (l + r) // 2
23.     return query(L, R, id * 2, l, mid) + query(L, R, id * 2 + 1, mid + 1, r)
24.    
25. n = int(input())
26. a = [0] + list(map(int, input().split()))
27. tree = [0] * (4 * n)
28. build(1, 1, n)
29. for _ in range(int(input())):
30.     op, x, y = map(int, input().split())
31.     if op == 1:
32.         update(x, y, 1, 1, n)
33.     else:
34.         print(query(x, y, 1, 1, n))

复制代码

区间修改、区间查询

1. def build(id, l, r):
2.     if l == r:
3.         tree[id] = a[l]
4.         return
5.     mid = (l + r) // 2
6.     build(id * 2, l, mid)
7.     build(id * 2 + 1, mid + 1, r)
8.     tree[id] = tree[id * 2] + tree[id * 2 + 1]
9.    
10. def to_down(id, sl, sr):
11.     tag[id * 2] += tag[id]
12.     tag[id * 2 + 1] += tag[id]
13.     tree[id * 2] += tag[id] * sl
14.     tree[id * 2 + 1] += tag[id] * sr
15.     tag[id] = 0
16.    
17. def update(L, R, v, id, l, r):
18.     if R < l or L > r: return
19.     if L <= l and r <= R:
20.         tag[id] += v
21.         tree[id] += v * (r - l + 1)
22.         return
23.     mid = (l + r) // 2
24.     to_down(id, mid - l + 1, r - mid)
25.     update(L, R, v, id * 2, l, mid)
26.     update(L, R, v, id * 2 + 1, mid + 1, r)
27.     tree[id] = tree[id * 2] + tree[id * 2 + 1]
28.    
29. def query(L, R, id, l, r):
30.     if R < l or L > r: return 0
31.     if L <= l and r <= R: return tree[id]
32.     mid = (l + r) // 2
33.     to_down(id, mid - l + 1, r - mid)
34.     return query(L, R, id * 2, l, mid) + query(L, R, id * 2 + 1, mid + 1, r)
35.         
36. n, q = map(int, input().split())
37. a = [0] + list(map(int, input().split()))
38. tag = [0] * (n<<2)
39. tree = [0] * (n << 2)
40. build(1, 1, n)  # 建树
41. for i in range(q):
42.     op = list(map(int, input().split()))
43.     if op[0] == 1:
44.         x, y, z = op[1:]
45.         update(x, y, z, 1, 1, n)
46.     else:
47.         x, y = op[1:]
48.         print(query(x, y, 1, 1, n))

复制代码

区间最大值

1. def bulid(id, l, r):
2.     if l == r:
3.         tree[id] = a[l]
4.         return
5.     mid = (l + r) // 2
6.     bulid(id * 2, l, mid)
7.     bulid(id * 2 + 1, mid + 1, r)
8.     tree[id] = max(tree[id * 2], tree[id * 2 + 1])
9.    
10. def query(L, R, id, l, r):
11.     if R < l or L > r: return -0x3f3f3f3f
12.     if L <= l and r <= R: return tree[id]
13.     mid = (l + r) // 2
14.     return max(query(L, R, id * 2, l, mid), query(L, R, id * 2 + 1, mid + 1, r))
16. n, q = map(int, input().split())
17. a = [0] + list(map(int, input().split()))
18. tree = [0] * (n<<2)
19. bulid(1, 1, n)
20. for _ in range(q):
21.     x, y = map(int, input().split())
22.     print(query(x, y, 1, 1, n))

复制代码

LCA最近公共祖先

1. import sys
2. sys.setrecursionlimit(10000)
3. input = sys.stdin.readline
5. def dfs(u, fa):
6.   # 预处理
7.   deep[u] = deep[fa] + 1
8.   p[u][0] = fa
9.   for i in range(1, 21):
10.     p[u][i] = p[p[u][i - 1]][i - 1]
11.   for v in G[u]:
12.     if v == fa: continue
13.     dfs(v, u)
15. def lca(x, y):
16.   if deep[x] < deep[y]:
17.     x, y = y, x
18.   for i in range(20, -1, -1):
19.     if deep[p[x][i]] >= deep[y]:
20.       x = p[x][i]
22.   if x == y:
23.     return x
24.   for i in range(20, -1, -1):
25.     if p[x][i] != p[y][i]:
26.       x, y = p[x][i], p[y][i]
27.   return p[x][0]
29. n = int(input())
30. G = [[] for i in range(n + 1)]
31. deep = [0] * (n + 1) # deep[u]表示节点u的深度
32. p = [[0] * 21 for i in range(n + 1)] # p[u][i]表示节点u往上走2^i到达的节点
34. for _ in range(n - 1):
35.   u, v = map(int, input().split())
36.   G[u].append(v)
37.   G[v].append(u)
39. dfs(1, 0)
40. Q = int(input())
41. for _ in range(Q):
42.   x, y = map(int, input().split())
43.   print(lca(x, y))

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。