4~5月份算竞总结
4~5月份总结
力扣水了700题（）
板子
"""质因数分解： 将输入的整数num分解为质因数的乘积，返回一个字典，其中： 键：质因数 值：该质因数出现的次数，即指数 列：fc(12) 返回 {2：2，3：1} 12 = 2**2 + 3**1"""def fc(num): fa = {} # 存储质因数字典 {质数: 指数} d = 2 # 从最小的质数2开始试除
while d * d <= num: # 只需要试除到 sqrt(num) if num % d == 0: # d是num的质因数 cnt = 0 while num % d == 0: # 反复除以d，统计指数 num //= d cnt += 1 fa[d] = fa.get(d, 0) + cnt # 记录该质因数及其指数 d += 1 if d == 2 else 2 # 跳过偶数（优化） # 等价于：d = 3 if d == 2 else d + 2
if num > 1: # 如果剩余num > 1，说明它是质数 fa[num] = fa.get(num, 0) + 1
return fa
"""生成一个数的所有约数： 接收一个质因数分解字典，返回该数的所有正约束组成的列表 例：输入{2:2,3:1} 返回[1,2,4,3,6,12]"""
def get_fa(fa): res = [1] # 初始只有约数1
for p, e in fa.items(): # 遍历每个质因数p及其指数e new = [] # 存储本轮新生成的约数
for f in res: # 遍历已有的每个约数 mul = 1 # p的幂次初始为1 (p^0)
for _ in range(e + 1): # 从p^0到p^e new.append(mul * f) # 生成新约数：f × p^i mul *= p # 更新为下一个幂次
res = new # 更新约数列表
return res# 区间覆盖最大重叠数n,k = map(int,input().split())g = []"""给定n个区间 [l, r]，每个区间表示某个条件满足的范围求在整数点上，最多有多少个区间同时覆盖该点特殊处理：区间被扩展了，实际处理的区间是 [l-k, r]（从l-k开始，到r结束）"""
for _ in range(n): l,r = map(int,input().split()) g.append((l - k,1)) g.append((r + 1,-1))g.sort()cur = 0ans = 0for _,d in g: cur += d ans = max(ans,cur)print(ans)# 选择尽可能多的不相交区间n = int(input())g = []for _ in range(n): l,r = map(int,input().split()) g.append([l,r])g.sort(key = lambda x:x[1])last = -1cnt = 0for st,en in g: if st >= last: cnt += 1 last = enprint(cnt)from collections import defaultdict"""不同字符个数不超过k的所有子串的数量"""def f(k): if k <= 0: return 0 # k≤0时，没有合法子串（除非k=0且有空串）
cnt = defaultdict(int) # 统计窗口内每个字符的出现次数 left = 0 # 窗口左边界 d = 0 # 窗口内不同字符的种类数 ans = 0 # 答案累计
for right in range(len(s)): # 右指针遍历 c = s[right] # 当前字符 cnt[c] += 1 # 加入窗口
if cnt[c] == 1: # 如果该字符第一次出现 d += 1 # 不同字符数+1
while d > k: # 如果不同字符数超过k c_left = s[left] # 左边界字符 cnt[c_left] -= 1 # 移出窗口 if cnt[c_left] == 0: # 如果该字符完全消失 d -= 1 # 不同字符数-1 left += 1 # 左边界右移
ans += right - left + 1 # 累加以right结尾的合法子串数 return ans
def f(s, k, l, r): """不同字符个数不超过k，且长度在[l, r]之间的子数组数量""" if k <= 0: return 0
cnt = defaultdict(int) left = 0 # 窗口左边界索引 distinct = 0 # 窗口内不同字符种类数 ans = 0
for right in range(len(s)): c = s[right] cnt[c] += 1 if cnt[c] == 1: distinct += 1
while distinct > k: c_left = s[left] cnt[c_left] -= 1 if cnt[c_left] == 0: distinct -= 1 left += 1
# 合法左端点范围：[max(left, right - r + 1), right - l + 1] lo = max(left, right - r + 1) hi = right - l + 1 if lo <= hi: ans += hi - lo + 1 return ansdef countSubsequences(s, mod): dp = [0] * mod for ch in s: d = int(ch) ndp = dp[:] ndp[d % mod] += 1 # 单独选当前字符 for r in range(mod): nr = (r * 10 + d) % mod # 追加到已有序列 ndp[nr] = (ndp[nr] + dp[r]) % MOD dp = ndp return dp[0] # 模mod为0的子序列数二分答案
ABC457D-二分答案
题意：
每次操作可以选择位置 i，将 A[i] 增加 i。总共最多 K 次操作，目标是最大化最终的最小值。
题解：
假设我们想让所有元素都至少为 X。对于位置 i，A[i] 需要增加的量是：need[i] = max(0,x - a[i]），每次操作可以增加i，所以位置i需要的操作次数为：ops[i] = ceil(need[i] / i) = (need[i] + i - 1) // i，如果∑ ops[i] ≤ K，则可以使最小值 ≥ X，否则不行。
n, k = map(int, input().split())a = list(map(int, input().split()))def check(mid): ops = 0 for i, x in enumerate(a): if x < mid: t = (mid - x + i) // (i + 1) ops += t if ops > k: return False return True
left = min(a) - 1right = max(a) + k * n + 1while left + 1 < right: mid = (left + right) // 2 if check(mid): left = mid else: right = midprint(left)搜索
CF1101Div2C2-三分搜索
-
思路(DS)
一、问题的本质
这道题的核心决策是：将多少个A型朋友当作I型处理？
设这个数量为
m（前m个A型当I型，其余当E型），定义函数：f(m) = 按照这个策略能入座的最大人数问题转化为：在
m ∈ [0, A_count]上求f(m)的最大值。二、为什么
f(m)是单峰函数？直观理解
想象两个极端：
m = 0（所有A型都当E型）：
- 桌子全靠I型来开
- 如果I型很少，桌子开得少，后面E型和A型没桌子可坐
- 问题：桌子太少，座位不够****m = A_count（所有A型都当I型）：
- 大量A型开新桌，很快就用完所有桌子
- 后面真正的I型没桌子可坐，只能被拒绝
- 问题：桌子被A型浪费，真正的I型无法入座****最优的m在中间：平衡桌子使用，既不让桌子太少导致E型无处可坐，也不让桌子被A型过早耗尽导致I型无法入座。 单调性分析
当m从0逐渐增加到A_count时：
阶段1：上升阶段（m较小）
m=0: A型都当E型I型开桌 → 只有几张桌子A型和E型争抢非空桌的座位问题：桌子太少，很多人因无非空桌而被拒绝m=1: 第1个A型开新桌多了一张桌子 → 更多非空桌 → 更多人能入座f(1) > f(0)m=2: 第2个A型开新桌再多一张桌子 → 更多人能入座f(2) > f(1)为什么上升？ 增加m意味着更多A型开新桌，增加桌子数量，为E型和后续A型创造更多”非空桌”座位。此时桌子还没用完，利大于弊。
阶段2：下降阶段（m较大）
m接近A_count: 大部分A型都开新桌桌子很快被占满m=A_count-1: 倒数第2个A型还在开新桌可能已经用完所有桌子m=A_count: 所有A型都开新桌桌子被A型占满，后面的I型没桌子可坐f(A_count) < f(A_count-1)为什么下降？ 增加m导致桌子被A型过早占满，真正的I型（必须坐空桌）无法入座。此时弊大于利。
数学证明思路
考虑相邻两个值
f(m)和f(m+1)：差异：第m+1个A型从”当E型”变为”当I型”
- 正面效果：可能多开一张桌子，增加T → 后续E型和A型更容易入座
- 负面效果：消耗一张空桌 → 后续I型可能无法入座 随着m增大：
- 正面效果递减（桌子越来越多，但总桌子数有限）
- 负面效果递增（剩余空桌越来越少，I型越难入座）
因此存在一个临界点，超过后
f(m+1) < f(m)，形成单峰。 三、为什么能用二分搜索？
二分搜索的前提是：函数具有单调性。
但
f(m)不是单调的（先增后减），怎么二分？关键技巧：比较相邻值判断方向
不需要
f(m)整体单调，只需要能判断当前在上升还是下降阶段：if f(m) < f(m + 1):# 还在上升，最大值在右侧# 可以安全排除 m 及左侧else:# 已经开始下降，最大值在左侧或就是m# 可以安全排除 m+1 及右侧这就是三分搜索的二分实现，专门用于单峰函数求极值。
import sysinput = sys.stdin.readlineT = int(input())for _ in range(T): n, t, s = map(int, input().split()) S = input().strip() def f(m): T = 0 ans = 0 remaining = m for c in S: if c == 'I': if T < t: T += 1 ans += 1 elif c == 'E': if ans < T * s: ans += 1 else: if remaining > 0: remaining -= 1 if T < t: T += 1 ans += 1 else: if ans < T * s: ans += 1 return ans A_count = S.count('A') l = -1 r = A_count while l + 1 < r: mid = (l + r) // 2 # 比较 mid 和 mid+1 if f(mid) < f(mid + 1): # 上升阶段，最大值在 mid+1 或更右 l = mid else: # 下降阶段，最大值在 mid 或更左 r = mid print(f(r))贪心
CF1100Div2C1-贪心
题意：
给定序列a，选择一个索引i且ai>0，对于每个1≤j≤i的aj对其乘以-1
要求是求出最多n次操作后，使sum(a)最小的序列
题解：
从后向前遍历，对于遇到的每个数，都可以确保其变为负数，如果当前数是整数，则对其进行一次操作；反之继续
CF1099Div2B-贪心
题意：
给定一个数组，可以最多对该数组执行如下的一次操作：
选择一个整数k，以及一个子序列b，将k加到该子序列的每个元素上
判断是否能够是数组按非递减顺序排序
题解：
当数组中相邻元素出现递减a[i] < a[i-1]时，如果a[i-1] < a[i-2]，那么显然，无法通过给定的操作实现非递减；反之，用一个maxadd = max(maxadd,a[i-1] - a[i])，记录最大的kk值
正向遍历数组，为每个a[i] < a[i-1]的a[i] += maxadd；
正向遍历数组，如果该数组中仍然出现递减，则无法通过指定操作实现目的。
for _ in range(int(input())): n = int(input()) a = list(map(int, input().split())) ok = 1 maxadd = 0 for i in range(1,n): if a[i] < a[i-1]: if i - 1 > 0 and a[i-1] < a[i-2]: ok = 0 maxadd = max(maxadd,a[i-1] - a[i]) if not ok: print("NO") else: for i in range(1,n): if a[i] < a[i-1]: a[i] += maxadd for i in range(1,n): if a[i] < a[i-1]: ok = 0 if ok: print("YES") else: print("NO")CF1101Div2B-贪心+排序
题意：
有一个长为n的蛋糕，每个位置i上的高度为ai，可执行如下操作：
将刀放在某个高度h处，从左到右扫描，如果该位置蛋糕的高度大于h，超出的部分会被推到i+1位置上，位置n上的超出部分完全脱离蛋糕
目标是对于每个位置i，只考虑前i个位置，通过上述操作能使高度达到的最大平整高度是对少？
题解：
遍历数组，计算前缀和，对于每个位置i，计算前缀平均值cur/(i+1)，维护最小的前缀平均值，第i个答案就是前i个位置的前缀平均值的最小值
for _ in range(int(input())): ans = [] n = int(input()) a = list(map(int,input().split())) cur = 0 mi = float('inf') for i,x in enumerate(a): cur += x if cur//(i+1) < mi: mi = cur//(i+1) ans.append(mi) print(*ans)CF1101Div2C1-贪心+枚举
Alice有n个朋友排队入场，派对上有x张桌子，每张桌子有s个座位。每个朋友有三种性格类型：
- I（内向型）：必须坐在一张完全空的桌子旁
- E（外向型）：必须坐在已经有人的桌子旁 （非空桌）
- A（中间型）：可以坐在任何桌子旁
朋友按固定顺序入场，Alice必须为每个人立即分配座位或拒绝入场。一旦入座就不能再移动。目标是最多能让多少人入座。
-
贪心+枚举
A型可以灵活选择，前
m个A型朋友当作I型处理，剩余当作E枚举当前有多少个A型当作E处理，模拟的过程如下： 1.维护以入座人数
ans，和已使用桌子数2.I型：若
T<t，就占用一张桌子3.E型：若当前入座人数小于总容量
ans<T*s，就可以入座4.A型：前
m个当作I型，其余当作E枚举所有可能的
m，求出最大的入座人数
def f(S,m,t,s): T = 0 ans = 0 for c in S: if c == "I": if T < t: T += 1 ans += 1 elif c == "E": if ans < T*s: ans += 1 else: if m > 0: m -= 1 if T < t: T += 1 ans += 1 else: if ans < T*s: ans += 1 return ans
for _ in range(int(input())): n,t,s = map(int,input().split()) S = input().strip() r = S.count("A") ans = 0 for i in range(r + 1): ans = max(ans,f(S,i,t,s)) print(ans)思维题
CF190Div2C-思维题
题意：
有n张牌，第n张牌有c个
选择需要从所有牌中至少取出3张将取出的牌排成圆圈满足：
任意连续的三张牌中，至少有两张牌的数字相同
求最大的取牌数
题解：
XXX1XX1XX1XXYY1YYY
对于每一个数量≥2的牌，为了包裹k个1，需要(k+1)对XX
则 x ≥ 2*(k+1)
所以其能够包裹的最大的单独为1的个数为：x//2 - 1
特殊情况：
若只有一种≥2的牌，则最大包裹个数为x//2
根据计算出的最大包裹的1个数，用总数减去该数即为答案
for _ in range(int(input())): n = int(input()) c = list(map(int,input().split())) s = sum(c) one = st = 0 for x in c: if x == 1: one += 1 else: st += x//2 - 1 if one == n - 1: st += 1 wast = max(0,one -st) if s - wast < 3: print(0) else: print(s - wast)CF1099Div2C-思维题
题意：
给定一个序列，选择一个元素进行如下操作：
1.如果所选的元素是偶数，则将其除以2
2.如果所选的元素是奇数，则将其加1
求出最小的操作次数，使得给定的序列中所有数都相等
题解：
注意到，对一个数进行上次多次操作后，该数会达到1，随后在进行操作，数在[1,2,1,2…]变换，
因此只需要保留该数在达到1之前的前缀部分即可
用一个字典reach记录数组中所有数字经过操作后得到的数字，包括两个字段：某个演变出的数字num有[went, steps]，分别代表有多少个原始数组中的元素经过操作可以到达num；所有可到达该数的总操作次数
最后比较所有went == n的情况下，最小的steps
for _ in range(int(input())): n = int(input()) a = list(map(int, input().split())) reach = {} for num in a: went_to = set() step = 0 while num not in went_to: went_to.add(num) if num not in reach: reach[num] = [1,step] else: reach[num][0] += 1 reach[num][1] += step if num%2 == 0: num //= 2 else: num += 1 step += 1 ans = float("inf") for went,step in reach.values(): if went == n and step < ans: ans = step print(ans)滑动窗口
牛客周赛145B-滑窗
给定一个01串，求该01串的子串中满足同时包含0和1的数目
由于是01串，满足题意的答案即为：总子串的数量减去单子串的数量即可
使用的f(k)函数统计字符串s中所有不同字符个数不超过k 的子串数量
from collections import defaultdictdef f(k): if k <= 0: return 0 cnt = defaultdict(int) left = 0 d = 0 ans = 0 for right in range(len(s)): c = s[right] cnt[c] += 1 if cnt[c] == 1: d += 1 while d > k: c_left = s[left] cnt[c_left] -= 1 if cnt[c_left] == 0: d -= 1 left += 1 ans += right - left + 1 return ansn = int(input())s = input().strip()ans = f(2) - f(1)print(ans)AWC65E-滑窗+双端队列
给定长度为 的整数数组 ，需要找到最长的连续子数组，使得该子数组内最大值与最小值的差 ≤ ，并且子数组长度至少为 。如果不存在，输出 -1。
题解：
使用两个单调队列分别维护窗口内的最大值和最小值
随着右指针 r 向右移动，更新两个队列
如果当前窗口内的最大值与最小值之差 > ，则移动左指针 l 缩小窗口，直到差值 ≤
每次满足差值 ≤ 时，更新答案 ans = max(ans, r - l + 1)，但只考虑长度 ≥ 的窗口
from collections import dequen,k,d = map(int,input().split())h = list(map(int,input().split()))maxq = deque()minq = deque()ans = -1l = 0for r in range(n): while maxq and h[maxq[-1]] < h[r]: maxq.pop() maxq.append(r) while minq and h[minq[-1]] > h[r]: minq.pop() minq.append(r) while maxq and minq and h[maxq[0]] - h[minq[0]] > d: if maxq[0] == l: maxq.popleft() if minq[0] == l: minq.popleft() l += 1 cur = r - l + 1 if cur >= k: ans = max(ans,cur)print(ans)差分/前缀和类
牛客周赛143D-差分+扫描线
题意：
给定一些区间与一个长度k，求使得与长度为k的区间相交的给定区间数量最多的区间数量
题解：
对于给定区间 与 相交，等价于：
即：
即：
因此，区间 能与 相交的 的范围是
每个给定区间对应一个 的可选区间 。我们要求一个点 被最多的这样的区间覆盖。
转换为一维区间最大重叠问题：给定若干区间 ，求一个点被覆盖的最大次数。
# 区间覆盖最大重叠数n,k = map(int,input().split())g = []"""给定n个区间 [l, r]，每个区间表示某个条件满足的范围求在整数点上，最多有多少个区间同时覆盖该点特殊处理：区间被扩展了，实际处理的区间是 [l-k, r]（从l-k开始，到r结束）"""for _ in range(n): l,r = map(int,input().split()) g.append((l - k,1)) g.append((r + 1,-1))g.sort()cur = 0ans = 0for _,d in g: cur += d ans = max(ans,cur)print(ans)洛谷P3078
每次可以打出从 i 到 j 的一个顺子，相当于在一段连续区间上每张牌各减 1。
目标：用最少的顺子清空所有牌。
- 每次操作给区间
[l, r]减 1 - 相当于在差分数组上
d[l] -= 1,d[r+1] += 1 - 要把原数组全部变为 0，相当于把差分数组全部变为 0
- 每次操作让一个位置 -1，另一个位置 +1
- 最少操作次数 = 所有正差分的和（每次消掉一个 +1）
n = int(input())ans = cur = 0for _ in range(n): a = int(input()) if a > cur: ans += a - cur cur = aprint(ans)CF1100Div2C2-前缀和+思维+构造
题意与C1相同，唯一不同点在于求的是操作后的最大值，值得注意的是，选择的索引必须满足ai>0才能进行反转操作，这就意味着不能像C1一样贪心的求解。
遍历每一个合法的最右侧切割点i，满足ai>0，则全局总和为：
pre = [0]*n pre[0] = abs(a[0]) for i in range(1,n): pre[i] = pre[i-1] + abs(a[i]) suf = [0]*(n+1) suf[n-1] = a[n-1] for i in range(n-2,-1,-1): suf[i] = suf[i+1] + a[i] best = suf[0] idx = -1 for i in range(1,n): if a[i] > 0: s = pre[i-1] + suf[i+1] - a[i] if s > best: best = s idx = i为什么左侧可以全部变成负数？
如果原本是负数，那么通过idx的操作，其会反转成正数
如果原本是正数，那么通过自己操作一次，就变成负数了，可以通过idx的操作变成负数
最后，通过逆序操作，找到需要进行操作的位置
ans = [] cur_a = list(a) for i in range(idx-1,-1,-1): if len(ans)%2 == 1: cur_a[i] = -cur_a[i] if cur_a[i] > 0: ans.append(i+1) ans.append(idx+1)for _ in range(int(input())): n = int(input()) a = list(map(int, input().split())) ans = [] pre = [0]*n pre[0] = abs(a[0]) for i in range(1,n): pre[i] = pre[i-1] + abs(a[i]) suf = [0]*(n+1) suf[n-1] = a[n-1] for i in range(n-2,-1,-1): suf[i] = suf[i+1] + a[i]
best = suf[0] idx = -1 for i in range(1,n): if a[i] > 0: s = pre[i-1] + suf[i+1] - a[i] if s > best: best = s idx = i if idx == -1: print("0\n") continue ans = [] cur_a = list(a) for i in range(idx-1,-1,-1): if len(ans)%2 == 1: cur_a[i] = -cur_a[i] if cur_a[i] > 0: ans.append(i+1) ans.append(idx+1) print(len(ans)) print(*ans)AWC65D-马哈顿距离+二维前缀和
题意：
- 平面上有 个商店，每个商店有坐标 和销售额 。
- 有 个配送中心候选点，每个候选点有坐标 和配送距离 （曼哈顿距离）。
- 如果商店与配送中心的曼哈顿距离 ，则该商店可被配送。
- 对每个候选点，求可配送商店的销售额总和。
题解：
曼哈顿距离的覆盖区域是一个菱形
可以通过坐标变换将其转化为矩形，使用二维前缀和快速查询。
曼哈顿距离：
令：
则：
曼哈顿距离 等价于：
因此，每个商店变换为点 ，每个候选对应矩形查询：
注意 可能为负数，需要平移（加偏移量）使其非负。
读入所有商店，计算每个商店的 ，（offset 取 1000 或更大），将销售额累加到二维数组 grid[u][v]
对 grid 做二维前缀和 pre
对于每个候选，计算矩形边界，利用前缀和 查询总和
n,m = map(int,input().split())of = 1000max_u = max_v = 2000grid = [[0]*(max_v + 5) for _ in range(max_u + 5)]for _ in range(n): x,y,c = map(int,input().split()) u = x + y v = x - y + of grid[u][v] += cpre = [[0]*(max_v + 10) for _ in range(max_u + 10)]for i in range(max_u + 5): for j in range(max_v + 5): pre[i][j] = grid[i][j] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1]for _ in range(m): p,q,k = map(int,input().split()) u0 = p + q v0 = p - q + of u1 = max(0,u0 - k) u2 = min(max_u,u0 + k) v1 = max(0,v0 - k) v2 = min(max_v,v0 + k) ans = pre[u2][v2] - pre[u1-1][v2] - pre[u2][v1-1] + pre[u1-1][v1-1] print(ans)数学类
牛客周赛143C-质因数分解
题意：
给定两个正因数x,y，记v = x * y，对于v的每个正因子d，计算d^d，并将结果累加起来，最终结果mod 10**9+7
题解：
# 分解x和y,合并质因数指数，利用合并后的质因数生成所有因子，求和MOD = 10**9 + 7
"""质因数分解： 将输入的整数num分解为质因数的乘积，返回一个字典，其中： 键：质因数 值：该质因数出现的次数，即指数 列：fc(12) 返回 {2：2，3：1} 12 = 2**2 + 3**1"""def fc(num): fa = {} # 存储质因数字典 {质数: 指数} d = 2 # 从最小的质数2开始试除
while d * d <= num: # 只需要试除到 sqrt(num) if num % d == 0: # d是num的质因数 cnt = 0 while num % d == 0: # 反复除以d，统计指数 num //= d cnt += 1 fa[d] = fa.get(d, 0) + cnt # 记录该质因数及其指数 d += 1 if d == 2 else 2 # 跳过偶数（优化） # 等价于：d = 3 if d == 2 else d + 2
if num > 1: # 如果剩余num > 1，说明它是质数 fa[num] = fa.get(num, 0) + 1
return fa
"""生成一个数的所有约数： 接收一个质因数分解字典，返回该数的所有正约束组成的列表 例：输入{2:2,3:1} 返回[1,2,4,3,6,12]"""
def get_fa(fa): res = [1] # 初始只有约数1
for p, e in fa.items(): # 遍历每个质因数p及其指数e new = [] # 存储本轮新生成的约数
for f in res: # 遍历已有的每个约数 mul = 1 # p的幂次初始为1 (p^0)
for _ in range(e + 1): # 从p^0到p^e new.append(mul * f) # 生成新约数：f × p^i mul *= p # 更新为下一个幂次
res = new # 更新约数列表
return res
x,y = map(int,input().split())fac_x = fc(x)fac_y = fc(y)for p,e in fac_y.items(): fac_x[p] = fac_x.get(p,0) + ec = get_fa(fac_x)ans = 0for d in c: ans = (ans + pow(d,d,MOD))%MODprint(ans)DP类
牛客周赛146D-子序列DP
题意：
给定一个由数字构成的字符串，计算该字符串中有多少个子序列满足：将该子序列转化为10进制数，该十进制数是6的倍数
题解：
DP定义：
dp[r]表示处理到当前位置时，所有已构造的非空子序列中，数值模6等于r的结果
DP初始化：
dp = [0,0,0,0,0,0]
DP状态转移方程：
对于当前处理的数字d，新的DP值ndp由以下三部分组成：
1.不选当前字符：ndp[r] = dp[r]
2.新建只包含当前字符的子序列：ndp[d%6] += 1
3.将当前字符追加到已有子序列末尾：对于每个r∈(0,1,2,3,4,5,6)：ndp[(r*10 + d)%6] = ndp[(r*10 + d)%6] + dp[r]
MOD = 998244353n = int(input())s = input().strip()dp = [0] * 6ans = 0for ch in s: d = int(ch) ndp = dp[:] ndp[d % 6] = (ndp[d % 6] + 1) % MOD for r in range(6): nr = (r * 10 + d) % 6 ndp[nr] = (ndp[nr] + dp[r]) % MOD dp = ndpprint(dp[0] % MOD)力扣940-子序列DP
题意：
给定一个字符串 s，计算 s 的 不同非空子序列 的个数。因为结果可能很大，所以返回答案需要对 10^9 + 7** 取余** 。
字符串的 子序列 是经由原字符串删除一些（也可能不删除）字符但不改变剩余字符相对位置的一个新字符串。
- 例如，
"ace"是"***a***b***c***d***e***"的一个子序列，但"aec"不是。
class Solution: def distinctSubseqII(self, s: str) -> int: MOD = 10**9 + 7 dp = [0] * 26 # dp[c]表示以字符c结尾的子序列数 ans = 0 for ch in s: idx = ord(ch) - ord('a') # 新增子序列 = 之前总数 + 1（单独选当前字符） - 之前以ch结尾的 new = (ans + 1 - dp[idx]) % MOD dp[idx] = (dp[idx] + new) % MOD ans = (ans + new) % MOD return ans力扣1978-子序列DP
题意：
给你一个二进制字符串binary。binary的一个 子序列如果是 非空的且没有 前导0（除非数字是 "0"本身），那么它就是一个 好 的子序列。
请你找到binary不同好子序列 的数目。
- 比方说，如果
binary = "001"，那么所有 好子序列为["0", "0", "1"]，所以 不同的好子序列为"0"和"1"。 注意，子序列"00"，"01"和"001"不是好的，因为它们有前导 0 。
请你返回binary中不同好子序列的数目。由于答案可能很大，请将它对109 + 7取余 后返回。
一个 子序列 指的是从原数组中删除若干个（可以一个也不删除）元素后，不改变剩余元素顺序得到的序列。
class Solution: def numberOfUniqueGoodSubsequences(self, binary: str) -> int: MOD = 10**9 + 7 end0 = 0 # 以0结尾的子序列数 end1 = 0 # 以1结尾的子序列数 has0 = 0 # 是否存在单独的'0' for ch in binary: if ch == '0': end0 = (end0 + end1) % MOD # 在已有子序列后加0 has0 = 1 else: end1 = (end0 + end1 + 1) % MOD # +1是单独选'1' return (end0 + end1 + has0) % MOD洛谷P2758-线性DP
题意：
设 和 是两个字符串。我们要用最少的字符操作次数，将字符串 转换为字符串 。这里所说的字符操作共有三种：
- 删除一个字符；
- 插入一个字符；
- 将一个字符改为另一个字符。
均只包含小写字母。
题解：
A = input().strip()B = input().strip()
lenA, lenB = len(A), len(B)
# dp[i][j]: A的前i个字符转换为B的前j个字符的最少操作次数dp = [[0] * (lenB + 1) for _ in range(lenA + 1)]
# 初始化for i in range(lenA + 1): dp[i][0] = i # 删除i次for j in range(lenB + 1): dp[0][j] = j # 插入j次
# 状态转移for i in range(1, lenA + 1): for j in range(1, lenB + 1): if A[i - 1] == B[j - 1]: dp[i][j] = dp[i - 1][j - 1] # 字符相同，无需操作 else: dp[i][j] = min( dp[i - 1][j] + 1, # 删除 dp[i][j - 1] + 1, # 插入 dp[i - 1][j - 1] + 1 # 替换 )
print(dp[lenA][lenB])CF190Div2B-线性DP
题意：
给定一个仅包含1~4的字符串s，求删掉的最小个数，使得按顺序从s中获取长度为2的子序列拼成的数字不能被4整除
题解：
显然的原字符串中4是必须删去的
此外，能被4整除的序列还有12和32
设计dp13和dp2
遍历字符c，如果字符为'2'，那么当前字符只能加到'2'后面，dp2 += 1;如果字符为'3'或者'1'，那么该字符可以加到'2'后面，也可以加到'1，3'后面，取二者的最大值：dp13 = max(dp2,dp3) + 1
那么剩下的最大的合法长度就是max(dp13,dp2)
CF1101Div2C1-线性DP
一、状态设计
我们只需要追踪两个关键信息：
- 多少张桌子被占用了（至少有1人的桌子数）
- 总共入座了多少人 这两个信息足够我们判断：
- I型能否入座：看是否还有空桌（j < x）
- E型能否入座：看是否有非空桌（j > 0）且还有空位（seated < j*s） 状态定义
dp[i][j] = 处理完前i个人后，恰好有j张桌子被占用时，最大入座人数i：自然维度，表示处理到第几个人j：关键约束维度。桌子数有限，且I型必须开新桌，所以桌子占用数是核心瓶颈- 值存储”最大入座人数”：在相同(i,j)下，入座人数越多越好，因为多一个人就多一个满足条件的机会（尤其是对E型，需要有人坐在桌旁）
- i：0到n（最多3000）
- j：0到x（最多3000）
- 总共最多9×10^6个状态 二、初始化与最终答案
dp[0][0] = 0 # 初始状态：0个人，0张桌子被占用，入座0人# 其他状态初始化为-1（不可达）三、状态转移方程
对于第i个人（字符为c），已知前i-1人的状态dp[i-1][j] = seated：
基础操作：拒绝
dp[i][j] = max(dp[i][j], seated)拒绝永远可行，桌子占用数和入座人数都不变。
Case 1: I型（内向者）
只能开新桌，否则拒之门外：
if j < x: # 还有空桌 dp[i][j+1] = max(dp[i][j+1], seated + 1)- 桌子占用数+1
- 入座人数+1 Case 2: E型（外向者） 只能坐非空桌，需要两个条件：
if j > 0 and seated < j * s: # 有非空桌且有剩余座位 dp[i][j] = max(dp[i][j], seated + 1)j > 0：至少有一张桌子被占用（存在非空桌）seated < j * s：已入座人数 < 这些桌子的总容量（还有空位） 为什么不需要知道具体哪张桌有空位？ 贪心性质：只要seated < j*s，就一定有至少一张桌子未满。因为j张桌子总容量为j*s，人数少于总容量，根据鸽巢原理，至少有一张桌子有空位。
Case 3: A型（中间者）
两种选择，取最优：
# 选择1: 当作I型，开新桌if j < x: dp[i][j+1] = max(dp[i][j+1], seated + 1)
# 选择2: 当作E型，坐非空桌if j > 0 and seated < j * s: dp[i][j] = max(dp[i][j], seated + 1)A型的灵活性体现在这里——DP自动选择能导致更优最终结果的选项。
ans = max(dp[n]) # 处理完所有人后，取所有可能桌子占用数下的最大入座人数t = int(input())for _ in range(t): n, x, s = map(int, input().split()) S = input().strip() dp = [[-1] * (x + 1) for _ in range(n + 1)] dp[0][0] = 0 for i in range(1, n + 1): c = S[i - 1] for j in range(x + 1): if dp[i - 1][j] == -1: continue seated = dp[i - 1][j] # 拒绝当前人（总是可选） dp[i][j] = max(dp[i][j], seated)
if c == 'I': # 必须坐空桌：需要有空桌子 if j < x: dp[i][j + 1] = max(dp[i][j + 1], seated + 1)
elif c == 'E': # 必须坐非空桌： # 条件1: 有非空桌 (j > 0) # 条件2: 非空桌还有空位 (seated < j*s) if j > 0 and seated < j * s: dp[i][j] = max(dp[i][j], seated + 1)
else: # 选项1: 开新桌 if j < x: dp[i][j + 1] = max(dp[i][j + 1], seated + 1) # 选项2: 坐非空桌 if j > 0 and seated < j * s: dp[i][j] = max(dp[i][j], seated + 1)
ans = max(dp[n]) print(ans)子串序列类问题
ABCG-最长上升子序列
题意：
我们有 个事件 。
一个机器人可以先后收集两个事件 和 （假设 ）当且仅当它们满足“速度约束”：
也就是说，机器人在时间差内最多移动距离不超过时间差。
把这一条件改写，引入变量
则上述条件等价于（设 ）：
因此，能被同一个机器人收集的事件，在 坐标系下，必须具有两维都不减小的偏序关系。
题解：
**偏序集与 **Dilworth 定理
我们把每个事件抽象成一个点 ，并定义偏序关系：
我们要找的是最少的单调链，这种链中元素全都可以被同一个机器人按照时间顺序收集
Dilworth 定理：
最小链划分的大小 = 最长反链的大小
反链是集合中任意两点不可比较的集合，即对于任意两点 ，不能同时满足 。
在二维平面上按 坐标排序后，反链在 坐标上一定是严格递减的。
如果 且 ，那么它们就是可比较的（自然可以放在同一条链中），这就不属于反链。
因此，要构成反链，当 递增时， 必须严格递减。
最长反链的长度 = 最长严格递减子序列（** 坐标）的长度**
如果 ，那么除非 （不可能，因为 不同），否则它们 。
如果 相同且 不同，那么它们的 不同，但无论如何，它们的时间 不一定相同。
因此，当 相同时，先按 降序排序，可使相同 的点不会错误地构成一条链，因为这时 递减，不会满足 的要求。
由此得出求最大反链 = 最长严格递减子序列
按 升序、 相同时按 降序排序后，原偏序关系变成：
要两点可比，必须同时满足 递增且 递增（因为相同的 我们已经按 降序安排，它们之间无法再形成 递增）。
于是，任何一个反链在这样的排序下就是 严格递减的子序列。
import sysimport bisectinput = sys.stdin.readlinen = int(input())a = []for _ in range(n): t, x = map(int, input().split()) a.append((x + t, x - t))a.sort(key=lambda p: (p[0], -p[1]))b = [p[1] for p in a]res = []for b in b: pos = bisect.bisect_left(res, b) if pos == len(res): res.append(b) else: res[pos] = bprint(len(res))力扣52-最大子数组和-①DP②贪心
题意：
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
题解：
class Solution: def maxSubArray(self, nums: List[int]) -> int: cur = nums[0] ans = nums[0] for x in nums[1:]: cur = max(x,cur+x) if cur > ans: ans = cur return ansclass Solution: def maxSubArray(self, nums: List[int]) -> int: f = [0]*len(nums) f[0] = nums[0] for i in range(1,len(nums)): f[i] = max(f[i-1],0) + nums[i] return max(f)力扣152-乘积最大子数组-DP
题意：
给你一个整数数组 nums，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个32-位 整数。
请注意，一个只包含一个元素的数组的乘积是这个元素的值。
题解：
class Solution: def maxProduct(self, nums: List[int]) -> int: n = len(nums) fmin = [0]*n fmax = [0]*n fmax[0] = fmin[0] = nums[0] for i in range(1,len(nums)): x = nums[i] fmax[i] = max(fmax[i-1]*x,fmin[i-1]*x,x) fmin[i] = min(fmin[i-1]*x,fmax[i-1]*x,x) return max(fmax)力扣918-环形子数组最大和
题意：
给定一个长度为 n 的环形整数数组nums，返回*nums的非空 子数组 的最大可能和* 。
环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i]的前一个元素是 nums[(i - 1 + n) % n] 。
子数组 最多只能包含固定缓冲区nums中的每个元素一次。形式上，对于子数组nums[i], nums[i + 1], ..., nums[j]，不存在i <= k1, k2 <= j其中k1 % n == k2 % n 。
题解：
class Solution: def maxSubarraySumCircular(self, nums: List[int]) -> int: n = len(nums) max_ = -inf pre = 0 for i in range(n): pre = max(0,pre) + nums[i] max_ = max(max_,pre) if max_ < 0: return max_ pre = 0 min_ = inf for i in range(n): pre = min(0,pre) + nums[i] min_ = min(pre,min_) return max(max_,sum(nums) - min_)力扣1749-子数组绝对值和的最大值
题意：
给你一个整数数组nums。一个子数组[numsl, numsl+1, ..., numsr-1, numsr]的 和的绝对值为abs(numsl+ numsl+1+ ... + numsr-1+ numsr) 。
请你找出 nums中 和的绝对值 最大的任意子数组（可能为空），并返回该 最大值 。
abs(x) 定义如下：
- 如果
x是负整数，那么abs(x) = -x。 - 如果
x是非负整数，那么abs(x) = x。
题解：
class Solution: def maxAbsoluteSum(self, nums: List[int]) -> int: ans = fmax = fmin = 0 for x in nums: fmax = max(fmax,0) + x fmin = min(fmin,0) + x ans = max(ans,fmax - fmin) return ans洛谷1714-带长度限制的最大子段和
题意：
有 块蛋糕，每块有美味度 （可能为负）。要求选出一段**长度不超过 ** 的连续蛋糕，使得美味度之和最大。
题解：
这是带长度限制的最大子段和问题，需要用到前缀和 + 单调队列。
设前缀和 ，则区间 的和 = 。
对于固定的右端点 ，要最大化 ，其中 ，即 。
转化为：对于每个 ，在窗口 内找到最小的前缀和，然后用 减去它。
- 计算前缀和 ，其中
- 维护一个单调递增队列，存储前缀和的索引，队首是窗口内的最小值
- 遍历 从 1 到 ：
- 如果队首索引 < ，弹出（滑出窗口）
- 当前最大子段和 =
- 将 入队，保持队列单调递增
from collections import dequen,m = map(int,input().split())a = list(map(int,input().split()))pre = [0]*(n+1)for i in range(1,n+1): pre[i] = pre[i-1] + a[i-1]q = deque()q.append(0)ans = -10**18for r in range(1,n+1): while q and q[0] < r - m: q.popleft() ans = max(ans,pre[r] - pre[q[0]]) while q and pre[q[-1]] >= pre[r]: q.pop() q.append(r)print(ans)力扣516-最长回文子序列
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
class Solution: def longestPalindromeSubseq(self, s: str) -> int: # n = len(s) # dp = [[0]*n for _ in range(n)] # for i in range(n-1,-1,-1): # dp[i][i] = 1 # for j in range(i+1,n): # if s[i] == s[j]: # dp[i][j] = dp[i+1][j-1] + 2 # else: # dp[i][j] = max(dp[i+1][j],dp[i][j-1]) # return dp[0][-1] @cache def dfs(i,j): if i > j: return 0 if i == j: return 1 if s[i] == s[j]: return dfs(i+1,j-1) + 2 return max(dfs(i+1,j),dfs(i,j-1)) return dfs(0,len(s) - 1)图类
力扣547-判断连通块的数量DFS
题意：
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
题解：
class Solution: def findCircleNum(self, a: List[List[int]]) -> int: n = len(a) vis = [False]*n def dfs(i): vis[i] = True for j in range(n): if a[i][j] and not vis[j]: dfs(j) ans = 0 for i,x in enumerate(vis): if x: continue ans += 1 dfs(i) return ans力扣1971-判断路径是否可达DFS+BFS
class Solution: def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool: # g = [[] for _ in range(n)] # for x,y in edges: # g[x].append(y) # g[y].append(x) # vis = [False]*n # def dfs(i): # if i == destination: # return True # vis[i] = True # for j in g[i]: # if not vis[j]: # if dfs(j): # return True # return False # return dfs(source) if source == destination: return True g = [[] for _ in range(n)] for x,y in edges: g[x].append(y) g[y].append(x) vis = [False]*n q = deque() q = [source] vis[source] = True for u in q: for v in g[u]: if v == destination: return True if not vis[v]: vis[v] = True q.append(v) return False力扣797-所有可能的路径
给你一个有n个节点的 有向无环图（DAG），请你找出从节点 0到节点 n-1的所有路径并输出（不要求按特定顺序）
graph[i]是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点graph[i][j]存在一条有向边）。
class Solution: def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]: n = len(graph) ans = [] path = [0] def dfs(i): if i == n -1: ans.append(list(path)) return for j in graph[i]: path.append(j) dfs(j) path.pop() dfs(0) return ans