3769. 二进制反射排序 - 力扣（LeetCode）
题目类型
#排序
解题思路
参考：这道题很简单！
示例代码
python
class Solution:
def sortByReflection(self, nums: List[int]) -> List[int]:
return sorted(nums, key=lambda p: (int(bin(p)[2:][::-1], 2), p))3770. 可表示为连续质数和的最大质数 - 力扣（LeetCode）
题目类型
#预处理 #数学 #质数筛
解题思路
参考：这道题很简单！
示例代码
python
MX = 5 * 10**5 + 5
primes = []
is_prime = [False] * 2 + [True] * (MX - 2)
for i in range(2, MX):
if is_prime[i]:
primes.append(i)
for p in primes:
if i * p >= MX:
break
is_prime[i * p] = False
if i % p == 0:
break
pre = 0
fair = [0]
for p in primes:
pre += p
if pre <= MX and is_prime[pre]:
fair.append(pre)
fair.append(inf)
class Solution:
def largestPrime(self, n: int) -> int:
idx = bisect_right(fair, n) - 1
return fair[idx]3771. 探索地牢的得分 - 力扣（LeetCode）
题目类型
#前缀和 #二分
解题思路
从起点 到房间 ，公式推导：
示例代码
python
class Solution:
def totalScore(self, hp: int, damage: List[int], requirement: List[int]) -> int:
s = [0] * (len(damage) + 1)
ans = 0
for i, (dmg, req) in enumerate(zip(damage, requirement)):
s[i + 1] = s[i] + dmg
low = s[i + 1] + req - hp
j = bisect_left(s, low, 0, i + 1) # 在 [0, i] 中二分
ans += i - j + 1
return anspython
class Solution:
def totalScore(self, hp: int, damage: List[int], requirement: List[int]) -> int:
n = len(damage)
pre = list(accumulate(damage, initial=0))
g = []
for i in range(n):
g.append(pre[-1] - pre[i])
g = g[::-1]
g.append(inf)
cur = hp
ans = 0
for i in range(n - 1, -1, -1):
tmp = cur - requirement[i]
idx = bisect_left(g, tmp + 1, n - i - 1, n + 1)
ans += idx - (n - i - 1)
cur += damage[i]
return ans3772. 子图的最大得分 - 力扣（LeetCode）
题目类型
#换根DP
解题思路
对 为根的子树进行 记录子树最大权值和，在进行 更新各个节点为根的子树最大权值和
参考：【图解】一张图秒懂换根 DP！（Python/Java/C++/Go/JS） | 换根 DP（Python/Java/C++/Go）
示例代码
python
class Solution:
def maxSubgraphScore(
self, n: int, edges: List[List[int]], good: List[int]
) -> List[int]:
g = [[] for _ in range(n)]
for u, v in edges:
g[u].append(v)
g[v].append(u)
def dfs(x, fa):
f[x] = 1 if good[x] else -1
for y in g[x]:
if y == fa:
continue
dfs(y, x)
f[x] += max(f[y], 0)
def reroot(x, fa, cur):
ans[x] = f[x] + max(cur, 0)
for y in g[x]:
if y == fa:
continue
reroot(y, x, ans[x] - max(f[y], 0))
return
f = [0] * n
ans = [-1] * n
dfs(0, -1)
re(0, -1, 0)
return ans