shiqumi

RUC

shiqumi
3个月前
# if __name__ == '__main__':
#     n, m = map(int, input().split())
#     v = [0 for i in range(n + 1)]; w = [0 for i in range(n + 1)]; s = [0 for i in range(n + 1)]
#     f = [[0 for j in range(m + 1)] for i in range(n + 1)]

#     for i in range(1, n + 1):
#         v[i], w[i], s[i] = list(map(int, input().split()))
# # 朴素做法（TLE）
# for i in range(1, n + 1):
#     for j in range(0, m + 1):
#         k = 0
#         while k <= s[i] and k * v[i] <= j:
#             f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i])
#         k += 1

# print(f[n][m])

if __name__ == '__main__':
n, m = map(int, input().split())
f = [0 for i in range(m + 1)]
newgood = []
# 二进制处理，一边输入每种物品的信息，一边将si个物品i转化为数量更少的新商品
for i in range(1, n + 1):
v, w, s = list(map(int, input().split()))
k = 1
while k <= s:
s -= k
newgood.append([k*v, k*w])
k *= 2
if s > 0:
newgood.append([s*v, s*w])

# 01背包问题
for t in newgood:
j = m
while j >= t[0]:
f[j] = max(f[j], f[j - t[0]] + t[1])
j -= 1
print(f[m])



shiqumi
3个月前
# if __name__ == '__main__':
#     n, m = map(int, input().split())
#     v = [0 for i in range(n + 1)]; w = [0 for i in range(n + 1)]; s = [0 for i in range(n + 1)]
#     f = [[0 for j in range(m + 1)] for i in range(n + 1)]

#     for i in range(1, n + 1):
#         v[i], w[i], s[i] = list(map(int, input().split()))
# # 朴素做法（TLE）
# for i in range(1, n + 1):
#     for j in range(0, m + 1):
#         k = 0
#         while k <= s[i] and k * v[i] <= j:
#             f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i])
#         k += 1

# print(f[n][m])

if __name__ == '__main__':
n, m = map(int, input().split())
f = [0 for i in range(m + 1)]
newgood = []
# 二进制处理，一边输入每种物品的信息，一边将si个物品i转化为数量更少的新商品
for i in range(1, n + 1):
v, w, s = list(map(int, input().split()))
k = 1
while k <= s:
s -= k
newgood.append([k*v, k*w])
k *= 2
if s > 0:
newgood.append([s*v, s*w])

# 01背包问题
for t in newgood:
j = m
while j >= t[0]:
f[j] = max(f[j], f[j - t[0]] + t[1])
j -= 1
print(f[m])



shiqumi
3个月前
if __name__ == '__main__':
N = 1010
n, m = map(int, input().split())
v = [0 for i in range(n + 1)]; w = [0 for i in range(n + 1)]
# f = [[0 for i in range(m + 1)] for j in range(n + 1)]

for i in range(1, n + 1):
v[i], w[i] = list(map(int, input().split()))

# 朴素做法(TLE)
# for i in range(1, n + 1):
#     for j in range(0, m + 1):
#         k = 0
#         while k * v[i] <= j:
#             f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + k * w[i])

#             k += 1
# print(f[n][m])
# 进阶做法一
# for i in range(1, n + 1):
#     for j in range(0, m + 1):
#         f[i][j] = f[i - 1][j]
#         if j >= v[i]:
#             f[i][j]= max(f[i][j], f[i][j - v[i]] + w[i])

# print(f[n][m])
# 进阶做法二：一维数组
f = [0 for i in range(m+1)]
for i in range(1, n + 1):
# print('----------------')
for j in range(v[i], m + 1):
f[j] = max(f[j], f[j - v[i]] + w[i])
# print(f)

print(f[m])



shiqumi
3个月前

## 一、为何可以用一维数组代替二维数组？

f[i][j] = f[i - 1][j] # 不含i的所有选法的最大价值
if j >= v[i]: # 判断含i的选法是否成立
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i])

可以看出f[i][:]只依赖于f[i-1][:]，所以根本没必要保留之前的f[i-2][:]等状态值；



## 二、为何要逆序更新？

        while j >= v[i]:
dp[j] = max(dp[j], dp[j - v[i]] + w[i])


### 一维数组python代码

if __name__ == '__main__':

n, m = map(int, input().split()) # n,m分别表示物品数量和背包容积
v = [0 for i in range(n+1)]; w = [0 for i in range(m+1)]
for i in range(1, n + 1):
v[i], w[i] = list(map(int, input().split())) # 从索引1开始

# 一维数组
dp = [0 for i in range(m+1)]
for i in range(1, n + 1):# i 仍代表可以选择前i个物品
j = m
while j >= v[i]:
dp[j] = max(dp[j], dp[j - v[i]] + w[i])
j -= 1
print(dp)
print('------------------')

print(dp[-1])


## 三、用样例解释，打印dp方便理解

#### 更新索引5

i = 3, j = 5(m=5),v[3] = 3, w[3] = 4

#### 更新索引4

i = 3, j = 4(m=5),v[3] = 3, w[3] = 4此时进入j = 4

### 到这里就可以看出按索引从大到小求当前层dp值能保留上一层较小索引的dp值

输入样例
4 5
1 2
2 4
3 4
4 5

8


n = 4, m = 5

第一层dp, i = 1, v[1] = 1 , w[1] = 2, dp[j] = max(dp[j], dp[j - v[1]] + w[1])
dp[j] = max(dp[j], dp[j - 1] + 2) j从5到1
[0, 0, 0, 0, 0, 2]
[0, 0, 0, 0, 2, 2]
[0, 0, 0, 2, 2, 2]
[0, 0, 2, 2, 2, 2]
[0, 2, 2, 2, 2, 2]
------------------

dp[j] = max(dp[j], dp[j - 2] + 4) j从5到2
[0, 2, 2, 2, 2, 6]
[0, 2, 2, 2, 6, 6]
[0, 2, 2, 6, 6, 6]
[0, 2, 4, 6, 6, 6]
------------------

dp[j] = max(dp[j], dp[j - 3] + 4) j从5到3
[0, 2, 4, 6, 6, 8]
[0, 2, 4, 6, 6, 8]
[0, 2, 4, 6, 6, 8]
------------------

dp[j] = max(dp[j], dp[j - 4] + 5) j从5到4
[0, 2, 4, 6, 6, 8]
[0, 2, 4, 6, 6, 8]
------------------
8


### 二维数组朴素方法（简单易懂也能AC）

if __name__ == '__main__':
N = 1010

n, m = map(int, input().split()) # n,m分别表示物品数量和背包容积
v = [0 for i in range(N)]; w = [0 for i in range(N)]
for i in range(1, n + 1):
v[i], w[i] = list(map(int, input().split())) # 从索引1开始

f = [[0 for i in range(N)] for j in range(N)] # 二维数组存储当前状态可达到的最大价值
# 朴素方法
i = 1
while i <= n:
j = 0
while j <= m:
f[i][j] = f[i - 1][j] # 不含i的所有选法的最大价值
if j >= v[i]: # 判断含i的选法是否成立
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i])
j += 1
i += 1
for i in range(len(f)):
print(f[i])

print(f[n][m])


shiqumi
3个月前

if __name__ == '__main__':
N = 6

n, m = map(int, input().split()) # n,m分别表示物品数量和背包容积
v = [0 for i in range(N)]; w = [0 for i in range(N)]
for i in range(1, n + 1):
v[i], w[i] = list(map(int, input().split())) # 从索引1开始

f = [[0 for i in range(N)] for j in range(N)] # 二维数组存储当前状态可达到的最大价值
# 朴素方法
i = 1
while i <= n:
j = 0
while j <= m:
f[i][j] = f[i - 1][j] # 不含i的所有选法的最大价值
if j >= v[i]: # 判断含i的选法是否成立
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i])
j += 1
i += 1
for i in range(len(f)):
print(f[i])

print(f[n][m])

# 一维数组
dp = [0 for i in range(m+1)]
for i in range(1, n + 1):# i 仍代表可以选择前i个物品
j = m
while j >= v[i]:
dp[j] = max(dp[j], dp[j - v[i]] + w[i])
j -= 1
print(dp)
print('------------------')
# 将每一个i循环的dp打印出来就容易理解为何要逆序遍历j(限制物品总体积)
# i = 3, j = 5(m=5),v[3] = 3, w[3] = 4
# 当前更新第3层索引5 dp[5] = max(dp[5], dp[2] + 4) # 注意，等号右边的dp[5],dp[2]都必须是上一层dp的对应索引值
# 此时第二层为[0, 2, 4, 6, 6, 6]，第三层[0, 2(未改), 4(未改), 6(未改), 6(未改), 6(正在改)]
# 因为本层更新dp[5]时，只能使用未更新的dp值，这些才是上一层的dp值，即索引较小的最后更新

# 此时第三层索引5更新完后为[0, 2(未改), 4(未改), 6(未改), 6(未改), 8(已经改)]
# i = 3, j = 4(m=5),v[3] = 3, w[3] = 4 此时进入j = 4
# 更新第三层索引4 dp[4] = max(dp[4], dp[1] + 4) # 注意，等号右边的dp[4],dp[1]都必须是上一层dp的对应索引值
# 到这里就可以看出按索引从大到小求当前层dp值能保留上一层较小索引的dp值
print(dp[-1])

# [0, 0, 0, 0, 0, 2]
# [0, 0, 0, 0, 2, 2]
# [0, 0, 0, 2, 2, 2]
# [0, 0, 2, 2, 2, 2]
# [0, 2, 2, 2, 2, 2]
# ------------------
# [0, 2, 2, 2, 2, 6]
# [0, 2, 2, 2, 6, 6]
# [0, 2, 2, 6, 6, 6]
# [0, 2, 4, 6, 6, 6]
# ------------------
# [0, 2, 4, 6, 6, 8]
# [0, 2, 4, 6, 6, 8]
# [0, 2, 4, 6, 6, 8]
# ------------------
# [0, 2, 4, 6, 6, 8]
# [0, 2, 4, 6, 6, 8]
# ------------------
# 8


shiqumi
3个月前
class SummaryRanges:

def __init__(self):
# 创建存储所有间隔的列表，例如截止7存储为[1, 3, 6, 7],两个两个为一个区间左右端点
self.d = []

def addNum(self, val: int) -> None:
# 二分法查找val应插入的位置，直接采用bisect库函数，其目的在于查找该数值将会插入的位置并返回，而不会插入。
m = bisect.bisect(self.d, val)

# 仅当m为偶数时才需要更新，因为间隔每两位为一组，若待插入位置为奇数，则一定位于某一组间隔内
# 比如[1,3,6,7] 插入2，返回m = 1,则代表2已经在区间之中（[1,3]),此时不用更新
if m % 2 == 0:

#处理右边界
# 若新加入的数与其插入位置右侧的间隔有重叠部分（即差为1），则更新，使插入位置的值val
# 比如[1,3,6,7] 插入5返回m = 2，且5 = 6 -1,说明5可以作为新连续区间的左端点，直接把原连续区间左端点覆盖为val(此处为5)即可
if m < len(self.d) and self.d[m] - val == 1:
self.d[m] = val

# 若新加入的数的插入位置等于数组长度，即放置在最后，则依次添加间隔对（暂不处理左边界）
# 比如[1,3,6,7] 插入8返回m = 4，则先无脑加入区间对8,8到数组最后，得到[1,3,6,7,8,8]
else:
self.d.insert(m, val)
self.d.insert(m, val)

# 处理左边界
# 若与左侧间隔有重叠部分，差为1时，删除本身左节点及前向间隔右节点
# 比如 [1,3,6,7,8,8] ,m仍为4，此时8-7<=1，则pop(m=4)删除第一个8，再pop(m-1)删除7，得到[1,3,6,8]
# 若[1,3,6,7] 插入7，也是m = 4，经过上一步得到[1,3,6,7,7,7]，然后7-7<=1,先删第二个7，再删第一个7,得到[1,3,6,7]
if m > 0 and self.d[m] - self.d[m - 1] <= 1:#根据现有情况选择是否和左区间合并
self.d.pop(m)
self.d.pop(m - 1)

def getIntervals(self) -> List[List[int]]:
# 列表元素两个两个输出为一个区间
res = []
i = 0
while i < len(self.d):
res.append(self.d[i:i+2])
i += 2
return res
# 间隔列表例如[1, 3, 6, 7], 按奇偶位组合填充列表返回
#         return [*zip(self.d[:: 2], self.d[1:: 2])]      #按奇偶顺序打包输出



shiqumi
3个月前
from heapq import *
class MedianFinder:

def __init__(self):
"""
"""
self.maxh = []; self.minh = []

def addNum(self, num: int) -> None:
heappush(self.minh, num) # 先无脑把新元素插到最小堆
if len(self.maxh) and -self.maxh[0] > self.minh[0]:
# 若最大堆非空且最大堆堆顶大于最小堆堆顶，把两者互换
maxv = - heappop(self.maxh)
minv = heappop(self.minh)
heappush(self.minh, maxv)
heappush(self.maxh, - minv)
# 若最小堆元素个数比最大堆多2，则弹出最小堆堆顶到最大堆中
if len(self.minh) > len(self.maxh) + 1:

heappush(self.maxh, -heappop(self.minh))

def findMedian(self) -> float:
if len(self.maxh) + len(self.minh) & 1: # 总数为奇数，返回最小堆堆顶
return self.minh[0]
else:
return (self.minh[0] - self.maxh[0]) / 2.0
# 返回两个堆顶求平均，注意最大堆堆顶弹出后取相反数

# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# param_2 = obj.findMedian()

# 动态维护有序序列-> 手写平衡树
# 使用对顶堆，小根堆维护数据较大的一半，大根堆维护数据较小的一半
# 先无脑塞进小根堆，若两堆数据量之差大于1，则弹出小根堆堆顶到大根堆
# 总数为偶数，取两个堆顶的均值；总数为奇数，取小根堆堆顶作为中位数


shiqumi
3个月前
from heapq import *
from collections import defaultdict
class Solution:
def topKFrequent(self, words: List[str], k: int) -> List[str]:
hash = defaultdict(lambda: 0) # 统计单词次数，默认值为0
heap = [] # 堆
for word in words:
hash[word] += 1
# for word, cnt in hash.items():
#     # 对字典键值进行互换，因为要用次数进行堆排序
#     t = [cnt, word]
#     # 先无脑向堆中插入新元素，若超过k个就删去最小值
#     heappush(heap, t)
#     if len(heap) > k:
#         heappop(heap)
# res = [None for i in range(k)]
# i = k - 1
# while i >= 0:
#     res[i] = heappop(heap)
#     i -= 1
# 当两个字符串出现次数相等，按照字母顺序排？好像不是
# 因为堆排序内部的字符串不是按照字母顺序排，所以可能会漏掉一些没进入答案集，所以还是失败
res = []
for i,v in hash.items():
res.append([v,i])
res.sort(key=lambda x:(-x[0], x[1]))
#第一个要颠倒，不然从小到大，第二个本就从小到大（a,aa）
res = res[:k]
return [i[1] for i in res]


shiqumi
3个月前
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
n = len(edges)
self.p = []
for i in range(n + 1): self.p.append(i) # 有多余边，所以加一

for e in edges: # 遍历每条边
a = e[0]; b = e[1]
if self.find(a) == self.find(b): return [a, b] # 若该边连的两个点之前已经在同一个集合
# 说明此边是冗余的，返回此边，代表可以删除
self.p[self.find(a)] = self.find(b) # 否则，将两点归到同一个集合，
return None
def find(self, x):
if self.p[x] != x:
self.p[x] = self.find(self.p[x])
return self.p[x]

# 把所有已经连通的点放到一个集合中去



shiqumi
3个月前
class UnionFind():
def __init__(self, p):
self.p = p

def find(self, x):
if self.p[x] != x:
self.p[x] = self.find(self.p[x])
return self.p[x]

def union(self, a, b):
fa, fb = self.find(a), self.find(b)
self.p[fb] = fa # 将b的父节点指向a的父节点

class Solution:
def findCircleNum(self, M: List[List[int]]) -> int:
n = len(M)
data = UnionFind([i for i in range(n)])
for i in range(n):
for j in range(i):
if M[i][j]:
data.union(i,j) # 合并两个朋友的朋友圈

res = 0
for i in range(n):
if data.find(i) == i: # 计算有多少个根节点就有多少个朋友圈
res += 1

return res