Q1. 最小正和子数组
原题链接
Q1. 最小正和子数组
思路分析
签到题，暴力就行
时间复杂度：O(N^2)
AC代码
class Solution:def minimumSumSubarray(self, nums: List[int], l: int, r: int) -> int:n = len(nums)res = -1acc = list(accumulate(nums, initial=0))for i in range(n):for j in range(i + l - 1, min(n, i + r)):if acc[j + 1] - acc[i] > 0:if res == -1:res = acc[j + 1] - acc[i]else:res = min(res, acc[j + 1] - acc[i])return resQ2. 重排子字符串以形成目标字符串
原题链接
Q2. 重排子字符串以形成目标字符串
思路分析
存一下s中每个块的数目和t的每个块比对下数量够不够
时间复杂度：O(N)
AC代码
class Solution:def isPossibleToRearrange(self, s: str, t: str, k: int) -> bool:cnt = Counter()n, m = len(s), len(t)if n % k: return FalseB = n // kfor i in range(0, n, B):cnt[s[i:i+B]] += 1for i in range(0, m, B):if cnt[t[i:i+B]] == 0:return Falsecnt[t[i:i+B]] -= 1return TrueQ3. 最小数组和
原题链接
Q3. 最小数组和
思路分析
很典的dp
f(i, j, k) 为 [i, n - 1] 剩余 j 次 操作1，k次操作2的最小数组和
枚举当前的方案进行转移即可
时间复杂度：O(N OP1 OP 2)
AC代码
class Solution:def minArraySum(self, nums: List[int], v: int, op1: int, op2: int) -> int:n = len(nums)@cachedef dfs(i: int, j: int, k: int):if i == n: return 0res = nums[i] + dfs(i + 1, j, k)if j:res = min(res, (nums[i] + 1) // 2 + dfs(i + 1, j - 1, k))if k and nums[i] >= v:res = min(res, nums[i] - v + dfs(i + 1, j, k - 1))if j and k and nums[i] >= v:t = (nums[i] - v + 1) // 2if (nums[i] + 1) // 2 >= v:t = min(t, (nums[i] + 1) // 2 - v)res = min(res, t + dfs(i + 1, j - 1, k - 1))return resres = dfs(0, op1, op2)dfs.cache_clear()return resQ4. 移除边之后的权重最大和
原题链接
Q4. 移除边之后的权重最大和
思路分析
树形dp + 贪心
每个边选或不选，容易想到树上背包
但是这个数据量，显然会炸掉，尝试优化
定义 f(u, lim) 为 u 所在子树最大合法化值，lim = true 说明<p, u> 的边被父节点拿掉了，否则没拿掉
所以 u 能够保存的边数目为 min(k - lim, adj[u] - 1)
我们假设 u 往下伸的所有边 都不拿，然后贪心的考虑拿谁
一条边 <u, v> 从不拿到拿的变化花费：f(v, true) + w - f(v, false)
即，按照f(v, true) + w - f(v, false) 从大到小拿即可
时间复杂度：O(nlogm)
AC代码
class Solution:def maximizeSumOfWeights(self, edges: List[List[int]], k: int) -> int:n = len(edges) + 1adj = [[] for _ in range(n)]for (u, v, w) in edges:adj[u].append([v, w])adj[v].append([u, w])@cachedef dfs(u: int, p: int, lim: bool) -> int:t = k - limh = []res = 0for (v, w) in adj[u]:if v == p: continuea = dfs(v, u, False)b = w + dfs(v, u, True)h.append(b - a)res += ah.sort(reverse=True)for i in range(min(t, len(h))):if h[i] <= 0: breakres += h[i]return resreturn dfs(0, -1, False)
