[LeetCode周赛复盘] 第 99 场双周赛20230304

一、本周周赛总结

• T1 贪心。
• T2 数学/dp。
• T3 线段合并/快速幂取模。
• T4 换根DP。

二、 [Easy] 2578. 最小和分割

链接: 2578. 最小和分割

1. 题目描述

2. 思路分析

• 这题如果不写暴力枚举的话，是个贪心，想了好一会。
• 排序后奇偶交错分配即可。
• 枚举的话，状压枚举可能写的更快一些。

3. 代码实现

class Solution:def splitNum(self, num: int) -> int:              s = []for c in str(num):if c != '0':s.append(c)s = sorted(s)n = len(s)h = n // 2a = []b = []for i,c in enumerate(s):if i & 1:b.append(c)else:a.append(c)x = int('0'+''.join(a))y = int('0'+''.join(b))return x + y 

三、[Medium] 2579. 统计染色格子数

链接: 2579. 统计染色格子数

1. 题目描述

2. 思路分析

数学能力已经退化，比赛时肯定不优先推公式。

• 找规律dp。
• 发现每次增加i*4个。

3. 代码实现

f = [1]*(10**5+1)
x = [1]*(10**5+1)
for i in range(2,10**5+1):x[i] = (i-1)*4f[i] = f[i-1] + x[i]
class Solution:def coloredCells(self, n: int) -> int:return f[n]        

四、[Medium] 2580. 统计将重叠区间合并成组的方案数

链接: 2580. 统计将重叠区间合并成组的方案数

1. 题目描述

2. 思路分析

• 分析题意发现，有交集的区间一定在一起，那么划分完会变成x个集合，这x个集合分别可以在左边或右边就互不影响了。
• 因此答案就是2**x。

3. 代码实现

MOD = 10 ** 9 + 7
class Solution:def countWays(self, ranges: List[List[int]]) -> int:cnt = 1ranges.sort()print(ranges)p = ranges[0][1]for x,y in ranges:if x <= p:p = max(p,y)else:cnt += 1p = yreturn pow(2,cnt,MOD)

五、[Hard] 2581. 统计可能的树根数目

链接: 2581. 统计可能的树根数目

1. 题目描述

2. 思路分析

• 知道是换根DP，之前学了max版的换根dp，这次遇到加法的就不会了。
• 学了一下。
• 当然用模板也能做。

3. 代码实现

class Solution:def rootCount(self, edges: List[List[int]], guesses: List[List[int]], k: int) -> int:n = len(edges)+ 1g = [[] for _ in range(n)]for u,v in edges:g[u].append(v)g[v].append(u)s = set(tuple(x) for x in guesses)f = [0]*ndef dfs(u,fa):for v in g[u]:if v != fa:if (u,v) in s:f[0] += 1dfs(v,u)def reroot(u,fa):for v in g[u]:if v != fa:f[v] = f[u] + int((v,u) in s) - int((u,v) in s)reroot(v,u)dfs(0,-1)reroot(0,-1)return sum(x >= k for x in f)      

六、参考链接