算法竞赛 Classic Tricks 复习笔记#
A. 任意 n≥2 都能由 2 和 3 凑出#
使用场景#
- 区间/长度要拆成若干段,每段长度只能取 2 或 3。
- 构造题中需要证明所有 n≥2 都可写成 2x+3y,其中 x,y≥0。
- 原题出现“2 和 3 的倍数组合”时,先把它化成非负整数解问题。
核心结论#
对任意整数 n≥2,都存在 x,y≥0 使
n=2x+3y.若 n 为偶数,取 x=n/2,y=0;若 n 为奇数,则 n≥3,先取一个 3,剩下 n−3 为偶数。
B. Kruskal 瓶颈在排序时不如直接枚举值域#
使用场景#
- 边权值域很小(如 [0,W],W≤106),但边数很多(m 很大)。
- 图由隐式规则生成,值域有限但边数是 O(n2) 级别。
- 需要最小生成树,且排序成本 O(mlogm) 超过 O(n+W) 枚举。
核心观察#
Kruskal 真正要求的是“按边权从小到大处理”,不一定非要比较排序。若边权值域 W 很小,并且能把显式边按权值桶化,或能直接生成某个权值的候选边,就可以从小到大枚举权值并做并查集合并。
显式边桶化时,排序部分可由 O(mlogm) 降到 O(m+W);若图是隐式生成的,还必须把“生成当前权值的候选边”的复杂度一起算进去,不能仅凭值域小就自动省掉 O(n2) 条边。
C. 固定 K 的乘除 → 考虑 K 进制#
使用场景#
- 问题中存在某个固定常数 K,元素需要乘以 K 或除以 K。
- 操作反复作用在同一数上,或需要统计”乘了多少次 K”。
- 权重/贡献与 K 的幂次有关,或题目本质是”进位/借位”。
核心观察#
若有固定的 K,则“乘 K”对应 K 进制左移一位;当当前数能被 K 整除时,“除 K”对应右移一位。若题目使用整数除法,还要单独处理被舍去的最低位。
因此看到反复乘/除固定 K,可以把数拆成 K 进制各位,检查操作是否变成移位、进位或按位独立处理。
D. BFS 遍历所有状态求最值#
使用场景#
- 状态空间有限,且每次转移代价均为 1(或均匀),问最短步数/最大/最小值。
- 问题看似需要 DP 或搜索,但状态之间无拓扑序或转移顺序不固定。
- 需要求”从所有合法起点出发能到达哪些状态的最小距离”,多源 BFS。
核心观察#
这里的重点不是“BFS 能直接求任意最值”,而是:BFS 也可以只是一个状态枚举器。
当状态空间有限,并且每个状态只需被处理一次时,可以从初始状态 BFS,把所有可达状态遍历出来;若目标是“所有可达状态自身的最大/最小属性”,遍历时直接统计即可。多源 BFS 则可同时从所有起点出发,得到到最近起点的最短距离。
E. 两物性价比与数量上界#
使用场景#
- 有两类物品,各有价值 vi 与价格 pi(i=1,2),要以最低总价达到总价值 ≥V。
- 背包类题目中物品只有两种,或可以把所有物品归类成”性价比高”与”性价比低”两组。
- 需要证明最优解中某类物品的数量有上界。
核心结论#
设两类物品价值/价格分别为 (v1,p1)、(v2,p2),且物品 1 的单位价值成本不高于物品 2:
v1p1≤v2p2.令 g=gcd(v1,v2)。若物品 2 买了至少 v1/g 个,可以把其中 v1/g 个物品 2 替换成 v2/g 个物品 1:两边提供的价值完全相同,而替换后的总价不会更高。因此一定存在一个最优解满足
0≤x2<gv1.所以可以枚举性价比较低的物品数量,再用高性价比物品补足目标价值。原文“性价比低的数量不会买超过性价比更高的价值”记录的就是这种交换上界思想;具体上界必须由题目参数证明,不能凭性价比直接猜。
F. 序列中移动元素 → 观察 ai±i#
使用场景#
- 序列中可以将某个元素向左或向右移动若干步,移动代价与移动距离(下标差)有关。
- 要把一组元素移动到某些目标位置,使总移动距离最小。
- 元素相对顺序不变(或只考虑某个元素),操作等价于调整下标。
核心观察#
当表达式里同时出现“值 ai”和位置差 ∣i−j∣ 时,先按左右关系拆绝对值。例如
ai+∣i−j∣={(ai−i)+j,(ai+i)−j,i≤j,i>j.于是所有与 i 有关的部分只剩 ai−i 或 ai+i。这经常能把“值 + 移动距离”拆成前缀/后缀最值问题。
常见触发式:ai±∣i−j∣、∣ai−aj∣+∣i−j∣、需要同时比较数值与位置的最值式。原文只记录了“观察 ai±i”这个触发器;具体操作是否真的形成不变量,必须针对题目另证。
G. 二进制位运算律速查#
位运算逐位独立,因此很多恒等式只需在单个 bit 的 0/1 情况下验证。
使用场景#
- 题目涉及位掩码、子集枚举、按位统计。
- 需要把 XOR/AND/OR 的前缀和或区间查询转化成等价形式。
- 推导某个位运算组合是否满足分配律,或需要把补集写成 XOR。
G-1. XOR(异或)#
- 交换律:a⊕b=b⊕a
- 结合律:(a⊕b)⊕c=a⊕(b⊕c)
- 单位元:a⊕0=a
- 自反:a⊕a=0
- 消去:a⊕b⊕b=a
- 因而前缀异或可直接还原区间:al⊕⋯⊕ar=prer⊕prel−1
G-2. AND / OR#
- 交换律:a&b=b&a,a∣b=b∣a
- 结合律:(a&b)&c=a&(b&c),OR 同理
- 幂等:a&a=a,a∣a=a
- 零元/单位元:a&0=0,a∣0=a
- 吸收律:a∣(a&b)=a,a&(a∣b)=a
AND 与 OR 互相满足分配律:
a&(b∣c)=(a&b)∣(a&c),a∣(b&c)=(a∣b)&(a∣c).固定掩码的 AND 对 XOR 也满足分配律:
(a⊕b)&m=(a&m)⊕(b&m),因此
(i∈S⨁ai)&m=i∈S⨁(ai&m).直观上,m 只是逐位过滤器:mi=0 时该位统一清零,mi=1 时原样保留 XOR。
G-3. NOT 与德摩根律#
在固定 B 位范围、MASK=2B−1 时,可把补集写成 a=a⊕MASK。
a&b=a∣b,a∣b=a&b.C++ 的 ~a 会翻转整数类型的全部位;只关心低 B 位时记得再 & MASK。
G-4. 竞赛常用恒等式#
- 判第 k 位:
(x >> k) & 1
- 置第 k 位:
x |= 1LL << k
- 清第 k 位:
x &= ~(1LL << k)
- 翻转第 k 位:
x ^= 1LL << k
- 最低位的 1:
lowbit(x) = x & -x
- 删除最低位的 1:
x &= x - 1
- 判断 x 是否为 2 的幂:
x > 0 && (x & (x - 1)) == 0
- 低 k 位掩码:
(1LL << k) - 1(注意 k 不能等于类型位宽)
- 枚举非空子掩码:
for (int s = mask; s; s = (s - 1) & mask)
G-5. 常见转化#
- XOR 前缀和:xor(l,r)=prer⊕prel−1。
- 只关心掩码 m 中的位:可以先做
a[i] & m 再 XOR,因为 AND 对 XOR 线性。
- 要求
mask 的所有 1 都包含在 x 中:(x & mask) == mask。
- 要求 x 的所有 1 都属于
mask:(x & mask) == x。
[!warning] 不要错误推广
OR 不对 XOR 满足类似分配律。例:a=0,b=0,m=1,(a∣m)⊕(b∣m)=0,但 (a⊕b)∣m=1。
移位等价于乘除 2k 只应在无溢出、且右移对象非负等条件下使用。
H. 质数与质因子:108 值域结论#
使用场景#
- 题目值域不超过 108,需要判素、分解质因子、或枚举约数。
- 需要对某个 n 的所有互质计数(容斥),或枚举无平方因子约数。
- 出现
gcd 边权,怀疑可用中间质数构造权值为 1 的边。
- 题目要求枚举 n 附近的质数,或判断”所有质因子都大于 104”。
H-1. 判定与筛法的边界#
- 若 n≤108 为合数,则它一定有一个不超过 n≤104 的质因子。因此单次试除只需检查到 104。
- 104 以内共有 1229 个质数。先筛出这些质数后,单次分解 n≤108 最多试除 1229 次,而不必枚举所有整数。
- 108 以内共有 5761455 个质数,最大质数是 99999989。
- 若要回答大量区间质数问题,埃氏筛的时间复杂度为 O(NloglogN),普通
bool/uint8_t 标记约占 N 字节;只存奇数可把空间减半。
- 单个 32 位整数的判素也可使用确定性 Miller—Rabin;但在 108 内,试除或预筛通常更短且常数稳定。参见 Miller Rabin算法、欧拉筛法(线性筛)。
[!tip] 平方根写法
用 1LL * p * p <= n,避免 p * p 在更大值域中发生 int 溢出。分解结束后若 n > 1,剩余部分本身就是一个质因子。
H-2. 不同质因子个数很少#
令 ω(n) 表示 n 的不同质因子个数。为了在固定值域内让 ω(n) 最大,应依次乘最小的不同质数:
2⋅3⋅5⋅7⋅11⋅13⋅17⋅19=9699690≤108,但
9699690⋅23=223092870>108.因此
n≤108⟹ω(n)≤8.直接推论:
- 枚举不同质因子的所有子集至多 28=256 个状态;
- 用容斥统计区间内与 n 互质的数,复杂度可视为常数;
- 若只需要无平方因子约数、莫比乌斯式容斥项,同样最多枚举 256 项。
对 n 的不同质因子集合 P,[1,x] 内与 n 互质的数可写为
C(x)=S⊆P∑(−1)∣S∣⌊∏p∈Spx⌋.区间 [l,r] 的答案为 C(r)−C(l−1)。
H-3. 质因子总数、因子个数与枚举规模#
- 令 Ω(n) 计重数。由于 226=67108864≤108<227,故 Ω(n)≤26。
- 108 内约数个数的最大值为 768,例如 73513440 达到该值。因此对单个数直接枚举全部约数通常足够快。
- 枚举因数对只需循环到 n≤104;发现 d∣n 时同时处理 d 与 n/d,平方数需避免重复。
- 质因数分解后,约数个数为 τ(n)=∏i(ei+1),欧拉函数为 φ(n)=n∏i(1−1/pi)。两者都只依赖分解结果,适合一次分解后集中计算。
H-4. 质数间隔可把”大值域”压成”小尾段”#
在明确值域上界时,相邻质数间隔可作为竞赛中的小常数,但必须区分”严格结论”和”拍脑袋常数”。
- 在 107 内,相邻质数的最大间隔为 154;在 108 内最大间隔为 220。
- 因而在 x≤108 时,向前或向后寻找附近质数,保守扫描约 220 个连续整数即可覆盖内部完整质数间隔;靠近值域端点时仍需显式处理边界。
- 这适合把区间拆成”大段统一计数 + 质数附近小尾段 DP/暴力”。例如边权为 gcd(u,v) 时,夹在两点之间且不整除端点的质数能提供两条权值为 1 的边,从而把最短路封顶为 2。
[!warning] 使用条件
“中间有质数”不自动推出两条边的 gcd 都是 1。若质数 p 小于端点 v,仍可能有 p∣v。证明中应排除该情形、另选质数,或把同一小质数间隔交给暴力/DP。
H-5. 常见建模触发器#
- 题目出现”与固定 n 互质的区间计数”:分解 n 的不同质因子,做至多 256 项容斥。
- 题目出现”寻找 x 附近的质数”且 x≤108:试除判素配合小范围扫描通常已经足够。
- 题目出现”所有质因子都大于 104“且数不超过 108:该数只能是 1 或质数,不可能含两个大于 104 的质因子。
- 题目出现
gcd 边权且允许向更大的整数跳转:尝试用中间质数制造权值 1 的边,再单独处理质数间隔内的短尾部。
- 题目要求枚举 n 的无平方因子约数:只枚举不同质因子子集,不必生成全部约数。
I. 自由构造模数:同余 → 整除取差#
使用场景#
- 题目要求输出一个模数 m,使得某个关系 a≡b(modm) 成立。
- 题目允许”任意合法解均可”,模数不是固定输入。
- 看到”输出一个数使得……在模该数意义下……”。
I-1. 触发器#
题目要求构造某个模数 m,并满足:
a≡b(modm)或者:
f(x)≡y(modm)且 m 不是输入固定的,而是允许自己输出。
这时不要急着做同余方程或二次剩余判定,先把同余翻译成整除:
a≡b(modm)⟺m∣a−b既然 m 可以自己选,若 a=b,最直接可以取
m=∣a−b∣,或者取 ∣a−b∣ 的某个正因子。若 a=b,这条同余对任意合法正模数都成立,再按题目的范围条件选 m 即可。
I-2. 核心想法#
如果模数由我们构造,那么我们可以反过来制造一个”必然成立”的模关系。
常见模板:
f(x)≡y(modm)等价于:
m∣f(x)−y若 f(x)=y,可令
m=∣f(x)−y∣.这条同余就直接成立;若 f(x)=y,任意合法正模数都满足它。之后仍要检查题目对 m 的范围、大小、互异性等额外限制。
[!tip] 赛时提醒
看到”输出一个模数 / 输出一个数作为模数 / 任意合法解均可”,优先把同余改写成整除。自由变量不要拿来猜,拿来消掉约束。
相关:抽象代数、Miller Rabin算法
J. LogTrick:固定端点压缩区间运算状态#
适用:区间运算满足结合律,并且固定一端后,累计值只会沿某个方向收缩/扩张。典型是 gcd、LCM、按位 AND、按位 OR。
固定右端点 r,看所有
f(l,r)=al∘al+1∘⋯∘ar,l=r,r−1,…,1.虽然左端点有 O(n) 个,但不同的 f(l,r) 往往只有 O(logV) 个,因此可以把连续产生同一结果的一批左端点合并成一个状态。
使用场景#
- 看到”所有子数组的 GCD / AND / OR / 有界 LCM”。
- 固定右端点后,区间值只会变小(GCD、AND)或变大(LCM、OR)。
- 要统计满足某个区间运算结果等于 K 的子数组个数。
- n 很大,显然不能枚举 O(n2) 个区间,但值域只有 30/60 位。
J-1. 为什么状态数是对数级#
- GCD:若新值变小,则它是旧值的真因数,因此至少减半:
gnew∣gold,gnew<gold⟹gnew≤2gold.所以从 V 开始最多严格变化 O(logV) 次。
- LCM:若新值变大,则旧值整除新值,因此至少翻倍:
Lold∣Lnew,Lnew>Lold⟹Lnew≥2Lold.实际使用时通常设上界 U 或要求最终整除目标 K。超过上界后直接截断,否则状态数也是 O(logU)。
- AND:向区间里加入元素后,二进制位只会 1→0。
- OR:向区间里加入元素后,二进制位只会 0→1。
若有效位数为 B,每次值改变至少翻转一个尚未翻转过的 bit,因此不同值最多 B+1 个。
J-2. 最稳的 Rolling Vector 写法#
不要纠结”最远左端点”方向,直接维护 (value,count):表示以当前 r 结尾时,有多少个左端点得到这个 value。
vector<pair<long long, long long>> cur;
for (int r = 0; r < n; ++r) {
vector<pair<long long, long long>> nxt;
nxt.push_back({a[r], 1}); // 区间 [r,r]
for (auto [v, cnt] : cur) {
long long nv = std::gcd(v, a[r]); // 可换成 &, |, lcm
if (!nxt.empty() && nxt.back().first == nv)
nxt.back().second += cnt;
nxt.push_back({nv, cnt});
为什么只需要合并相邻相同值:上一轮状态已经按左端点远近排好,加入同一个 ar 后,GCD / AND / OR / 有界 LCM 的变化仍保持单调,因此相同结果会连续出现。
总状态数每轮只有 O(logV),所以总复杂度通常是
O(nlogV).GCD 还要乘上一次 gcd 的常数/对数代价,但竞赛里通常很小。
J-3. 常见用途#
- 统计所有子数组能得到多少种不同 GCD / AND / OR:每个 r 枚举
cur,扔进全局 set。
- 统计满足 f(l,r)=K 的子数组个数:若某状态 (K,cnt),答案直接加 cnt。
- 求区间运算结果最接近 K:每轮只检查 O(logV) 个状态。
- 最短区间 LCM =K:先把不是 K 因子的元素当断点;更新 LCM 后若不再整除 K,该状态直接删除。
J-4. LCM 溢出保护#
计算
lcm(a,b)=gcd(a,b)a⋅b必须先除后乘。若只关心不超过上界 U,设
x=gcd(a,b)a.乘之前判断
J-5. ST 表 + 二分跳跃#
另一种写法是先用 ST 表支持静态区间 GCD / AND / OR 查询。
固定左端点 l,当前区间值为 v。由于结果沿右端点单调变化,可以二分找到满足
f(l,x)=v的最远位置 x,然后从 x+1 开始处理下一个不同值。
若区间查询 O(1),枚举一个固定端点的全部不同状态约为
O(logVlogn).这种写法适合需要直接找”下一次值变化位置”或配合离线区间查询的题;单纯扫全部子数组时通常 Rolling Vector 更短。
J-6. 赛时触发器#
看到下面这些特征就想 LogTrick:
- “所有子数组的 GCD / AND / OR”
- “固定右端点后,区间值只会变小/变大”
- “要求统计某个区间运算结果等于 K”
- ”n 很大,显然不能枚举 O(n2) 个区间,但值域只有 30/60 位”
一句话:固定一个端点,把连续产生同一运算结果的左端点压成一个状态;状态数靠因数链或 bit 单调性压到 O(logV)。
K. 网格图 Hamilton 路径 / 回路:先看黑白染色#
使用场景#
- 二维网格要求“一笔走完所有格子”、每格恰好经过一次。
- 判断某两个指定端点之间能否存在 Hamilton 路径。
- 网格删点、加边、加障碍后,需要先做快速无解判定。
- 构造 Hamilton 回路/路径前,先检查奇偶性和黑白点数量。
K-1. 网格天然是二分图#
对格点 (x,y) 按
c(x,y)=(x+y)mod2黑白染色。任意网格边都使 x+y 的奇偶性翻转,因此每条边一定连接异色点。
所以任何路径颜色都严格交替:
B→W→B→W→⋯这给 Hamilton 问题提供了最便宜也最常用的必要条件。
K-2. 黑白点数量#
设 (1,1) 为黑点。
∣VB∣=∣VW∣=2nm.∣VB∣=2nm+1,∣VW∣=2nm−1.即黑点恰好多一个。
K-3. Hamilton 回路#
二分图中的任意环长度必为偶数,所以 Hamilton 回路必须满足
∣VB∣=∣VW∣.对于完整矩形网格 Pn×Pm:
存在 Hamilton 回路 ⟺n,m≥2 且 nm 为偶数。
必要性来自二分图黑白平衡以及单行/单列无法成环;充分性可用标准蛇形构造。
若其中一维为偶数,例如 n 为偶数,可以保留第一列作为“回边通道”,其余部分蛇形扫描,最后沿边界回到起点。
赛时记忆:
矩形完整网格要成 Hamilton 环:不能是一条链,并且总格子数必须是偶数。
K-4. Hamilton 路径的端点颜色#
Hamilton 路径经过 nm 个点,有 nm−1 条边。
nm 为偶数#
路径长度为奇数,首尾颜色必须不同:
c(s)=c(t).也就是一个黑点、一个白点。
nm 为奇数#
路径长度为偶数,首尾颜色相同;同时因为黑点比白点多一个,所以若 (1,1) 为黑点,则必须
c(s)=c(t)=0.即两个端点都必须取多数色。
[!warning] 颜色条件通常只是必要条件
对“指定任意两个端点”的矩形网格 Hamilton 路径,除了颜色相容,还可能受到窄网格、边界位置、割结构等限制。竞赛中除非已经有对应定理或构造证明,否则不要直接把“颜色满足”当成充分条件。
所谓 Hamilton-laceable,强调的是二分图中颜色相容的两端点之间总能找到 Hamilton 路径。矩形网格的精确端点可行性有额外边界条件,做题时更实用的是:先用染色秒掉不可能,再针对剩余情况构造或 DP。
K-5. 删点 / 加边时的快速判定#
删点后想成 Hamilton 回路#
先统计剩余黑白点:
∣VB′∣=∣VW′∣⟹一定无解.但
∣VB′∣=∣VW′∣只是必要条件,不保证一定存在回路;障碍可能造成割点、死角或局部不可连通。
带障碍、规模较小的网格 Hamilton 回路通常考虑:
- 轮廓线 DP / 插头 DP;
- 状压 DP;
- 根据题目特殊形状做构造。
完美匹配、最大流可以提供额外必要条件或辅助建模,但一般不能单独判定 Hamilton 回路存在性。
奇数网格额外加一条边#
原图黑点比白点多 1。若想形成经过全部点的 Hamilton 回路,回路中必须“补偿”一次颜色交替被打破。
因此新增边若仍然是黑白边,整体仍保持二分图,奇数个顶点不可能形成 Hamilton 环。
若有希望,新增边必须是同色边;在 (1,1) 为黑色的标准染色下,尤其要关注黑—黑边。
K-6. 赛时触发器#
看到网格“一笔走完 / 每格恰一次 / 回到起点”,先做三件事:
- 染色:c(x,y)=(x+y)mod2。
- 数黑白点:回路要求相等;路径看端点颜色。
- 再检查结构:边界、障碍、割点、窄网格,最后才进入构造或插头 DP。
一句话:网格 Hamilton 问题先别急着搜路径,先用二分图黑白计数把不可能情况砍掉。
L. 概率与期望#
L-1. 概率计算#
独立事件的交集概率相乘,互斥事件的并集概率相加。
P(A∩B)=P(A)P(B∣A).只有独立时才能把 P(B∣A) 换成 P(B)。不放回抽样通常不独立。
至少发生一次,先算一次都不发生。各次独立、发生概率为 pi 时:
P(至少一次)=1−i∏(1−pi).事件不独立时,可用容斥:
P(i=1⋃nAi)=∅=S⊆[n]∑(−1)∣S∣+1P(i∈S⋂Ai).L-2. 期望的性质#
离散变量按概率求和,有密度的连续变量按密度积分:
E[g(X)]=x∑g(x)P(X=x),E[g(X)]=∫g(x)fX(x)dx.线性性不要求独立。
E[c+i∑wiXi]=c+i∑wiE[Xi].例如相邻差共享元素,仍然可以拆开算:
E[i=2∑n∣ai−ai−1∣]=i=2∑nE[∣ai−ai−1∣].若 X,Y 独立,则 E[XY]=E[X]E[Y]。但下面这些式子一般不成立:
E[X2]=E[X]2,E[∣X∣]=∣E[X]∣,E[X/Y]=E[X]/E[Y].按第一步结果分类,就是全期望公式。设 Bi 是互斥且覆盖所有情况的事件:
E[X]=i∑P(Bi)E[X∣Bi].期望 DP 的转移由此得到。
L-3. 指示变量与贡献法#
设 Ii 表示第 i 个对象是否贡献,贡献为 1,否则为 0。那么
E[Ii]=P(Ii=1),E[i∑Ii]=i∑P(Ii=1).求数量的期望,往往只需要算单个对象被计入的概率。
这里 Hn=∑i=1n1/i,H0=0。
覆盖长度也可以按位置拆:整数位置求 ∑xP(x 被覆盖),连续区间求 ∫P(x 被覆盖)dx。
L-4. 尾和公式与最值#
非负整数变量:
E[X]=k=1∑∞P(X≥k),E[X2]=k=1∑∞(2k−1)P(X≥k).证明只需把每个取值拆开:x=∑k=1x1,x2=∑k=1x(2k−1)。
非负连续变量:
E[X]=∫0∞P(X>t)dt.最值先求阈值概率。若 Xi 独立,Fi(t)=P(Xi≤t),则
P(imaxXi≤t)=i∏Fi(t),P(iminXi>t)=i∏(1−Fi(t)).求“最长长度、最大值、还能进行多少步”的期望时,可以先枚举阈值,算达到这个阈值的概率。
L-5. 成功次数与等待时间#
成功次数#
n 次独立试验,每次成功率都是 p,恰好成功 k 次:
P(X=k)=(kn)pk(1−p)n−k,E[X]=np.成功率不同为 pi 时,E[X]=∑ipi。恰好成功 k 次的概率用 DP:
dp[i][k]=dp[i−1][k](1−pi)+dp[i−1][k−1]pi,dp[0][0]=1.从 N 个物品中均匀不放回取 m 个,其中 K 个是目标物品:
P(X=k)=(mN)(kK)(m−kN−K),E[X]=NmK.不合法的组合数按 0 处理。
首次成功#
每次独立成功率为 p>0,T 包含成功那次:
P(T=k)=(1−p)k−1p,E[T]=p1.也可以写 E=1+(1−p)E,移项得 E=1/p。
- 只数成功前的失败次数:(1−p)/p。
- 等到累计 k 次成功:k/p。
- 等到连续 k 次成功:∑j=1kp−j。
连续成功的式子可由状态方程推出。Ej 表示当前连续成功 j 次,到结束还需的步数:
Ej=1+pEj+1+(1−p)E0(0≤j<k),Ek=0.分阶段#
在阶段 i,每次独立以概率 pi>0 进入下一阶段,失败仍停在原阶段。总期望为
i∑pi1.每次独立均匀抽取 n 种物品之一,已经有 k 种时,抽到新种类的概率为 (n−k)/n。集齐全部的期望为
E[T]=k=0∑n−1n−kn=nHn.只需集齐任意 m 种,则为 n(Hn−Hn−m)。各种物品概率不相等时,不能套这个式子。
L-6. 均匀分布#
设 L=r−l,m=r−l+1。
连续分布除以 r−l,整数分布除以 r−l+1。l=r 时是常数,期望为 l、方差为 0。
连续均匀变量的分布函数:
FX(t)=⎩⎨⎧0,(t−l)/L,1,t<l,l≤t≤r,t>r.区间概率等于交集长度除以 L;整数分布则数交集中的整数个数,再除以 m。
令 X=l+LU,U∼U[0,1],可以把一般区间化到 [0,1]。对整数 k≥0:
E[Uk]=k+11,E[Xk]=(k+1)(r−l)rk+1−lk+1.连续抽样:第 k 小、最值和间隔#
在 [l,r] 中独立均匀取 n 个点,排序后记为 X(1),…,X(n):
E[X(k)]=l+n+1kL,E[minXi]=l+n+1L,E[maxXi]=r−n+1L,E[maxXi−minXi]=n+1n−1L.加上两个端点后,共有 n+1 个间隔。各间隔同分布、总长为 L,所以每个间隔的期望都是 L/(n+1)。第 k 小距左端点的长度是前 k 个间隔之和。
整数抽样:有放回#
n 次独立均匀取整数 l,…,r,允许重复:
E[maxXi]=l+j=1∑m−1(1−(mj)n),E[minXi]=l+j=1∑m−1(mm−j)n.由尾和公式得到,m=1 时空和为 0。
整数抽样:不放回#
从 1,…,N 中均匀选出 m 个不同数,排序后为 S1<⋯<Sm:
E[Sk]=m+1k(N+1).选中元素前后及之间共有 m+1 个空隙,未选中元素共 N−m 个。每个空隙中未选中元素数的期望为 (N−m)/(m+1),于是 E[Sk]=k+k(N−m)/(m+1)。
L-7. 均匀分布的距离#
点到区间#
X∼U[l,r],L=r−l>0,固定点为 p:
E[∣X−p∣]=2L(r−p)∣r−p∣−(l−p)∣l−p∣.分段写法:
E[∣X−p∣]=⎩⎨⎧(l+r)/2−p,((p−l)2+(r−p)2)/(2L),p−(l+r)/2,p≤l,l<p<r,p≥r.两个区间#
X∼U[a,b]、Y∼U[c,d] 独立,A=b−a>0、B=d−c>0:
E[∣X−Y∣]=6AB∣b−c∣3+∣a−d∣3−∣a−c∣3−∣b−d∣3.推导:联合密度为 1/(AB),而
∫cd∣x−y∣dy=2(x−c)∣x−c∣−(x−d)∣x−d∣,∫ab∫cd∣x−y∣dydx=[6∣x−c∣3−∣x−d∣3]ab.区间相离、相交、包含都适用。一个区间退化为点时用“点到区间”;两个都是点时直接取绝对差。
若 b≤c,直接算 E[Y]−E[X]=(c+d−a−b)/2。
同一区间#
X,Y 独立同分布:
| | E[∣X−Y∣] | E[(X−Y)2] |
| --- | --- | --- |
| 连续区间,长度 L | L/3 | L2/6 |
| 整数区间,共 m 个数 | (m2−1)/(3m) | (m2−1)/6 |
整数绝对差按距离枚举:距离 k>0 的有序数对有 2(m−k) 对,所以
E[∣X−Y∣]=m22k=1∑m−1k(m−k)=3mm2−1.同一连续区间中,距离不超过 t 的概率为
P(∣X−Y∣≤t)=L2t−L2t2,0≤t≤L.可在边长为 L 的正方形中,减掉 ∣x−y∣>t 对应的两个三角形来推。
两个数的大小关系#
仍设两个区间非退化且独立,记 z+=max(z,0):
P(X≤Y)=2AB(d−a)+2−(d−b)+2−(c−a)+2+(c−b)+2.由 P(X≤Y)=B1∫cdFX(y)dy 积分得到。
这里 P(X=Y)=0。整数分布则需要另算相等概率,不能混用 < 和 ≤。
L-8. 二阶矩与方差#
Var(X)=E[X2]−E[X]2.计算总贡献平方时,展开成单项和成对贡献:
E(i∑Xi)2=i∑E[Xi2]+2i<j∑E[XiXj].对指示变量,Ii2=Ii,E[IiIj]=P(Ii=Ij=1)。因此计数的方差通常需要算“两件事同时发生”的概率。
独立时:
Var(i∑Xi)=i∑Var(Xi).独立试验的成功次数,方差为 ∑ipi(1−pi)。
两个独立变量的平方差:
E[(X−Y)2]=Var(X)+Var(Y)+(E[X]−E[Y])2.L-9. 期望 DP#
按步数分层或在 DAG 上,维护:
- Ps:到达状态 s 的概率。
- Fs:到达状态 s 的所有情况中,累计得分乘概率的和。
边 s→t 的转移概率为 p,新增得分为 w:
Pt+=pPs,Ft+=p(Fs+wPs).初始状态 P=1,F=0,答案为所有终止状态的 F 之和。Fs 已经包含到达概率,新增得分仍需乘 Ps。
Es 表示从状态 s 出发,到结束还需要的期望代价。转移概率为 pst、单步代价为 wst:
Es=t∑pst(wst+Et).没有终点奖励时 Eend=0。每步代价都是 1 时:
Es=1+t∑pstEt.自环概率为 q<1,移项:
Es=1−q1+∑t=spstEt.有一般环依赖时写线性方程组,不能直接记忆化递归。先检查是否可能进入无法到达终点的状态;若能以正概率进入,结束步数的期望为无穷大。
状态需包含决定后续转移的全部信息。例如连续成功题要记当前连击长度,不能只记已经进行多少次。
二阶矩转移#
Qs 表示从 s 出发,剩余总代价平方的期望。边代价 wst 固定时:
Qs=t∑pst(wst2+2wstEt+Qt).先求 Es,再求 Qs,方差为 Qs−Es2。
相关:期望DP。
L-10. 取模#
有理数 P/Q 的模表示为 P⋅Q−1。模数 M 为质数且 Q≡0(modM) 时:
Q−1≡QM−2(modM).
- 百分比转为 p⋅100−1,固定分母的逆元只算一次。
- 比较大小、取绝对值、取 z+,都在取模前做。
- 连乘逐步取模,三次方不要直接在原整数上计算。
- 自环移项的 1−q 也要检查是否可逆。实数意义下非零,不代表模意义下非零。
- 大量非零分母可用前缀积和倒推批量求逆,只求一次总乘积的逆元,复杂度 O(n+logM)。
- 分母模 M 为 0 时不能硬求逆。先在有理数层面约分,最终分母仍与 M 不互质,则这种模表示不存在。
M. 切比雪夫距离与曼哈顿距离#
设 P=(x1,y1),Q=(x2,y2):
- 曼哈顿距离:d1(P,Q)=∣x1−x2∣+∣y1−y2∣。
- 切比雪夫距离:d∞(P,Q)=max(∣x1−x2∣,∣y1−y2∣)。
将每个点变换为 T(x,y)=(x+y,x−y),则:
d1(P,Q)=d∞(T(P),T(Q))d∞(P,Q)=21d1(T(P),T(Q))即:原曼哈顿 = 新切比雪夫;原切比雪夫 = 新曼哈顿的一半。
N. 离散介值性质与非单调二分#
N-1. 使用场景#
固定长度的窗口每次右移一格,只移出左端点、加入右侧新点。若每个位置的贡献为 0 或 1,窗口统计量每次只能变化 −1,0,1。
当题目要求找到 f(s)=k 的某个位置时,可以检查相邻位置的差值是否至多为 1。此时即使 f 不单调,只要找到函数值位于 k 两侧的两个端点,也能二分出一个解。
N-2. 离散介值性质#
命题:设整数区间 [L,R] 上的整数值函数 f:Z∩[L,R]→Z 满足对任意整数 x∈[L,R−1] 均有 ∣f(x+1)−f(x)∣≤1。
对任意整数 k:
- 若 f(L)>k≥f(R) 且 L<R,则必存在整数 s∈(L,R] 满足 f(s)=k。
- (反向跨越版本)若 f(L)<k≤f(R) 且 L<R,则同样必存在整数 s∈(L,R] 满足 f(s)=k。
证明(以 f(L)>k≥f(R) 为例):
考虑集合 S={x∈[L,R]∣f(x)≤k}。
- 因为 R∈S,故 S 是有限非空整数集,必存在最小元素 s=minS。
- 因为 f(L)>k,故 L∈/S,由此可知 s>L。
- 由 s 的最小性,其前驱位置 s−1∈/S,即 f(s−1)>k。由于函数值为整数,这意味着 f(s−1)≥k+1。
- 根据单步差分约束,每步至多下降 1:f(s)≥f(s−1)−1≥k。
- 结合 s∈S 的定义 f(s)≤k,两式夹逼立得 f(s)=k。
N-3. 非单调二分#
这里不要求 f 单调,也不要求判定式 f(s)>k 构成一个连续前缀。
算法维护当前搜索区间 [L,R],其循环不变式始终为:
f(L)>k且f(R)≤k
- 取 mid=⌊(L+R)/2⌋。
- 若 f(mid)>k,更新 L←mid;否则更新 R←mid。
- 循环终止条件为 L+1=R(区间长度缩减为 1,两端点为相邻整数)。
- 相邻端点收敛正确性:终止时由不变式可知 f(L)≥k+1 且 f(R)≤k。又由单步变化约束 ∣f(R)−f(L)∣≤1,两端至多相差 1,因此两个不等式必然同时取等,推导出 f(L)=k+1 且 f(R)=k。
被丢弃的半边可能也有解,但保留下来的两端始终分别满足 f(L)>k 与 f(R)≤k。二分只利用这两个端点的跨越关系,直到它们相邻;并不是在求单调分界点。
N-4. 实例:CF Target Infection#
题意抽象:数轴上给定若干互不相交的闭区间 [li,ri](均为感染点,其余为 0)。给定检测窗口长度 m 与目标感染数 k,求是否存在窗口 [s,s+m−1] 使得其中的感染点数恰好为 k。
- 单步变化性质:
设 a(x)∈{0,1} 为坐标 x 是否被感染的示性函数。窗口以 s 为左端点,包含感染点数为 f(s),则平移一步的变化为:
f(s+1)−f(s)=a(s+m)−a(s)∈{−1,0,1}
- 全局最大值必可在某个 li 处取到:
设某个窗口 [s∗,s∗+m−1] 取得全局感染点数最大值:
- 若 s∗ 为非感染点且右侧还有感染区间,向右平移至下一个区间左端点 li。平移时左端移出的全是 0,右端移入点数非负,f 不减。若 s∗>rn,则 f(s∗)=0,而 f(ln)≥1,因此这不可能是最大值点;
- 若 s∗ 落在某个感染区间内部且 s∗>li,向左平移窗口至 li。平移期间左端移入的全是 1,右端移出点数至多等于移入点数,f 不减。
- 故枚举所有区间的左端点 li,必能覆盖到至少一个全局最大值。
- 算法流程与边界处理:
- 遍历所有 li 计算 f(li):
- 若中途直接命中 f(li)=k,直接输出 li 即可(包含 k=0 时若恰好有 f(li)=0);
- 若存在 f(li)>k,记录任意一个满足条件的端点作为二分左端点 L;
- 若所有 li 均满足 f(li)<k,由于最大值亦严格小于 k,问题直接无解;
- 确定 L 后,取右端点 R=rn+1。因为窗口完全落在所有感染区间右侧,窗口内感染数为 f(R)=0。对于任意非负目标 k≥0,均满足 f(R)=0≤k;特别地若 k=0,此处可直接确定有解;
- 此时满足 L<R 且 f(L)>k≥f(R),直接调用非单调二分,返回收敛时的 R 即可。
- O(logn) 快速求 f(s):
- 令 F(x) 为坐标 ≤x 的感染点总数,则 f(s)=F(s+m−1)−F(s−1)。
- 区间互不相交,维护各区间长度的前缀和。用
std::upper_bound 找到最后一个满足 lj≤x 的区间,再计算 pre[j−1]+min(x,rj)−lj+1;没有这样的区间时取 0。即使 x 位于两个区间的空隙中,公式也成立。单次计算为 O(logn)。
- 坐标与前缀长度可能达到 1015,相关计算需统一使用
long long。
N-5. C++17 核心模板#
以下代码放在 solve() 内;f(s) 已实现,区间数组 l,r 使用 1-based 下标,n,k 和坐标均为整数。
auto find_s = [&]() -> ll {
if (k == 0) return r[n] + 1;
for (int i = 1; i <= n; ++i) {
if (val == k) return l[i];
if (L == -1) return -1; // 最大感染数小于 k
ll R = r[n] + 1; // f(L) > k,f(R) = 0 <= k
ll mid = L + (R - L) / 2;
return R; // 相邻时必有 f(R) == k
cout << find_s() << '\n';
局限:若每步可跳过整数目标(如 2→0 找 1),结论不成立;两端未跨越 k 时也不适用。
O. SOS:先把集合包含方向写出来#
触发器:候选满足“至少含有这些位”、与 x 按位不相交、某些位全部为1。
子集和从缺一位传给有这一位,超集和从有这一位传给缺这一位。用 01 检查:子集是 00,01,超集是 01,11。x&y==0 则 y 是 FULL^x 的子集,调用 cp::subset_witness(a,B) 后查补集即可。
求非空子集 AND=0:超集统计 c[S],容斥加减 2^c[S]-1,符号由 popcount(S) 的奇偶决定。预处理2的幂,避免每个mask重复快速幂。
代码证据:cf/165E.cpp、cf/449D.cpp。完整公式见 算法竞赛数学套路,自包含代码见 算法竞赛模板增补。
P. 乘积为完全平方:质因子指数奇偶 + 前缀相等#
触发器:区间乘积巨大,但只关心它是否为平方。
不乘出乘积,而存质因子指数模2。区间乘积为平方 iff 两端前缀向量相同。用质数集合对称差维护,或质数种类小时压成bit。
12 和 3 相乘为平方,指数2必须抵消;不能只记出现的质数,也不能将质数本身数值随意XOR来替代坐标向量。0与负数额外处理。
代码证据:cf/cf1125/f.cpp。完全k次幂改成指数模k,查询互补向量。
Q. 严格多数的坏事件互斥#
触发器:每个选择只属一个类别,禁止某类数量超过所选总数的一半。
两类不能同时严格过半,故“总方案数 - 每类坏方案数之和”即可。固定类别j,用差值 选j个数-选其他个数 做DP,最后减去差值>0的状态。
若变为“大于等于一半”,两类各占一半可以同时发生,就不能直接减。空方案是否允许必须独立处理。
代码证据:luogu/P5664.cpp,转移与模减法见 算法竞赛数学套路。
R. mask 已决定的余数,不再增加状态维#
触发器:已选元素集合固定,所有组目标和为T。
rem=sum[mask]%T 唯一,删除余数维。但“余数为0”是否完成一个合法组依赖题意;装桶需检查不超过T,计数倍数边界是另一种模型。dp[0] 根据“已完成非空组数”初始化为0。
代码证据:atcoder/atcoder480/f.cpp。用充分性与可恢复性同时审查状态:未来不同则不能合并,量已唯一决定则不必存。
S. 离线缓存:下一次最晚使用者优先淘汰#
触发器:已知完整访问序列,容量有限、载入代价相同,求最少缺失。
从后往前计算每次访问的下一次位置;标准单项请求模型中,满缓存缺失时淘汰下次使用最远的已有对象,永不再用视为无穷。交换论证:若另一方案淘汰更早要用者,交换这两个淘汰对象,在更早的那次访问前不会更差。
本地 nowcoder_2026_summer/8/m.cpp 将Trie前缀映射为访问对象,并用PBDS修改下一次位置。整批前缀需要共存的规则和逐个请求不同,不能把通用单项模板原封不动套到整批模型。是否能提前丢弃、当前批次容量如何约束,均要查原题。
自包含单项版本 cp::offline_cache_misses 使用惰性堆,复杂度O(n log n)、空间O(n),不是O(n log capacity)。容量0单独返回访问数。
T. min/max 组成代价:断点与斜率#
触发器:参数t变化,代价为线性项加若干截断区间贡献。
先标出改变表达式的断点,如l_i,r_i。相邻断点间函数线性,最值在端点或整段取得;不需要先证明整个函数单峰。
同坐标事件一起处理:旧斜率推值到pos → 更新答案 → 合并pos事件。cp::clipped_cost_min 对指定的截断模型返回最优值与t;通用推导见 算法竞赛数学套路。
代码证据:reginonals/26xian/h.cpp。128位必须保护括号内乘法。
U. 同步加减的数对:先压缩差值#
触发器:两数一起加减,或者同时除某个公因子。
一起加减保持差d;共同因子整除d;同除p使差变d/p。因此可先分解初始差,递归只选择其质因子,再记忆化当前(a,d)。向上和向下凑倍数是否都允许,必须服从原题。
代码证据:reginonals/21nanjing/j.cpp。d=0、1及数值是否要求正数需单独分析,不能盲抄非零差的分解过程。
V. 乘法统计:转到原根指数域做循环卷积#
触发器:模素数p,非零乘积的余数分布,或重复独立乘法。
非零值=g^e后,乘法变指数相加mod(p-1),由线性卷积再按p-1折叠。0单独处理;1对应指数0;多项式快速幂单位元为[1,0,…]。
代码证据:reginonals/23xian/f.cpp。原根、NTT长度、计数模数是三个不同参数;不能把乘法值域素数p直接当NTT模数。见 算法竞赛数学套路。
W. 区间颜色比较:先变前缀差,再看二维偏序#
触发器:同一区间内多种字符数量之间有若干不等式。
R>=G与R>=B变为两个前缀差X,Y,合法(j,i]等价于X_j<=X_i,Y_j<=Y_i。若答案是所选不交区间总长度,再将i-j拆成i+(-j),查询历史点的dp[j]-j最大值。
不要因“二维”就直接选树套树;先说明第三个时间约束j<i由处理顺序保证,查询在插入前。cp::Fenwick2DMax 预收坐标,后续在线chmax与前缀最大值查询。
来源:用户提供的9月RGB回顾,未凭题名补造完整题面。见 算法竞赛数学套路。
X. 树上路径差分:用割决定传播方向#
触发器:批量路径对每条树边的覆盖次数或奇偶。
端点XOR后,边的答案是子树标记XOR,必须从子到父恢复。理由:路径跨越子树割当且仅当一端在子树里。
若改求普通次数,需要端点+1、LCA-2;点覆盖次数又是另一套LCA修正。根到点前缀的父传子不能替代这一步。
来源:用户提供的Canal Crossing回顾。迭代代码 cp::tree_path_xor_edges 不依赖LCA,适用于边覆盖奇偶。
Y. 算法退出前,先完成状态恢复#
触发器:DSU on Tree、回溯、虚树多询问、二分check临时统计。
提前找到答案只允许跳过不再需要的搜索,不能跳过本层负责的回滚。保存found,完成清理后返回,或用局部容器/作用域恢复。keep=false需恢复,keep=true按协议保留,二者不能混淆。
固定验证:同一个check调用两次结果相同、用例次序交换不影响各自答案、兄弟处理顺序不改变结果。来源:用户提供的10月DSU on Tree回顾。
Z. 同key对象:相遇事件、计数还是等价历史?#
触发器:map中用位置、时间、前缀状态等作为key。
mp[key]=value默认丢弃旧对象。先判断同key是否应碰撞、累加、保留全部ID,还是只需保留最小代价。树上碰撞最小反例:一个节点、两个对象同一时刻出现,不能互相覆盖。
同理,前缀平方状态需要累加频次,最短路状态通常保留最小距离。容器操作应来自状态等价证明,而不是按习惯赋值。
2026-10-25 整理入口#
新增O–Z来自本地代码核对及用户提供的近三个月对话回顾,未独立读取原网页历史;旧A–N保留。结构证明、输入边界与可运行代码分别见: