Python常用算法模板（蓝桥杯）
写在前面一些可以直接调用的板子我都在下面给出，主要适用于蓝桥杯的Python选手。一些没有固定模板的写法在本文中不列出，如有紧张知识点遗漏，欢迎大家指出。
https://i-blog.csdnimg.cn/blog_migrate/f7a70fbfa93cd7097d95bcb3f6e60a55.png
Python常用算法模板
快读
import sys
input = sys.stdin.readline
影象化
from functools import lru_cache
@lru_cache(maxsize=None)
def dfs(a, b):
pass
开递归深度
import sys
sys.setrecursionlimit(10**5)
日期问题
常用库函数：
from datetime import datetime # 日期时间
from datetime import date # 日期
from datetime import time # 时间
from datetime import timedelta # 时间间隔
有关日期天数的加减：
d = datetime(2024, 4, 7) # 设置时间为2024年4月7日
delta = timedelta(days=1) # 时间间隔为1天
d_new = d + delta # d_new为2024年4月8日
获取日期的年代日：
d = datetime(2024, 4, 7) # 设置时间为2024年4月7日
year = d.year() # 获取年
month = d.month() # 获取月
day = d.day() # 获取天
进制转换
十进制转成其他进制：
# 十进制转二进制
bin(3) # 0b11
# 十进制转八进制
oct(8) # 0o10
# 十进制转十六进制
hex(255) # 0xff
其他进制转十进制：
# 二进制转十进制
print(int('11', 2)) # 3
# 八进制转十进制
print(int('10', 8)) # 8
# 十六进制转十进制
print(int('ff', 16)) # 255
前缀和模板
一维前缀和：
a =
prex = ]
for i in range(1, len(a)):
prex.append(prex[-1] + a)
print(prex) #
二维前缀和：
n = 3 # 3*3的矩阵
a = [, , ]
prex = [ * (n + 1) for _ in range(n + 1)]
for i in range(1, n+1):
for j in range(1, n+1):
prex = prex + prex - prex + a
print(prex)
差分模板
一维差分：
a = +
diff =
for i in range(1, len(a)):
diff.append(a - a)
print(diff) #
二维差分：
n = 3 # 3*3的矩阵
a = [, , , ]
diff = [ * (n+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, n+1):
diff = a - a - a + a
print(diff) # [, , , ]
在(x1,y1)到(x2,y2)的区间均加d
diff += d
diff += d
diff -= d
diff -= d
离散化
from bisect import bisect_left
a =
def discrete(li):
tmp = sorted(set(a))
new_li = []
for i in range(len(a)):
new_li.append(bisect_left(tmp, a) + 1)
return new_li
print(discrete(a)) #
二分模板
a =
def bin_search_right(li, x):
l, r = -1, len(li)
while l + 1 != r:
mid = (l + r) // 2
if li <= x: l = mid
else: r = mid
return l
# 找数组中最右边的值
print(bin_search_right(a, 5)) # 5
a =
def bin_search_right(li, x):
l, r = -1, len(li)
while l + 1 != r:
mid = (l + r) // 2
if li >= x: r = mid
else: l = mid
return r
# 找数组中最左边的值
print(bin_search_right(a, 5)) # 3
埃氏筛模板
def get_prime():
N = 100010
flag = * N
for i in range(2, N):
if flag == 0:
for j in range(i+i, N, i):
flag = 1
prime = []
for i in range(2, N):
if flag == 0: prime.append(i)
return prime
print(get_prime())
快速幂模板
mod = 10**9+7 # 带mod的pow有快速幂功能
print(pow(2, 10, mod)) # 1024
def ksm(x, a): # return x**a
res = 1
while a:
if a&1:
res *= x
a >>= 1
x *= x
return res
print(ksm(2, 10)) # 1024
KMP算法
N = 1000005
Next = * N
def getNext(p): # 求前缀数组
for i in range(1, len(p)):
j = Next
while j > 0 and p != p:
j = Next
if p == p: Next = j + 1
else: Next = 0
def kmp(s, p): # KMP
j = 0
ans = 0
for i in range(0, len(s)):
while j > 0 and s != p:
j = Next
if s == p:
j += 1
ans = max(ans, j)
if j == len(p): return ans
return ans
s = input()
p = input()
getNext(p)
print(kmp(s, p))
字符串hash
n, m = map(int, input().split())
a = + list(input())
p = 131 # 固定写法防止出现歧义
mod = 10**9 + 7
h = * (n + 1)
for i in range(1, n + 1):
h = (h * p + ord(a)) % mod
def query(l, r):
return (h - h * pow(p, (r-l+1), mod)) % mod
for _ in range(m):
l1, r1, l2, r2 = map(int, input().split())
ifquery(l1, r1) == query(l2, r2):
print('Yes')
else: print('No')
矩阵乘法
def mutiply(A, B):
n, m = len(A), len(A) # n行m列
_m, k = len(B), len(B) # m行k列
C = [ * (k) for i in range(n)]
for i in range(n):
for j in range(k):
for d in range(m):
C += (A * B) % mod
return C # n行k列
gcd与lcm
from math import gcd
def lcm(a, b):
return a * b // gcd(a, b)
print(gcd(4, 16)) # 4
print(lcm(4, 16)) # 16
唯一分解定理
一个大于1的数N要么为质数，要么可以分解为有限个质数的乘积。
def f(n):
factor = []
for i in range(2, n+1):
while n % i == 0:
n //= i
factor.append(i)
if n == 1:
break
return factor
print(f(16))
结论：因子个数为其每个分解的质数的出现次数+1再相乘
求逆元
mod = 10**9 + 7 # mod必须为奇数
def inv(x):
return pow(x, mod-2, mod)
裴蜀定理
a, b为不全为0的整数，则存在x, y满足：ax + by = gcd(a, b)
并查集
def find(x):
if x == p: return x
p = find(p) # 压缩路径
return p
def merge(x, y):
xRoot = find(x)
yRoot = find(y)
p = yRoot
def query(x, y):
return find(x) == find(y)
树状数组
N = 10**9
tree = * (N)
def lowbit(x):
return x & (-x)
def update(x, d):
while x <= N:
tree += d
x += lowbit(x)
def query(x):
ans = 0
while x:
ans += tree
x -= lowbit(x)
return ans
Floyd算法
n, m = map(int, input().split())
dp = [ * (n + 1) for _ in range(n + 1)]
for _ in range(m):
x, y, z = map(int, input().split())
dp = dp = min(dp, z)
for k in range(1, n + 1):
for i in range(1, n + 1):
for j in range(1, n + 1):
dp = min(dp, dp + dp)
Dijkstra算法
from queue import PriorityQueue
import sys
sys.input = sys.stdin.readline
n, m = map(int, input().split())
inf = 1<<64
g = [[] for _ in range(n + 1)]
for _ in range(m):
u, v, w = map(int, input().split())
g.append()
def dijkstra(s):
global r
pq = PriorityQueue() # pq表示下一个要走的最优路
vis = * (n + 1) # 表示某点是否被标记为最优
r = * (n + 1) # 存的是起点到i的最短路
r = 0 # 起点到起点的距离为0
pq.put(, s]) # 把起点放入优先队列
while pq.qsize() > 0:
now = pq.get()
if vis]: continue
vis] = 1
for i in g]:
v, w = i, i
if vis: continue
r = min(r, r] + w)
pq.put(, v])
dijkstra(1)
for i in range(1, n + 1):
if r >= inf: print(-1, end = ' ')
else: print(r, end = ' ')
线段树
单点修改、区间查询
def build(id, l, r):
if l == r:
tree = a
return
mid = (l + r) // 2
build(id * 2, l, mid)
build(id * 2 + 1, mid + 1, r)
tree = tree + tree
def update(pos, v, id, l, r):
if l == r:
tree += v
return
mid = (l + r) // 2
if pos <= mid: update(pos, v, id * 2, l, mid)
else: update(pos, v, id * 2 + 1, mid + 1, r)
tree = tree + tree
def query(L, R, id, l, r):
if L > r or R < l: return 0
if L <= l and r <= R: return tree
mid = (l + r) // 2
return query(L, R, id * 2, l, mid) + query(L, R, id * 2 + 1, mid + 1, r)
n = int(input())
a = + list(map(int, input().split()))
tree = * (4 * n)
build(1, 1, n)
for _ in range(int(input())):
op, x, y = map(int, input().split())
if op == 1:
update(x, y, 1, 1, n)
else:
print(query(x, y, 1, 1, n))
区间修改、区间查询
def build(id, l, r):
if l == r:
tree = a
return
mid = (l + r) // 2
build(id * 2, l, mid)
build(id * 2 + 1, mid + 1, r)
tree = tree + tree
def to_down(id, sl, sr):
tag += tag
tag += tag
tree += tag * sl
tree += tag * sr
tag = 0
def update(L, R, v, id, l, r):
if R < l or L > r: return
if L <= l and r <= R:
tag += v
tree += v * (r - l + 1)
return
mid = (l + r) // 2
to_down(id, mid - l + 1, r - mid)
update(L, R, v, id * 2, l, mid)
update(L, R, v, id * 2 + 1, mid + 1, r)
tree = tree + tree
def query(L, R, id, l, r):
if R < l or L > r: return 0
if L <= l and r <= R: return tree
mid = (l + r) // 2
to_down(id, mid - l + 1, r - mid)
return query(L, R, id * 2, l, mid) + query(L, R, id * 2 + 1, mid + 1, r)
n, q = map(int, input().split())
a = + list(map(int, input().split()))
tag = * (n<<2)
tree = * (n << 2)
build(1, 1, n)# 建树
for i in range(q):
op = list(map(int, input().split()))
if op == 1:
x, y, z = op
update(x, y, z, 1, 1, n)
else:
x, y = op
print(query(x, y, 1, 1, n))
区间最大值
def bulid(id, l, r):
if l == r:
tree = a
return
mid = (l + r) // 2
bulid(id * 2, l, mid)
bulid(id * 2 + 1, mid + 1, r)
tree = max(tree, tree)
def query(L, R, id, l, r):
if R < l or L > r: return -0x3f3f3f3f
if L <= l and r <= R: return tree
mid = (l + r) // 2
return max(query(L, R, id * 2, l, mid), query(L, R, id * 2 + 1, mid + 1, r))
n, q = map(int, input().split())
a = + list(map(int, input().split()))
tree = * (n<<2)
bulid(1, 1, n)
for _ in range(q):
x, y = map(int, input().split())
print(query(x, y, 1, 1, n))
LCA最近公共祖先
import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
def dfs(u, fa):
# 预处理
deep = deep + 1
p = fa
for i in range(1, 21):
p = p]
for v in G:
if v == fa: continue
dfs(v, u)
def lca(x, y):
if deep < deep:
x, y = y, x
for i in range(20, -1, -1):
if deep] >= deep:
x = p
if x == y:
return x
for i in range(20, -1, -1):
if p != p:
x, y = p, p
return p
n = int(input())
G = [[] for i in range(n + 1)]
deep = * (n + 1) # deep表示节点u的深度
p = [ * 21 for i in range(n + 1)] # p表示节点u往上走2^i到达的节点
for _ in range(n - 1):
u, v = map(int, input().split())
G.append(v)
G.append(u)
dfs(1, 0)
Q = int(input())
for _ in range(Q):
x, y = map(int, input().split())
print(lca(x, y))
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]