self-studying-online

import heapq # 创建一个空的优先堆 priority_queue = [] # 插入元素到优先堆中 heapq. heappush (priority_queue, ( 2 , 'task 2' )) heapq. heappush (priority_queue, ( 1 , 'task 1' )) heapq. heappush (priority_queue, ( 3 , 'task 3' )) # 查看优先堆中的元素 print ( " 优先堆中的元素： " , priority_queue) # 删除并返回具有最高优先级的元素（即最小的元素） highest_priority_task = heapq. heappop (priority_queue) print ( " 具有最高优先级的任务： " , highest_priority_task) # 查看删除后优先堆中的元素 print ( " 删除后的优先堆中的元素： " , priority_queue)   heapq.heappush(heap, item) ：将 item 插入堆中。 heapq.heappop(heap) ：从堆中删除并返回最小的元素。 heapq.heapify(x) ：将列表 x 转换为堆。 heapq.heappushpop(heap, item) ：将 item 插入堆中，然后弹出并返回最小的元素。 heapq.heapreplace(heap, item) ：弹出并返回最小的元素，然后将 item 插入堆中。

from collections import defaultdict for _ in range ( int ( input ())): m, x = map ( int , input (). split ()) c = [ 0 ] * (m + 1 ) h = [ 0 ] * (m + 1 ) for i in range (m): c[i], h[i] = map ( int , input (). split ()) mh = sum (h) dp = [ 0 ] + [ float ( 'inf' )] * mh for i in range (m): for j in range (mh, h[i] - 1 , - 1 ): if i * x >= dp[j - h[i]] + c[i]: dp[j] = min (dp[j], dp[j - h[i]] + c[i]) for i in range (mh, - 1 , - 1 ): if dp[i] != float ( 'inf' ): print (i) break link： https://codeforces.com/contest/1974/problem/E """ 1. 背包容量 capacity, n 件物品 2.n 件物品的重量 w, 价值 v """ def knapsack_01 ( items , capacity ): n = len ( items ) # dp[i][j] 代表 前 i 个物品 j 容量时的价值 dp = [[ 0 ] * ( capacity + 1 ) for _ in range (n + 1 )] for i in range ( 1 , n + 1 ): weight, val = items [i - 1 ] for j in range ( capacit...

def LCS ( A , B ): n = len ( A ) m = len ( B ) #dp[i][j] 代表 A 的前 i 个字符 与 B 的前 j 个字符最长公共子序列长度 dp = [[ 0 ] * (m + 1 ) for _ in range (n + 1 )] for i in range ( 1 , n + 1 ): for j in range ( 1 , m + 1 ): if A [i - 1 ] == B [j - 1 ]: dp[i][j] = dp[i - 1 ][j - 1 ] + 1 else : dp[i][j] = max (dp[i - 1 ][j], dp[i][j - 1 ]) lcs_max_len = dp[n][m] lcs = [] i, j = n, m while i > 0 and j > 0 : if A [i - 1 ] == B [j - 1 ]: lcs. append ( A [i - 1 ]) j -= 1 i -= 1 elif dp[i - 1 ][j] > dp[i][j - 1 ]: i -= 1 else : j -= 1 lcs. reverse () return lcs_max_len, lcs A = input () B = input () lcs_len, lcs = LCS (A, B) print ( '' . join (lcs))  

 Kruskal MST 模板： class UnionFind: def __init__ ( self , n ): self .parent = list ( range ( n )) self .rank = [ 0 ] * n def find ( self , x ): if self .parent[ x ] != x : self .parent[ x ] = self . find ( self .parent[ x ]) return self .parent[ x ] def union ( self , x , y ): root_x = self . find ( x ) root_y = self . find ( y ) if root_x == root_y: return if self .rank[root_x] < self .rank[root_y]: self .parent[root_x] = root_y elif self .rank[root_x] > self .rank[root_y]: self .parent[root_y] = root_x else : self .parent[root_y] = root_x self .rank[root_x] += 1 def kruskal ( n , edges ): edges . sort ( key = lambda edge : edge[ 2 ]) uf = UnionFind ( n ) mst_w = 0 mst_edges= [] for u, v, w in edges : if uf. find (u) != uf. find (v): uf. union (u, v) mst_w += w ...

并查集模板 class UnionFind: def __init__ ( self , n ): self .parent = [i for i in range ( n )] self .rank = [ 0 ] * n def find ( self , x ): if self .parent[ x ] != x : self .parent[ x ] = self . find ( self .parent[ x ]) return self .parent[ x ] def union ( self , x , y ): root_x = self . find ( x ) root_y = self . find ( y ) if root_x == root_y: return if self .rank[root_x] < self .rank[root_y]: self .parent[root_x] = root_y elif self .rank[root_x] > self .rank[root_y]: self .parent[root_y] = root_x else : self .parent[root_y] = root_x self .rank[root_x] += 1 n, m = map ( int , input (). split ()) uf = UnionFind (n) for _ in range (m): z, x, y = map ( int , input (). split ()) x -= 1 y -= 1 if z == 1 : uf. union (x, y) else : if uf. find (x) != uf. find (y): print ( 'N...

 前缀和 c = [0]  *  11 a = list(map(int, input().split())) for i in range(1, 11):     c[i] = c[i - 1] + a[i - 1] print(c) 1 2 3 4 5 6 7 8 9 10 [0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55] python 中自带前缀和函数，在itertools中的accumulate，请转到该模块 ** Process exited - Return Code: 0 ** 差分 假设 数组a = [1, 2, 3, 4, 5]  对 数组a [1, 3]进行加 5 操作 设差分数组: D[0] = a[0] = 1 D[1] = a[1] - a[0] = 1 D[2] = a[2] - a[1] = 1 D[3] = a[3] - a[2] = 1 D[4] = a[4] - a[3] = 1 进行操作D[L] += 5 D[R + 1] -= 5  这里L, R = 1, 3 => D[1] = 6, D[4] = 1 - 5 = -4 a[0] = D[0] = 1 a[1] = D[1] + a[0] = 7 a[2] = a[1] + D[2] = 8 a[3] = a[2] + D[3] = 9 a[4] = a[3] + D[4] = 9 - 4 = 5 由此完成差分！