self-studying-online

 埃式筛 import math def sieve_of_eratosthenes ( n ): is_prime = [ True ] * ( n + 1 ) p = 2 while p * p <= n : if is_prime[p] == True : for i in range (p * p, n + 1 , p): is_prime[i] = False p += 1 prime_numbers = [p for p in range ( 2 , n + 1 ) if is_prime[p]] return prime_numbers def lcm_using_log ( n ): primes = sieve_of_eratosthenes ( n ) lcm = 1 for p in primes: max_power = math. floor (math. log ( n ) / math. log (p)) lcm *= p ** max_power return lcm 1到n的LCM求法： 为 累乘 P ** （log(n) / log(p)）（向下取整） 欧拉筛

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))