一、本周周赛总结

• 比赛后才做出T3，没敢交
• T1 模拟。
• T2 贪心+分类讨论。
• T3 26维前缀和+枚举。
• T4 组合数学。

100144. 找出峰值

100144. 找出峰值

1. 题目描述

2. 思路分析

按题意模拟即可。

3. 代码实现

class Solution:def findPeaks(self, a: List[int]) -> List[int]:return [i for i in range(1,len(a)-1) if a[i-1] < a[i] > a[i+1]]

100153. 需要添加的硬币的最小数量

100153. 需要添加的硬币的最小数量

1. 题目描述

2. 思路分析

分类讨论

• 先把数据排序，从小到大处理。
• 假设当前我们已经得到了[0,s)之间所有的整数。下一个要添加的数x。
  • 添加后可以新获得[x,x+s)之间所有的数。
• 若x<=s,则可以获得[0,x+s)。
• 若x>s, 则无法得到s,必须添加s，得到[0,s+s)。

---

• 时间复杂度O(nlgn+lgtarget),
• 解释其中lgtarget：若coins为空，那么我们必须自己构造1 2 4 8相当于给target二进制分解。

3. 代码实现

class Solution:def minimumAddedCoins(self, coins: List[int], target: int) -> int:coins.sort()n = len(coins)ans = 0 i = 0s = 1while s <= target:if i < n and coins[i] <= s:s += coins[i]i += 1else:s += s ans += 1return ans

100145. 统计完全子字符串

100145. 统计完全子字符串

1. 题目描述

2. 思路分析

 被这题干趴了。一开始写了个滑窗一直wa。

• 这题的难点主要在于计算复杂度，敢不敢暴力。
• 观察合法子串性质，发现子串长度一定是k的倍数，而且最多是26k。再大的话，一定有字母的出现次数超过k了。
• 枚举每个位置作为子串的最后一个字符，左端点每次向前跳k，能否快速计算这段里的每个字符的出现次数？
  • 对每个字符单独做前缀和，用一个26*(n+1)的数组存。
  • 这样计算的次数是26。
• 另外注意，相邻字符差不能超过2，因此左端点向前跳时不能超过这段的开头。
• 实现时，把原串先改写成0~25的数字。

---

• 时间复杂度O(n2626)。最多比较26次（向前跳），每次比较花费26。

3. 代码实现

class Solution:def countCompleteSubstrings(self, word: str, k: int) -> int:n = len(word)a = [ord(c) - ord('a') for c in word]cnt = [[0] * 26 for _ in range(n+1)]for i, v in enumerate(a):cnt[i+1] = cnt[i][:]cnt[i+1][v] += 1ans = 0start = 0  # 当前连续段的开头(相邻差<=2)for i, v in enumerate(a):if i and abs(v-a[i-1]) > 2:  # 重开一段start = i j = i - k + 1  # 往前跳over_k = False  # 有一个字符数量已经超过kwhile j >= start and not over_k:for x,y in zip(cnt[i+1],cnt[j]):if x-y>k:over_k = True breakif x-y > 0 and x - y != k :breakelse:ans += 1j -= kreturn ans 

100146. 统计感冒序列的数目

100146. 统计感冒序列的数目

1. 题目描述

2. 思路分析

组合数学

• m = len(sick)个病人把 整个数组分割成m+1段，只讨论不为空的段。
• 处于中间的段，长为k，自己的传染顺序方案有pow(2,k-1)种，即每次要么感染左端，要么感染右端，当长为1时，左右等价。
• 一共n-m个健康人，从这个序列中选k个位置，作为这组的人的位置，共C(n-m,k)种方案。
  • 安排完这一组，安排下一组时，是从n-m-k中选k’个位置。
• 然后讨论处于两端的段，他们只有一个传染方向，因此自己的顺序只有一种，但要讨论位置方案。

---

• 其中组合数直接贴逆元模板。
• 初始化放里边竟然会TLE，难绷

3. 代码实现

class ModComb:"""通过O(n)预处理逆元，达到O(1)询问组合数"""def __init__(self, n, p):"""初始化，为了防止模不一样，因此不写默认值，强制要求调用者明示:param n:最大值:param p: 模"""self.p = pself.inv_f, self.fact = [1] * (n + 1), [1] * (n + 1)inv_f, fact = self.inv_f, self.factfor i in range(2, n + 1):fact[i] = i * fact[i - 1] % pinv_f[-1] = pow(fact[-1], p - 2, p)for i in range(n, 0, -1):inv_f[i - 1] = i * inv_f[i] % pdef comb(self, m, r):if m < r or r < 0:return 0return self.fact[m] * self.inv_f[r] % self.p * self.inv_f[m - r] % self.p
MOD = 10 ** 9 + 7 
mc = ModComb(10**5 + 5, MOD)
class Solution:def numberOfSequence(self, n: int, sick: List[int]) -> int:ans = 1 s = n - len(sick)for x,y in pairwise(sick):v = y - x -1if v:ans = ans * mc.comb(s,v) % MOD * pow(2,v-1,MOD) % MOD s -= v ans = ans * mc.comb(s,sick[0]) % MODreturn ans % MOD       

参考链接