# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param triangle int整型二维数组 # @return int整型 # """ minTrace1(self , triangle: List[List[int]]) -> int: 这段代码的问题在于它使用了一种 "贪心" 策略来选择路径，这在很多情况下会得到错误的结果。 具体来说，代码的逻辑是：在每一步都选择当前行中相邻的两个元素中较小的那个。但这种局部最优的选择并不能保证最终得到全局最优解。 举个例子，对于输入 [[2],[...

from collections import deque import sys def func(): n, m = map(int, input().split()) adj = [[] for i in range(5001)] count=0 s="" for i in range(m): #u, v = map(int, input().split()) # 输入不一定两个数 有孤立点 # 尝试读取一行，处理可能的EOF line = sys.stdin.readline() if not line: # 已经到达输入末尾 输入的函数可能不是m 行 break c...

# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param head ListNode类 # @param val int整型 # @return ListNode类 # class Solution: def deleteNode(self , head: ListNode, val: int) -> ListNode: # write code her newhead=ListNode...

import itertools def get_prime_factors(num): factors=set() i=2 while i*i<=num: # 只需要检查到 sqrt(num) while num%i==0: # 整除 factors.add(i) num=num//i # 不断除以当前质数 i=i+1 # 关键步骤 处理剩余的质数 num>1 说明剩余的num 是一个质数 无法被2-sqrt(num) 之间的任何数整除 if num>1: factors.add(num) return factors def dfs(arr:list): result=[...

""" 总结： https://mp.csdn.net/mp_blog/creation/success/149482114 """ n ,m , q =map(int ,input().split()) maxtrix = [list(map(int, input().split())) for _ in range(n)] d = [[0 for _ in range(m + 2)] for _ in range(n + 2)] # 初始化差分数组 for i in range(1, n + 1): for j in range(...

import sys # for line in sys.stdin: # a = line.split() # print(int(a[0]) + int(a[1])) def func1(): nm= list( map(int,input().split())) n=nm[0] m=nm[1] nums=list(map(int,input().split())) for i in range(m): cmd=list(map(int,input().split())) l=cmd[0] r=cmd[1] k=cmd[2] #print(nums) for index in range(...

import sys # for line in sys.stdin: # a = line.split() # print(int(a[0]) + int(a[1])) def func1(): nm= list( map(int,input().split())) n=nm[0] m=nm[1] nums=list(map(int,input().split())) for i in range(m): cmd=list(map(int,input().split())) l=cmd[0] r=cmd[1] k=cmd[2] #print(nums) for index in range(...

import sys # for line in sys.stdin: # a = line.split() # print(int(a[0]) + int(a[1])) def sovle(): ns = list(map(int,input().split())) n =ns[0] m =ns[1] nums=list(map(int,input().split())) arr =[0]*(n+1) for i in range (1,n+1): arr[i]=nums[i-1]+arr[i-1] #print(arr) for i in range(m): cm=list(map(int...

import sys """ 解题 思路 https://blog.nowcoder.net/n/3bd0863ecee6487185d6b8217cc01caa 后缀和数据 suffix[i+1][j] 表示str 中字母i 位置后面对应的字母a-z出现次数 从i 后面选择与i位置 不同字母 的两个相同字母j个数cnt , C（ 2,cnt）= cnt*(cnt-1)//2 所以统计 [i+1][0:26] C（ 2,cnt）= cnt*(cnt-1)//2 总和 """ def sovle(): n =int(input()) s...

import sys # for line in sys.stdin: # a = line.split() # print(int(a[0]) + int(a[1])) """ 测试用例1 1 2 2 3 5 4 测试用例2 ---------------------------------- 3 683241938 1 737202770 72474 0701 2 [737202770 72474 0701] 长度为2 ------------------------------------ 测试用例三 12 143115078 395834330 22014...

# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # 将给定数组排序 # @param arr int整型一维数组 待排序的数组 # @return int整型一维数组 题解 ： https://leetcode.cn/discuss/post/3690844/0x11-pai-xu-by-zengjx-mqc4/ # class Solution: def partition(self,arr,left,right): i,j=left,right while i<j: # 从右到左找第一个小于哨兵的元素 while i<j and arr[l...

import sys # for line in sys.stdin: # a = line.split() # print(int(a[0]) + int(a[1])) # +,, """ 堆 heapq 默认实现的是最小堆 实现最大堆 可以插入负值 取出时候添加负号 """ import heapq def solve(): arr=[] n =int(input()) for i in range(n): line =input().split(" ") #print(arr) if line[0]==&qu...

import sys # for line in sys.stdin: # a = line.split() # print(int(a[0]) + int(a[1])) """ 哈夫曼编码 https://blog.csdn.net/xyy1028/article/details/139965597 哈夫曼编码的核心思想： 高频字符用短编码 ，低频符号用长编码，从而最小化总编码长度。 算法思路： 1.优先队列（最小堆） 将所有字符的频率存入最小堆，每次取出两个最小的频率合并 直到对重只剩下一个节点。 合并时，记录每次合并的权值之和，这些权值的累加为最小编码长度。...

import sys # for line in sys.stdin: # a = line.split() # print(int(a[0]) + int(a[1])) """ 解题思路： 贪心解法 0. 对所有活动以结束时间b 为排序 0.1 设置 count 计数 current_end=-1 作为记录结束时间 1. 选择结束时间早的活动，为后面活动预留时间 2. 选择下一个不重叠活动 比较当前活动的起始时间a与current_end 如果当前的起始时间a 大于current_end 用当前活动结束时间更新current_end 用于下次比较， 每次更新当前...