算法笔记

Acwing算法学习 [TOC] 第一章 课上：学思想 课下：背代码 题目，一道题写好几遍 理解没有任何意义，体力活+脑力活 记忆力 毅力/自制力 沉下心背东西 快速排序算法模板 —— 模板题 AcWing 785. 快速排序 分治 ...

算法笔记（二）——数据结构(Python实现) 数据结构 单链表 N = int(1e5+10) e=[0]*N ne=[0]*N head=-1 idx=1 def insert(x): global idx, head e[idx]=x ne[idx]=head head=idx idx+=1 def add(k, x): global idx e[idx]=x ne[idx]=ne[k] ne[k]=idx idx+=1 def remove(k): global idx, head if k==0: head = ne[head] else: ne[k]=ne[ne[k]] n = int(input()) for _ in range(n): s = input().split() op=s[0] if op=='H': insert(int(s[1])) elif op=='I': add(int(s[1]), int(s[2])) else: remove(int(s[1])) i=head while i!=-1: print(e[i], end=' ') i=ne[i] 双链表 N = int(1e5+10) e=[0]*N l=[0]*N r=[0]*N idx=0 def init(): global idx r[2]=1 l[1]=2 idx=3 def insert(k, x): global idx e[idx]=x l[idx]=k r[idx]=r[k] l[r[k]]=idx r[k]=idx idx+=1 def remove(k): l[r[k]]=l[k] r[l[k]]=r[k] init() m=int(input()) for _ in range(m): s=input().split() if s[0]=='L': x=int(s[1]) insert(2,x) elif s[0]=='R': x=int(s[1]) insert(l[1],x) elif s[0]=='D': k=int(s[1])+2 remove(k) elif s[0]=='IL': k=int(s[1])+2 x=int(s[2]) insert(l[k],x) elif s[0]=='IR': k=int(s[1])+2 x=int(s[2]) insert(k,x) i=2 while i!=0: if i==2 or i==1: i=r[i] continue print(e[i],end=" ") i=r[i] 栈 N = int(1e5+10) # 假设N的值为100 stk = [0] * N tt = 0 # 向栈顶插入一个数 tt += 1 stk[tt] = x # 从栈顶弹出一个数 tt -= 1 # 栈顶的值 stk[tt] # 判断栈是否为空 if tt > 0: pass 队列 N = 100 # 假设N的值为100 q = [0] * N hh = 0 tt = -1 # 向队尾插入一个数 tt += 1 q[tt] = x # 从队头弹出一个数 hh += 1 # 队头的值 q[hh] # 判断队列是否为空 if hh <= tt: pass N = 100 # 假设N的值为100 q = [0] * N hh = 0 tt = 0 # 向队尾插入一个数 q[tt] = x tt += 1 if tt == N: tt = 0 # 从队头弹出一个数 hh += 1 if hh == N: hh = 0 # 队头的值 q[hh] # 判断队列是否为空 if hh != tt: pass 单调栈 tt = 0 stk = [0] * (n + 1) for i in range(1, n + 1): while tt and check(stk[tt], i): tt -= 1 stk[tt + 1] = i tt += 1 单调队列 n = 10 # 假设n的值为10 hh = 0 tt = -1 q = [0] * n for i in range(n): while hh <= tt and check_out(q[hh]): hh += 1 while hh <= tt and check(q[tt], i): tt -= 1 q[tt + 1] = i tt += 1 N = int(1e6+10) q=[0 for _ in range(N)] n,k=map(int, input().split()) a=[0]+[int(x) for x in input().split()] hh,tt=0,-1 for i in range(1,n+1): if hh<=tt and i-q[hh]+1>k: hh+=1 while hh<=tt and a[q[tt]] >= a[i]: tt-=1 tt+=1 q[tt]=i if i >= k: print(a[q[hh]], end=" ") print() hh,tt=0,-1 for i in range(1,n+1): if hh<=tt and i-q[hh]+1>k: hh+=1 while hh<=tt and a[q[tt]] <= a[i]: tt-=1 tt+=1 q[tt]=i if i>=k: print(a[q[hh]], end=" ") KMP m = len(p) # 假设p为模板串，长度为m n = len(s) # 假设s为模式串，长度为n ne = [0] * (m + 1) # 初始化ne数组 # 求Next数组 j = 0 for i in range(2, m + 1): while j and p[i] != p[j + 1]: j = ne[j] if p[i] == p[j + 1]: j += 1 ne[i] = j # 匹配 j = 0 for i in range(1, n + 1): while j and s[i] != p[j + 1]: j = ne[j] if s[i] == p[j + 1]: j += 1 if j == m: j = ne[j] # 匹配成功后的逻辑 n = int(input()) p = ' ' + input() m = int(input()) s = ' ' + input() ne = [0]*(n+1) j = 0 for i in range(2, n+1): while j and p[i]!=p[j+1]: j = ne[j] if p[i]==p[j+1]: j += 1 ne[i] = j j = 0 res = [] for i in range(1, m+1): while j and s[i]!=p[j+1]: j = ne[j] if s[i]==p[j+1]: j += 1 if j==n: res.append(i-j) j = ne[j] print(*res, sep=' ') Z函数 def z_function(s): n = len(s) z = [0] * n l, r = 0, 0 for i in range(1, n): if i <= r and z[i - l] < r - i + 1: z[i] = z[i - l] else: z[i] = max(0, r - i + 1) while i + z[i] < n and s[z[i]] == s[i + z[i]]: z[i] += 1 if i + z[i] - 1 > r: l = i r = i + z[i] - 1 return z Tire N = 100010 son = [[0] * 26 for _ in range(N)] cnt = [0] * N idx = 0 # 0号点既是根节点，又是空节点 # son[][]存储树中每个节点的子节点 # cnt[]存储以每个节点结尾的单词数量 # 插入一个字符串 def insert(s): global idx p = 0 for i in range(len(s)): u = ord(s[i]) - ord('a') if not son[p][u]: idx += 1 son[p][u] = idx p = son[p][u] cnt[p] += 1 # 查询字符串出现的次数 def query(s): p = 0 for i in range(len(s)): u = ord(s[i]) - ord('a') if not son[p][u]: return 0 p = son[p][u] return cnt[p] 马拉车（字符串回文串算法） class Solution: # 推荐教学视频 ：https://www.bilibili.com/video/BV1Sx4y1k7jG/?spm_id_from=333.337.search-card.all.click&vd_source=a4a2b56f746715b34521bfb853094cf4 def longestPalindrome(self, s: str) -> str: s = '#' + '#'.join(list(s)) + '#' n = len(s) p = [0]*n #每个点的 最长回文字串 能到的 两侧长度 c, r = 0, 0 # 右边能到达最远的蘑菇的位置 和 其最右边能达到的位置 for i in range(n): if i<=r: p[i] = min(r-i, p[c + c-i]) # 由已知条件得到当前位置能达到的最大右侧距离( 需要取min(镜像位置的值, 当前最大蘑菇能覆盖到的最大值) ) while i+p[i]+1 < n and s[i-p[i]-1] == s[i+p[i]+1]: p[i]+=1 if p[i]+i > r: r = p[i] + i c = i ma = max(p) idx = p.index(ma) return s[idx-ma+1:idx+ma+1:2] 并查集 N = 1000005 # 假设N的值为1000005 p = [0] * N # 初始化p数组 # 返回x的祖宗节点 def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] ''' 非递归写法 def find(x): while p[x]!=x: p[x] = p[p[x]] x = p[x] return x ''' # 初始化，假定节点编号是1~n for i in range(1, n + 1): p[i] = i # 合并a和b所在的两个集合 p[find(a)] = find(b) 维护size信息 ...

算法笔记（三）——图论（Python实现） 图论 树的存储 邻接矩阵 # 创建一个二维列表表示邻接矩阵 n = 10 # 顶点数量 g = [[0] * n for _ in range(n)] # 添加一条边a->b def add_edge(a, b): g[a][b] = 1 # 初始化 g = [[0] * n for _ in range(n)] 邻接表 # 创建一个列表表示邻接表 n = 10 # 顶点数量 h = [-1] * n e = [0] * n ne = [0] * n idx = 0 # 添加一条边a->b def add_edge(a, b): global idx e[idx] = b ne[idx] = h[a] h[a] = idx idx += 1 # 初始化 idx = 0 h = [-1] * n 树和图的存储 # 邻接表表示的图 N = 100010 # 根据具体需求设置合适的最大节点数量 # 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点 h = [-1] * N # 存储边的目标节点 e = [0] * N # 存储下一条边的索引 ne = [0] * N # 边的索引 idx = 0 # 添加一条边a->b def add(a, b): global idx e[idx] = b ne[idx] = h[a] h[a] = idx idx += 1 # 初始化 idx = 0 for i in range(N): h[i] = -1 树和图的遍历 DFS def dfs(u): st[u] = True i = h[u] while i!=-1: j = e[i] if not st[j]: dfs(j) i = ne[i] BFS from collections import deque q = deque() st[1] = True q.append(1) while q: t = q.popleft() i = h[t] while i!=-1: j=e[i] if not st[j]: st[j] = True q.append(j) i=ne[i] 拓扑排序 from sys import stdin from collections import deque input = lambda:stdin.readline().strip() def topsort(): q = deque() res = [] for i in range(1, n+1): if ind[i]==0: res.append(i) q.append(i) while q: u = q.popleft() for v in g[u]: ind[v] -= 1 if ind[v]==0: q.append(v) res.append(v) return res n = int(input()) ind = [0]*(n+1) g = [[] for _ in range(n+1)] for i in range(1, n+1): a = list(map(int, input().split())) for j in range(len(a)-1): g[i].append(a[j]) ind[a[j]]+=1 res = topsort() print(*res, sep=' ') 奖金 from sys import stdin from collections import deque def topsort(): res = [] q = deque() ans = 0 for i in range(1, n+1): if ind[i]==0: res.append(i) q.append((i, 100)) ans += 100 while q: u, m = q.popleft() for v in g[u]: ind[v] -= 1 if ind[v]==0: q.append((v, m+1)) res.append(v) ans += m+1 if len(res)==n: print(ans) else: print("Poor Xed") n, m = map(int, input().split()) ind = [0]*(n+1) g = [[] for _ in range(n+1)] for i in range(m): a, b = map(int, input().split()) ind[a] += 1 g[b].append(a) topsort() LCA def lca(x,y): if dep[x] < dep[y]: x,y = y,x d = dep[x]-dep[y] while d: # 循环直到深度差为 0 v = d & -d # 获取 d 的最低位的 1 所在的位置 i = v.bit_length() - 1 # 计算最低位的位置索引 x = fa[i][x] # 将节点 x 上移到和节点 y 同一深度 d -= v # 更新深度差 if x==y: return x for k in range(K-1, -1, -1): if fa[k][x] != fa[k][y]: x = fa[k][x] y = fa[k][y] return fa[0][x] # 初始化深度以及父节点信息 dep[x]=dep[val]+1 dep[y]=dep[val]+1 fa[0][x] = val fa[0][y] = val for k in range(K-1): fa[k+1][x] = fa[k][fa[k][x]] # 自己的第2^(1+1)级父亲即为 自己的第2^(1)级父亲 的第2^(1)级父亲 fa[k+1][y] = fa[k][fa[k][y]] 祖孙询问 from sys import stdin from collections import deque, defaultdict from math import inf K = 17 N = int(4*10e4) + 10 dep = [inf]*(N) fa = [[0]*N for _ in range(K)] def bfs(): dep[0] = 0; dep[root] = 1 q = deque([root]) while q: u = q.popleft() for v in g[u]: if dep[v] > dep[u] + 1: dep[v] = dep[u] + 1 q.append(v) fa[0][v] = u for k in range(1, K-1): fa[k][v] = fa[k-1][fa[k-1][v]] def lca(x, y): if dep[x] < dep[y]: x, y = y, x d = dep[x] - dep[y] while d: v = d & -d i = v.bit_length() - 1 x = fa[i][x] d -= v if x==y: return x for k in range(K-1, -1, -1): if fa[k][x] != fa[k][y]: x = fa[k][x] y = fa[k][y] return fa[0][x] n = int(input()) g = defaultdict(list) for i in range(n): a, b = map(int, input().split()) if b==-1: root = a else: g[a].append(b) g[b].append(a) bfs() # print(dep) m = int(input()) for i in range(m): x, y = map(int, input().split()) res = lca(x, y) if res == x and res != y: print(1) elif res == y and res != x: print(2) else: print(0) 最短路 单元最短路 ...

算法笔记（四）——数学（Python实现） 数学 试除法判定质数 def check(x): # 判定 if x<2: return False for i in range(2, int(x**0.5)+1): if x%i==0: return False return True n = int(input()) for i in range(n): x = int(input()) if check(x): print("Yes") else: print("No") 试除法分解质因数 def get(x): #分解 for i in range(2, int(x**0.5)+1): if x%i==0: cnt=0 while x%i==0: x//=i cnt+=1 print(i, cnt, sep=' ') if x>1: print(x, 1, sep=' ') n = int(input()) for i in range(n): x = int(input()) get(x) print() 线性筛法求素数 N = int(1e6+10) primes = [] st = [False]*N def get(n): for i in range(2, n+1): if not st[i]: primes.append(i) for j in range(len(primes)): if i*primes[j]>n: break st[i*primes[j]]=True if i%primes[j]==0: break n = int(input()) get(n) print(len(primes)) 朴素筛法求素数 N = 1000005 # 根据需要修改 primes = [] # 存储所有素数 st = [False] * N # st[x]存储x是否被筛掉 # 筛素数函数 def get_primes(n): global primes global st for i in range(2, n + 1): if not st[i]: primes.append(i) for j in range(i, n + 1, i): st[j] = True # Example usage: # get_primes(100) # print(primes) 试除法求所有约数 def get(x): res = [1] for i in range(2, int(x**0.5)+1): if x%i==0: res.append(i) if i!=x//i: res.append(x//i) if x>1: res.append(x) return sorted(res) n = int(input()) for i in range(n): x = int(input()) res = get(x) print(*res) 约数个数和约数之和 如果 N = p1^c1 * p2^c2 * ... *pk^ck 约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1) 约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck) 约数之和 题目大意：给定两个自然数 A 和 B，定义 S 为 A*B 的所有约数之和。求 S mod 9901 的值。 ...

算法笔记（五）——DP（Python实现） DP 数字三角形 f=[] n=int(input()) for _ in range(n): f.append([int(x) for x in input().split()]) for i in range(n-2,-1,-1): for j in range(i+1): f[i][j]=max(f[i+1][j], f[i+1][j+1])+f[i][j] print(f[0][0]) 背包 空间优化成1维之后，只有完全背包问题的体积是从小到大循环的 01背包 N = int(1e3+10) f=[ 0 for _ in range(N) ] n,v=map(int,input().split()) for i in range(n): vi,wi=map(int,input().split()) for j in range(v, vi-1,-1): f[j]=max(f[j],f[j-vi]+wi) print(f[v]) 多重背包 单调队列 MN = int(2e4+10) f=[0 for _ in range(MN)] q=[0 for _ in range(MN)] g=[0 for _ in range(MN)] N,V = map(int, input().split()) for i in range(N): v,w,s=map(int, input().split()) g=f[:] for j in range(v): hh,tt=0,-1 for k in range(j,V+1,v): while hh<=tt and q[hh]<k-s*v: hh+=1 while hh<=tt and g[q[tt]]+(k-q[tt])//v*w <= g[k]: tt-=1 tt+=1 q[tt]=k f[k]=g[q[hh]]+(k-q[hh])//v*w print(f[V]) 二维费用背包 N = int(1e2+10) f=[[0]*N for _ in range(N)] n,V,M = map(int , input().split()) 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): f[j][k]=max(f[j][k], f[j-v][k-m]+w) print(f[V][M]) 宠物小精灵 题目大意：小智在野外捕捉宠物小精灵，他带了一些精灵球和皮卡丘，精灵球可以捕捉小精灵，但每捕捉一个小精灵都会消耗精灵球和减少皮卡丘的体力。现在给定小智拥有的精灵球数量、皮卡丘的初始体力值以及每个小精灵需要的精灵球数量和对皮卡丘造成的伤害数目，问小智最多能捕捉多少个小精灵，并且在这种情况下，皮卡丘的剩余体力值最多是多少。 ...

算法笔记（一）——基础+杂项（Python实现） 基础+杂项 快速排序 def quick_sort(q, l, r): if l>=r: return i,j,x=l-1,r+1,q[(l+r)>>1] while i<j: i+=1 while q[i]<x: i+=1 j-=1 while q[j]>x: j-=1 if i<j: q[i], q[j] = q[j], q[i] quick_sort(q, l, j) quick_sort(q, j+1, r) n=int(input()) arr=list(map(int, input().split())) quick_sort(arr,0,n-1) print(" ".join(map(str, arr))) 随机选择pivot import random class Solution: def sortArray(self, nums: List[int]) -> List[int]: def quick_sort(q, l, r): if l >= r: return # 随机选择 pivot i, j = l, r rand_idx = random.randint(l, r) x = q[rand_idx] while i <= j: while q[i] < x: i += 1 while q[j] > x: j -= 1 if i <= j: q[i], q[j] = q[j], q[i] i += 1 j -= 1 quick_sort(q, l, j) quick_sort(q, i, r) quick_sort(nums, 0, len(nums) - 1) return nums 归并排序 j = mid+1 !!! ...