V=int(input()) n=int(input()) a=[] for _ in range(n): a.append(int(input())) # dp[j] 表示是否存在一个子集，使得体积和正好等于 s dp=[False]*(V+1) dp[0]=True for w in a:#每考虑一个物体，dp[j]都会被更新 if w>V: continue for j in range(V,w-1,-1):#对于j<=w的dp[j]肯定不需要更新 if dp[j-w]: #j是V,V-1,...,w 这样递减的，最后一步必然是j-w=0 dp[j]=True for k i...

#2.使用二分查找，动态构建一个辅助数组 res 来记录当前能够构成的上升子序列的“最小末尾元素” import sys from bisect import bisect_left n=int(sys.stdin.readline()) a=[int(x) for x in sys.stdin.readline().split()] res=[] for x in a: i=bisect_left(res,x)#返回的是 第一个不小于 x 的位置。如果 x 已经在数组中，它返回 x 第一个出现的位置 if i==len(res):#比res最后一个元素还大 res.append(x) els...

# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param triangle int整型二维数组 # @return int整型 # #1.线性dp class Solution: def minTrace(self , triangle: List[List[int]]) -> int: # write code here #逆向思维，自底向上 dp=triangle[-1] n=len(triangle) for i in range(n-2,-1,-1):#从倒数第二行开始 for j in range(len(triangle[i]...

import sys from collections import deque # 给定一组字符及其出现频率（或权重），哈夫曼编码为每个字符分配一串二进制码字。 # 高频字符分配较短的编码，低频字符分配较长的编码，保证无前缀（一个码字不是另一个码字的前缀）。 # 目标是使编码后所有字符加权平均长度最短，从而压缩数据。 def huffman_length(): n=int(sys.stdin.readline()) freqs=list(map(int,sys.stdin.readline().split())) if n<=2: return sum(freqs) freqs.sor...

# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # 将给定数组排序 # @param arr int整型一维数组 待排序的数组 # @return int整型一维数组 # class Solution: def MySort(self , arr: List[int]) -> List[int]: # write code here def quicksort(nums,left,right):#选取中间元素作为基准 if left>=right: return pivot=nums[(left+right)//2] i,j=left,righ...

import sys q=int(sys.stdin.readline()) # (m * n) mod p = ((m mod p) * (n mod p)) mod p # def fast_pow(a,b,p): #1.递归版本 # if b==1: # return a%p # elif b%2==0: # return (fast_pow(a,b//2,p)**2)%p # else: # return (a*fast_pow(a,b//2,p)**2)%p # def fast_pow(a,b,p): #2.位运算版本 # if b==0: # return 1 # half=fa...

# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param n int整型 # @return string字符串一维数组 # class Solution: def getSolution(self , n: int) -> List[str]: # write code here #(n,0,0) -> (0,0,n) # if n==1: # print('move from left to right') # elif n==2: # print('move from left to mid') # print('move f...

import sys def all_times(t): h0,h1,m0,m1=t[0],t[1],t[3],t[4] hh=[h for h in range(24) if (h0=='?' or h0==f'{h:02d}'[0]) and (h1=='?' or h1==f'{h:02d}'[1])] mm=[m for m in range(60) if (m0=='?' or m0==f'{m:02d}'[0]) and (m1=='?' or m1==f'{m:02d}'[1])] return [h*60+m for h in hh for m in mm] def solve...

n=int(input()) a=[int(i) for i in input().split()] from functools import lru_cache @lru_cache(None) def is_prime(x):#x>=2 if x<=3: return True if x%2==0: return False limit=int(x**0.5) #只试除奇数到sqrt(x) for num in range(3,limit+1,2): if x%num==0: return False return True used=set() min_sum=float(...

遍历二维数组，找到为 1 的之后，使用深度优先搜索将与其相邻的陆地全部淹没（也就是1 改为 0） # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # 判断岛屿数量 # @param grid char字符型二维数组 # @return int整型 # class Solution: def solve(self , grid: List[List[str]]) -> int: # write code here m=len(grid) n=len(grid[0]) num=0 def dfs(grid, x, y): # 先“淹掉”自己 grid[x...

此题中任意两点之间距离是 1，可以直接用广度优先搜索（BFS), 第一次到达n 号点的时候就是最短距离。 from collections import deque from collections import defaultdict def main(): n,m=map(int, input().split()) #有个小坑：点数是 5000，n表示目的点的序号，并不表示说点的序号就是0到n-1 edges=defaultdict(list) for i in range(m): u,v=map(int,input().split()) edges[u].append(v) edges[...

通过完全二叉树构建堆：（索引为 i的节点，左子树和右子树分别是2i+1和2i+2）1.push 的时候，将元素加入到末尾，通过_heapify_up 进行调整（和父节点比较大小）2.pop 的时候，交换堆顶元素和末尾元素，通过_heapify_down 进行调整（和左右子树比较大小） class Heap: def __init__(self): self.heap=[] def _heapify_up(self): #末尾元素向上调整，只需要不断和父节点进行比较就行 #考虑2i+1, 2i+2 -> i，父节点的索引是 (index-1)//2 idx= len(self.heap)-...

分治法：将原问题分解成若干个规模较小的子问题，这些子问题的结构与原问题相似。通常，子问题是相互独立的，并且问题规模通常比原问题小。 # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param inorder int整型一维数组 中序遍历序列 # @param postorder int整型一维数组 后序遍历序列 # @return TreeNode类 # ...

# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # 返回最小的花费代价使得这n户人家连接起来 # @param n int整型 n户人家的村庄 # @param m int整型 m条路 # @param cost int整型二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价 # @return int整型 # class UnionFind: def __init__(self, n): self.parent=list(range(n+1)) self.rank=[0]*(n+1) # def find(self,x): #找到x所在的顶...