1 字符串 字符串匹配：kmp、mancher、z函数、滚动哈希 字典树 后缀数组 2 位运算 位运算 3 链表 链表 4 栈 计算器 5 块 块状数组 6 贪心 贪心 7 数学 数学

数位dp 1 2 3 4 5 6 7 8 9 10 11 @cache def dfs(i,st,bd): if i==len(s): return st res = 0 cur = int(s[i]) up = cur if bd else 9 for x in range(up+1): res += dfs(i+1,st+(x==1),bd and x==cur) return res s = str(n)

1 最大流 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 class Dinic: def __init__(self,): self.g = defaultdict(list) # g 是图中每个 u 对应的 v 列表 self.h =

二分图 最大匹配 1 2 3 4 5 6 7 8 9 10 11 12 13 14 def hgr(g): # g 是二分图中每个 x 对应的 y 列表 def find(x): for y in g[x]: if y not in vis: vis.add(y) if y not in d or find(d[y]): d[y]=x return True return False res,vis,d = 0,set(),{} for x in g:

博弈反推 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Q = deque(res) # res[u]：终态 u 的胜负结果 while Q: u = Q.popleft() if u==start: # start：初始态 return res[u] for v in nxt[u]: if v in res: continue if v[-1]==res[u]: res[v]

1 dijkstra 1 2 3 4 5 6 7 8 9 10 11 12 13 def dij(g,s): pq,d = [(0,s)], [inf]*n d[s] = 0 while pq: w,u = heappop(pq) if w>d[u]: continue for v,w2 in g[u]: nw = w+w2 if nw<d[v]: d[v] = nw heappush(pq, (nw,v)) return d 1 2 3 4 5 6 7 8 9 def dij(g,s): Q, d = set(range(n)), [inf]*n d[s] = 0 while Q: u

珂朵莉树 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class ODT: def __init__(self,): from sortedcontainers import SortedList self.sl = SortedList() def update(self,l,r,x): s, e = l, r pos = self.sl.bisect_right((r+2,))-1 while pos>=0 and self.sl[pos][1]>=l-1: a, b, y = self.sl.pop(pos) if y==x: s, e = min(s, a), max(e, b) else: if b>r: self.sl.add((r+1,b,y)) if a<l: self.sl.add((a,l-1,y)) pos

线段树 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 class Seg: def __init__(self, n, A=None): self.n = n self.t

1 区间和 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class BIT: def __init__(self, n): self.n = n+1 self.t = [0]*(n+1) def update(self, i, x): i += 1 while i<self.n: self.t[i] += x i += i&-i def get(self, i): res, i = 0, i+1 while i: res += self.t[i] i &= i-1 return res 2 区间最大

ST 表（静态区间最值） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 class ST: def __init__(self,A,func=max): dp = A[:] self.st = st = [dp] j, N = 1, len(dp) while 2*j<=N: dp = [func(dp[i],dp[i+j]) for i in range(N-2*j+1)] st.append(dp) j <<= 1 self.func = func def query(self,l,r): j = (r-l+1).bit_length()-1 return self.func(self.st[j][l],self.st[j][r-(1<<j)+1])