目录
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 passl,r = #初始化，一般最边界ans = #初始化while l <= r: mid = (l+r)//2 if check(mid): ans = mid l = mid + 1#二选一，视题目以及自己定义条件 else: r = mid - 12.浮点数二分（考不到）
def check(): passl,r = #初始化eps = 1e-4while r - l >= eps: mid = (l+r)/2 if check(mid): r = mid#二选一 else: l = mid2.前缀和、差分
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 sumdef 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] += cN = 1010def 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] += cn, 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结尾的最长上升子序列#并且初始为1dp = [0] + [1]*nfor 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结尾的最长上升子序列#并且初始为1dp = [[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 dequedef bfs(): result = [] queue = deque() queue.append(root) while queue: u = queue.popleft() result.append(u) for v in G[u]: queue.append(v) return result6.数据结构
1.并查集
import osimport 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 == rootyN,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 ansn = 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 osimport 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] = 0dfs(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 PriorityQueueINF = 1e18def 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 = 1e18n,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] = 0for 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 = 1e9d = [INF]*(n+1)d[1] = 0for 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 dequedef 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 gcdfrom 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 = 12num2 = 18result = gcd(num1, num2)print(f"最大公约数为: {result}")#2.同余 暴力res = 1n = 10000mod = 10007for i in range(1,n+1): res = (res *i) %modprint(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