10983 字
55 分钟
算法竞赛 Classic Tricks 复习笔记

算法竞赛 Classic Tricks 复习笔记#


A. 任意 n≥2n\ge2 都能由 2 和 3 凑出#

使用场景#

  • 区间/长度要拆成若干段,每段长度只能取 2 或 3。
  • 构造题中需要证明所有 n≥2n\ge2 都可写成 2x+3y2x+3y,其中 x,y≥0x,y\ge0。
  • 原题出现“2 和 3 的倍数组合”时,先把它化成非负整数解问题。

核心结论#

对任意整数 n≥2n\ge2,都存在 x,y≥0x,y\ge0 使

n=2x+3y.n=2x+3y.

若 nn 为偶数,取 x=n/2,y=0x=n/2,y=0;若 nn 为奇数,则 n≥3n\ge3,先取一个 3,剩下 n−3n-3 为偶数。


B. Kruskal 瓶颈在排序时不如直接枚举值域#

使用场景#

  • 边权值域很小(如 [0,W][0,W],W≤106W \le 10^6),但边数很多(mm 很大)。
  • 图由隐式规则生成,值域有限但边数是 O(n2)O(n^2) 级别。
  • 需要最小生成树,且排序成本 O(mlog⁡m)O(m\log m) 超过 O(n+W)O(n + W) 枚举。

核心观察#

Kruskal 真正要求的是“按边权从小到大处理”,不一定非要比较排序。若边权值域 WW 很小,并且能把显式边按权值桶化,或能直接生成某个权值的候选边,就可以从小到大枚举权值并做并查集合并。

显式边桶化时,排序部分可由 O(mlog⁡m)O(m\log m) 降到 O(m+W)O(m+W);若图是隐式生成的,还必须把“生成当前权值的候选边”的复杂度一起算进去,不能仅凭值域小就自动省掉 O(n2)O(n^2) 条边。


C. 固定 K 的乘除 → 考虑 K 进制#

使用场景#

  • 问题中存在某个固定常数 KK,元素需要乘以 KK 或除以 KK。
  • 操作反复作用在同一数上,或需要统计”乘了多少次 KK”。
  • 权重/贡献与 KK 的幂次有关,或题目本质是”进位/借位”。

核心观察#

若有固定的 KK,则“乘 KK”对应 KK 进制左移一位;当当前数能被 KK 整除时,“除 KK”对应右移一位。若题目使用整数除法,还要单独处理被舍去的最低位。

因此看到反复乘/除固定 KK,可以把数拆成 KK 进制各位,检查操作是否变成移位、进位或按位独立处理。


D. BFS 遍历所有状态求最值#

使用场景#

  • 状态空间有限,且每次转移代价均为 11(或均匀),问最短步数/最大/最小值。
  • 问题看似需要 DP 或搜索,但状态之间无拓扑序或转移顺序不固定。
  • 需要求”从所有合法起点出发能到达哪些状态的最小距离”,多源 BFS。

核心观察#

这里的重点不是“BFS 能直接求任意最值”,而是:BFS 也可以只是一个状态枚举器。

当状态空间有限,并且每个状态只需被处理一次时,可以从初始状态 BFS,把所有可达状态遍历出来;若目标是“所有可达状态自身的最大/最小属性”,遍历时直接统计即可。多源 BFS 则可同时从所有起点出发,得到到最近起点的最短距离。


E. 两物性价比与数量上界#

使用场景#

  • 有两类物品,各有价值 viv_i 与价格 pip_i(i=1,2i=1,2),要以最低总价达到总价值 ≥V\ge V。
  • 背包类题目中物品只有两种,或可以把所有物品归类成”性价比高”与”性价比低”两组。
  • 需要证明最优解中某类物品的数量有上界。

核心结论#

设两类物品价值/价格分别为 (v1,p1)(v_1,p_1)、(v2,p2)(v_2,p_2),且物品 1 的单位价值成本不高于物品 2:

p1v1≤p2v2.\frac{p_1}{v_1}\le\frac{p_2}{v_2}.

令 g=gcd⁡(v1,v2)g=\gcd(v_1,v_2)。若物品 2 买了至少 v1/gv_1/g 个,可以把其中 v1/gv_1/g 个物品 2 替换成 v2/gv_2/g 个物品 1:两边提供的价值完全相同,而替换后的总价不会更高。因此一定存在一个最优解满足

0≤x2<v1g.0\le x_2<\frac{v_1}{g}.

所以可以枚举性价比较低的物品数量,再用高性价比物品补足目标价值。原文“性价比低的数量不会买超过性价比更高的价值”记录的就是这种交换上界思想;具体上界必须由题目参数证明,不能凭性价比直接猜。


F. 序列中移动元素 → 观察 ai±ia_i \pm i#

使用场景#

  • 序列中可以将某个元素向左或向右移动若干步,移动代价与移动距离(下标差)有关。
  • 要把一组元素移动到某些目标位置,使总移动距离最小。
  • 元素相对顺序不变(或只考虑某个元素),操作等价于调整下标。

核心观察#

当表达式里同时出现“值 aia_i”和位置差 ∣i−j∣|i-j| 时,先按左右关系拆绝对值。例如

ai+∣i−j∣={(ai−i)+j,i≤j,(ai+i)−j,i>j.a_i+|i-j|= \begin{cases} (a_i-i)+j,&i\le j,\\ (a_i+i)-j,&i>j. \end{cases}

于是所有与 ii 有关的部分只剩 ai−ia_i-i 或 ai+ia_i+i。这经常能把“值 + 移动距离”拆成前缀/后缀最值问题。

常见触发式:ai±∣i−j∣a_i\pm|i-j|、∣ai−aj∣+∣i−j∣|a_i-a_j|+|i-j|、需要同时比较数值与位置的最值式。原文只记录了“观察 ai±ia_i\pm i”这个触发器;具体操作是否真的形成不变量,必须针对题目另证。


G. 二进制位运算律速查#

位运算逐位独立,因此很多恒等式只需在单个 bit 的 0/10/1 情况下验证。

使用场景#

  • 题目涉及位掩码、子集枚举、按位统计。
  • 需要把 XOR/AND/OR 的前缀和或区间查询转化成等价形式。
  • 推导某个位运算组合是否满足分配律,或需要把补集写成 XOR。

G-1. XOR(异或)#

  • 交换律:a⊕b=b⊕aa\oplus b=b\oplus a
  • 结合律:(a⊕b)⊕c=a⊕(b⊕c)(a\oplus b)\oplus c=a\oplus(b\oplus c)
  • 单位元:a⊕0=aa\oplus0=a
  • 自反:a⊕a=0a\oplus a=0
  • 消去:a⊕b⊕b=aa\oplus b\oplus b=a
  • 因而前缀异或可直接还原区间:al⊕⋯⊕ar=prer⊕prel−1a_l\oplus\cdots\oplus a_r=pre_r\oplus pre_{l-1}

G-2. AND / OR#

  • 交换律:a&b=b&aa\mathbin{\&}b=b\mathbin{\&}a,a∣b=b∣aa|b=b|a
  • 结合律:(a&b)&c=a&(b&c)(a\mathbin{\&}b)\mathbin{\&}c=a\mathbin{\&}(b\mathbin{\&}c),OR 同理
  • 幂等:a&a=aa\mathbin{\&}a=a,a∣a=aa|a=a
  • 零元/单位元:a&0=0a\mathbin{\&}0=0,a∣0=aa|0=a
  • 吸收律:a∣(a&b)=aa|(a\mathbin{\&}b)=a,a&(a∣b)=aa\mathbin{\&}(a|b)=a

AND 与 OR 互相满足分配律:

a&(b∣c)=(a&b)∣(a&c),a\mathbin{\&}(b|c)=(a\mathbin{\&}b)|(a\mathbin{\&}c),a∣(b&c)=(a∣b)&(a∣c).a|(b\mathbin{\&}c)=(a|b)\mathbin{\&}(a|c).

固定掩码的 AND 对 XOR 也满足分配律:

(a⊕b)&m=(a&m)⊕(b&m),(a\oplus b)\mathbin{\&}m =(a\mathbin{\&}m)\oplus(b\mathbin{\&}m),

因此

(⨁i∈Sai)&m=⨁i∈S(ai&m).\left(\bigoplus_{i\in S}a_i\right)\mathbin{\&}m =\bigoplus_{i\in S}(a_i\mathbin{\&}m).

直观上,mm 只是逐位过滤器:mi=0m_i=0 时该位统一清零,mi=1m_i=1 时原样保留 XOR。

G-3. NOT 与德摩根律#

在固定 BB 位范围、MASK=2B−1MASK=2^B-1 时,可把补集写成 a‾=a⊕MASK\overline a=a\oplus MASK。

a&b‾=a‾∣b‾,a∣b‾=a‾&b‾.\overline{a\mathbin{\&}b}=\overline a|\overline b, \qquad \overline{a|b}=\overline a\mathbin{\&}\overline b.

C++ 的 ~a 会翻转整数类型的全部位;只关心低 BB 位时记得再 & MASK。

G-4. 竞赛常用恒等式#

  • 判第 kk 位:(x >> k) & 1
  • 置第 kk 位:x |= 1LL << k
  • 清第 kk 位:x &= ~(1LL << k)
  • 翻转第 kk 位:x ^= 1LL << k
  • 最低位的 11:lowbit(x) = x & -x
  • 删除最低位的 11:x &= x - 1
  • 判断 xx 是否为 22 的幂:x > 0 && (x & (x - 1)) == 0
  • 低 kk 位掩码:(1LL << k) - 1(注意 kk 不能等于类型位宽)
  • 枚举非空子掩码:for (int s = mask; s; s = (s - 1) & mask)

G-5. 常见转化#

  • XOR 前缀和:xor(l,r)=prer⊕prel−1xor(l,r)=pre_r\oplus pre_{l-1}。
  • 只关心掩码 mm 中的位:可以先做 a[i] & m 再 XOR,因为 AND 对 XOR 线性。
  • 要求 mask 的所有 11 都包含在 xx 中:(x & mask) == mask。
  • 要求 xx 的所有 11 都属于 mask:(x & mask) == x。

[!warning] 不要错误推广 OR 不对 XOR 满足类似分配律。例:a=0,b=0,m=1a=0,b=0,m=1,(a∣m)⊕(b∣m)=0(a|m)\oplus(b|m)=0,但 (a⊕b)∣m=1(a\oplus b)|m=1。 移位等价于乘除 2k2^k 只应在无溢出、且右移对象非负等条件下使用。


H. 质数与质因子:10810^8 值域结论#

使用场景#

  • 题目值域不超过 10810^8,需要判素、分解质因子、或枚举约数。
  • 需要对某个 nn 的所有互质计数(容斥),或枚举无平方因子约数。
  • 出现 gcd 边权,怀疑可用中间质数构造权值为 11 的边。
  • 题目要求枚举 nn 附近的质数,或判断”所有质因子都大于 10410^4”。

H-1. 判定与筛法的边界#

  • 若 n≤108n\le 10^8 为合数,则它一定有一个不超过 n≤104\sqrt n\le10^4 的质因子。因此单次试除只需检查到 10410^4。
  • 10410^4 以内共有 12291229 个质数。先筛出这些质数后,单次分解 n≤108n\le10^8 最多试除 12291229 次,而不必枚举所有整数。
  • 10810^8 以内共有 5 761 4555\,761\,455 个质数,最大质数是 99 999 98999\,999\,989。
  • 若要回答大量区间质数问题,埃氏筛的时间复杂度为 O(Nlog⁡log⁡N)O(N\log\log N),普通 bool/uint8_t 标记约占 NN 字节;只存奇数可把空间减半。
  • 单个 3232 位整数的判素也可使用确定性 Miller—Rabin;但在 10810^8 内,试除或预筛通常更短且常数稳定。参见 Miller Rabin算法、欧拉筛法(线性筛)。

[!tip] 平方根写法 用 1LL * p * p <= n,避免 p * p 在更大值域中发生 int 溢出。分解结束后若 n > 1,剩余部分本身就是一个质因子。

H-2. 不同质因子个数很少#

令 ω(n)\omega(n) 表示 nn 的不同质因子个数。为了在固定值域内让 ω(n)\omega(n) 最大,应依次乘最小的不同质数:

2⋅3⋅5⋅7⋅11⋅13⋅17⋅19=9 699 690≤108,2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19 =9\,699\,690\le10^8,

但

9 699 690⋅23=223 092 870>108.9\,699\,690\cdot23=223\,092\,870>10^8.

因此

n≤108⟹ω(n)≤8.n\le10^8\Longrightarrow \omega(n)\le8.

直接推论:

  • 枚举不同质因子的所有子集至多 28=2562^8=256 个状态;
  • 用容斥统计区间内与 nn 互质的数,复杂度可视为常数;
  • 若只需要无平方因子约数、莫比乌斯式容斥项,同样最多枚举 256256 项。

对 nn 的不同质因子集合 PP,[1,x][1,x] 内与 nn 互质的数可写为

C(x)=∑S⊆P(−1)∣S∣⌊x∏p∈Sp⌋.C(x)=\sum_{S\subseteq P}(-1)^{|S|} \left\lfloor\frac{x}{\prod_{p\in S}p}\right\rfloor.

区间 [l,r][l,r] 的答案为 C(r)−C(l−1)C(r)-C(l-1)。

H-3. 质因子总数、因子个数与枚举规模#

  • 令 Ω(n)\Omega(n) 计重数。由于 226=67 108 864≤108<2272^{26}=67\,108\,864\le10^8<2^{27},故 Ω(n)≤26\Omega(n)\le26。
  • 10810^8 内约数个数的最大值为 768768,例如 73 513 44073\,513\,440 达到该值。因此对单个数直接枚举全部约数通常足够快。
  • 枚举因数对只需循环到 n≤104\sqrt n\le10^4;发现 d∣nd\mid n 时同时处理 dd 与 n/dn/d,平方数需避免重复。
  • 质因数分解后,约数个数为 τ(n)=∏i(ei+1)\tau(n)=\prod_i(e_i+1),欧拉函数为 φ(n)=n∏i(1−1/pi)\varphi(n)=n\prod_i(1-1/p_i)。两者都只依赖分解结果,适合一次分解后集中计算。

H-4. 质数间隔可把”大值域”压成”小尾段”#

在明确值域上界时,相邻质数间隔可作为竞赛中的小常数,但必须区分”严格结论”和”拍脑袋常数”。

  • 在 10710^7 内,相邻质数的最大间隔为 154154;在 10810^8 内最大间隔为 220220。
  • 因而在 x≤108x\le10^8 时,向前或向后寻找附近质数,保守扫描约 220220 个连续整数即可覆盖内部完整质数间隔;靠近值域端点时仍需显式处理边界。
  • 这适合把区间拆成”大段统一计数 + 质数附近小尾段 DP/暴力”。例如边权为 gcd⁡(u,v)\gcd(u,v) 时,夹在两点之间且不整除端点的质数能提供两条权值为 11 的边,从而把最短路封顶为 22。

[!warning] 使用条件 “中间有质数”不自动推出两条边的 gcd 都是 11。若质数 pp 小于端点 vv,仍可能有 p∣vp\mid v。证明中应排除该情形、另选质数,或把同一小质数间隔交给暴力/DP。

H-5. 常见建模触发器#

  • 题目出现”与固定 nn 互质的区间计数”:分解 nn 的不同质因子,做至多 256256 项容斥。
  • 题目出现”寻找 xx 附近的质数”且 x≤108x\le10^8:试除判素配合小范围扫描通常已经足够。
  • 题目出现”所有质因子都大于 10410^4“且数不超过 10810^8:该数只能是 11 或质数,不可能含两个大于 10410^4 的质因子。
  • 题目出现 gcd 边权且允许向更大的整数跳转:尝试用中间质数制造权值 11 的边,再单独处理质数间隔内的短尾部。
  • 题目要求枚举 nn 的无平方因子约数:只枚举不同质因子子集,不必生成全部约数。

I. 自由构造模数:同余 → 整除取差#

使用场景#

  • 题目要求输出一个模数 mm,使得某个关系 a≡b(modm)a \equiv b \pmod{m} 成立。
  • 题目允许”任意合法解均可”,模数不是固定输入。
  • 看到”输出一个数使得……在模该数意义下……”。

I-1. 触发器#

题目要求构造某个模数 mm,并满足:

a≡b(modm)a\equiv b\pmod m

或者:

f(x)≡y(modm)f(x)\equiv y\pmod m

且 mm 不是输入固定的,而是允许自己输出。

这时不要急着做同余方程或二次剩余判定,先把同余翻译成整除:

a≡b(modm)⟺m∣a−ba\equiv b\pmod m \Longleftrightarrow m\mid a-b

既然 mm 可以自己选,若 a≠ba\ne b,最直接可以取

m=∣a−b∣,m=|a-b|,

或者取 ∣a−b∣|a-b| 的某个正因子。若 a=ba=b,这条同余对任意合法正模数都成立,再按题目的范围条件选 mm 即可。

I-2. 核心想法#

如果模数由我们构造,那么我们可以反过来制造一个”必然成立”的模关系。

常见模板:

f(x)≡y(modm)f(x)\equiv y\pmod m

等价于:

m∣f(x)−ym\mid f(x)-y

若 f(x)≠yf(x)\ne y,可令

m=∣f(x)−y∣.m=|f(x)-y|.

这条同余就直接成立;若 f(x)=yf(x)=y,任意合法正模数都满足它。之后仍要检查题目对 mm 的范围、大小、互异性等额外限制。

[!tip] 赛时提醒 看到”输出一个模数 / 输出一个数作为模数 / 任意合法解均可”,优先把同余改写成整除。自由变量不要拿来猜,拿来消掉约束。

相关:抽象代数、Miller Rabin算法


J. LogTrick:固定端点压缩区间运算状态#

适用:区间运算满足结合律,并且固定一端后,累计值只会沿某个方向收缩/扩张。典型是 gcd⁡\gcd、LCM、按位 AND、按位 OR。

固定右端点 rr,看所有

f(l,r)=al∘al+1∘⋯∘ar,l=r,r−1,…,1.f(l,r)=a_l\circ a_{l+1}\circ\cdots\circ a_r,\qquad l=r,r-1,\dots,1.

虽然左端点有 O(n)O(n) 个,但不同的 f(l,r)f(l,r) 往往只有 O(log⁡V)O(\log V) 个,因此可以把连续产生同一结果的一批左端点合并成一个状态。

使用场景#

  • 看到”所有子数组的 GCD / AND / OR / 有界 LCM”。
  • 固定右端点后,区间值只会变小(GCD、AND)或变大(LCM、OR)。
  • 要统计满足某个区间运算结果等于 KK 的子数组个数。
  • nn 很大,显然不能枚举 O(n2)O(n^2) 个区间,但值域只有 30/60 位。

J-1. 为什么状态数是对数级#

  • GCD:若新值变小,则它是旧值的真因数,因此至少减半:
gnew∣gold,gnew<gold⟹gnew≤gold2.g_{\text{new}}\mid g_{\text{old}},\quad g_{\text{new}}<g_{\text{old}} \Longrightarrow g_{\text{new}}\le \frac{g_{\text{old}}}{2}.

所以从 VV 开始最多严格变化 O(log⁡V)O(\log V) 次。

  • LCM:若新值变大,则旧值整除新值,因此至少翻倍:
Lold∣Lnew,Lnew>Lold⟹Lnew≥2Lold.L_{\text{old}}\mid L_{\text{new}},\quad L_{\text{new}}>L_{\text{old}} \Longrightarrow L_{\text{new}}\ge 2L_{\text{old}}.

实际使用时通常设上界 UU 或要求最终整除目标 KK。超过上界后直接截断,否则状态数也是 O(log⁡U)O(\log U)。

  • AND:向区间里加入元素后,二进制位只会 1→01\to0。
  • OR:向区间里加入元素后,二进制位只会 0→10\to1。

若有效位数为 BB,每次值改变至少翻转一个尚未翻转过的 bit,因此不同值最多 B+1B+1 个。

J-2. 最稳的 Rolling Vector 写法#

不要纠结”最远左端点”方向,直接维护 (value,count)(value,count):表示以当前 rr 结尾时,有多少个左端点得到这个 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;
else
nxt.push_back({nv, cnt});
}
cur.swap(nxt);
// cur 中就是所有以 r 结尾的不同区间值
}

为什么只需要合并相邻相同值:上一轮状态已经按左端点远近排好,加入同一个 ara_r 后,GCD / AND / OR / 有界 LCM 的变化仍保持单调,因此相同结果会连续出现。

总状态数每轮只有 O(log⁡V)O(\log V),所以总复杂度通常是

O(nlog⁡V).O(n\log V).

GCD 还要乘上一次 gcd⁡\gcd 的常数/对数代价,但竞赛里通常很小。

J-3. 常见用途#

  1. 统计所有子数组能得到多少种不同 GCD / AND / OR:每个 rr 枚举 cur,扔进全局 set。
  2. 统计满足 f(l,r)=Kf(l,r)=K 的子数组个数:若某状态 (K,cnt)(K,cnt),答案直接加 cntcnt。
  3. 求区间运算结果最接近 KK:每轮只检查 O(log⁡V)O(\log V) 个状态。
  4. 最短区间 LCM =K=K:先把不是 KK 因子的元素当断点;更新 LCM 后若不再整除 KK,该状态直接删除。

J-4. LCM 溢出保护#

计算

lcm⁡(a,b)=agcd⁡(a,b)⋅b\operatorname{lcm}(a,b)=\frac{a}{\gcd(a,b)}\cdot b

必须先除后乘。若只关心不超过上界 UU,设

x=agcd⁡(a,b).x=\frac{a}{\gcd(a,b)}.

乘之前判断

if (x > U / b) {
// lcm > U,直接截断
} else {
long long l = x * b;
}

J-5. ST 表 + 二分跳跃#

另一种写法是先用 ST 表支持静态区间 GCD / AND / OR 查询。

固定左端点 ll,当前区间值为 vv。由于结果沿右端点单调变化,可以二分找到满足

f(l,x)=vf(l,x)=v

的最远位置 xx,然后从 x+1x+1 开始处理下一个不同值。

若区间查询 O(1)O(1),枚举一个固定端点的全部不同状态约为

O(log⁡Vlog⁡n).O(\log V\log n).

这种写法适合需要直接找”下一次值变化位置”或配合离线区间查询的题;单纯扫全部子数组时通常 Rolling Vector 更短。

J-6. 赛时触发器#

看到下面这些特征就想 LogTrick:

  • “所有子数组的 GCD / AND / OR”
  • “固定右端点后,区间值只会变小/变大”
  • “要求统计某个区间运算结果等于 KK”
  • ”nn 很大,显然不能枚举 O(n2)O(n^2) 个区间,但值域只有 30/60 位”

一句话:固定一个端点,把连续产生同一运算结果的左端点压成一个状态;状态数靠因数链或 bit 单调性压到 O(log⁡V)O(\log V)。


K. 网格图 Hamilton 路径 / 回路:先看黑白染色#

使用场景#

  • 二维网格要求“一笔走完所有格子”、每格恰好经过一次。
  • 判断某两个指定端点之间能否存在 Hamilton 路径。
  • 网格删点、加边、加障碍后,需要先做快速无解判定。
  • 构造 Hamilton 回路/路径前,先检查奇偶性和黑白点数量。

K-1. 网格天然是二分图#

对格点 (x,y)(x,y) 按

c(x,y)=(x+y) mod 2c(x,y)=(x+y)\bmod 2

黑白染色。任意网格边都使 x+yx+y 的奇偶性翻转,因此每条边一定连接异色点。

所以任何路径颜色都严格交替:

B→W→B→W→⋯B\to W\to B\to W\to\cdots

这给 Hamilton 问题提供了最便宜也最常用的必要条件。

K-2. 黑白点数量#

设 (1,1)(1,1) 为黑点。

  • 若 nmnm 为偶数:
∣VB∣=∣VW∣=nm2.|V_B|=|V_W|=\frac{nm}{2}.
  • 若 nmnm 为奇数:
∣VB∣=nm+12,∣VW∣=nm−12.|V_B|=\frac{nm+1}{2},\qquad |V_W|=\frac{nm-1}{2}.

即黑点恰好多一个。

K-3. Hamilton 回路#

二分图中的任意环长度必为偶数,所以 Hamilton 回路必须满足

∣VB∣=∣VW∣.|V_B|=|V_W|.

对于完整矩形网格 Pn×PmP_n\times P_m:

存在 Hamilton 回路 ⟺n,m≥2\Longleftrightarrow n,m\ge2 且 nmnm 为偶数。

必要性来自二分图黑白平衡以及单行/单列无法成环;充分性可用标准蛇形构造。

若其中一维为偶数,例如 nn 为偶数,可以保留第一列作为“回边通道”,其余部分蛇形扫描,最后沿边界回到起点。

赛时记忆:

矩形完整网格要成 Hamilton 环:不能是一条链,并且总格子数必须是偶数。

K-4. Hamilton 路径的端点颜色#

Hamilton 路径经过 nmnm 个点,有 nm−1nm-1 条边。

nmnm 为偶数#

路径长度为奇数,首尾颜色必须不同:

c(s)≠c(t).c(s)\ne c(t).

也就是一个黑点、一个白点。

nmnm 为奇数#

路径长度为偶数,首尾颜色相同;同时因为黑点比白点多一个,所以若 (1,1)(1,1) 为黑点,则必须

c(s)=c(t)=0.c(s)=c(t)=0.

即两个端点都必须取多数色。

[!warning] 颜色条件通常只是必要条件 对“指定任意两个端点”的矩形网格 Hamilton 路径,除了颜色相容,还可能受到窄网格、边界位置、割结构等限制。竞赛中除非已经有对应定理或构造证明,否则不要直接把“颜色满足”当成充分条件。

所谓 Hamilton-laceable,强调的是二分图中颜色相容的两端点之间总能找到 Hamilton 路径。矩形网格的精确端点可行性有额外边界条件,做题时更实用的是:先用染色秒掉不可能,再针对剩余情况构造或 DP。

K-5. 删点 / 加边时的快速判定#

删点后想成 Hamilton 回路#

先统计剩余黑白点:

∣VB′∣≠∣VW′∣⟹一定无解.|V'_B|\ne|V'_W| \Longrightarrow \text{一定无解}.

但

∣VB′∣=∣VW′∣|V'_B|=|V'_W|

只是必要条件,不保证一定存在回路;障碍可能造成割点、死角或局部不可连通。

带障碍、规模较小的网格 Hamilton 回路通常考虑:

  • 轮廓线 DP / 插头 DP;
  • 状压 DP;
  • 根据题目特殊形状做构造。

完美匹配、最大流可以提供额外必要条件或辅助建模,但一般不能单独判定 Hamilton 回路存在性。

奇数网格额外加一条边#

原图黑点比白点多 11。若想形成经过全部点的 Hamilton 回路,回路中必须“补偿”一次颜色交替被打破。

因此新增边若仍然是黑白边,整体仍保持二分图,奇数个顶点不可能形成 Hamilton 环。

若有希望,新增边必须是同色边;在 (1,1)(1,1) 为黑色的标准染色下,尤其要关注黑—黑边。

K-6. 赛时触发器#

看到网格“一笔走完 / 每格恰一次 / 回到起点”,先做三件事:

  1. 染色:c(x,y)=(x+y) mod 2c(x,y)=(x+y)\bmod2。
  2. 数黑白点:回路要求相等;路径看端点颜色。
  3. 再检查结构:边界、障碍、割点、窄网格,最后才进入构造或插头 DP。

一句话:网格 Hamilton 问题先别急着搜路径,先用二分图黑白计数把不可能情况砍掉。


L. 概率与期望#

L-1. 概率计算#

独立事件的交集概率相乘,互斥事件的并集概率相加。

P(A∩B)=P(A)P(B∣A).P(A\cap B)=P(A)P(B\mid A).

只有独立时才能把 P(B∣A)P(B\mid A) 换成 P(B)P(B)。不放回抽样通常不独立。

至少发生一次,先算一次都不发生。各次独立、发生概率为 pip_i 时:

P(至少一次)=1−∏i(1−pi).P(\text{至少一次})=1-\prod_i(1-p_i).

事件不独立时,可用容斥:

P(⋃i=1nAi)=∑∅≠S⊆[n](−1)∣S∣+1P(⋂i∈SAi).P\left(\bigcup_{i=1}^n A_i\right) =\sum_{\varnothing\ne S\subseteq[n]}(-1)^{|S|+1} P\left(\bigcap_{i\in S}A_i\right).

L-2. 期望的性质#

离散变量按概率求和,有密度的连续变量按密度积分:

E[g(X)]=∑xg(x)P(X=x),E[g(X)]=∫g(x)fX(x) dx.E[g(X)]=\sum_x g(x)P(X=x),\qquad E[g(X)]=\int g(x)f_X(x)\,dx.

线性性不要求独立。

E[c+∑iwiXi]=c+∑iwiE[Xi].E\left[c+\sum_i w_iX_i\right]=c+\sum_iw_iE[X_i].

例如相邻差共享元素,仍然可以拆开算:

E[∑i=2n∣ai−ai−1∣]=∑i=2nE[∣ai−ai−1∣].E\left[\sum_{i=2}^n|a_i-a_{i-1}|\right] =\sum_{i=2}^nE[|a_i-a_{i-1}|].

若 X,YX,Y 独立,则 E[XY]=E[X]E[Y]E[XY]=E[X]E[Y]。但下面这些式子一般不成立:

E[X2]=E[X]2,E[∣X∣]=∣E[X]∣,E[X/Y]=E[X]/E[Y].E[X^2]=E[X]^2,\qquad E[|X|]=|E[X]|,\qquad E[X/Y]=E[X]/E[Y].

按第一步结果分类,就是全期望公式。设 BiB_i 是互斥且覆盖所有情况的事件:

E[X]=∑iP(Bi)E[X∣Bi].E[X]=\sum_iP(B_i)E[X\mid B_i].

期望 DP 的转移由此得到。

L-3. 指示变量与贡献法#

设 IiI_i 表示第 ii 个对象是否贡献,贡献为 11,否则为 00。那么

E[Ii]=P(Ii=1),E[∑iIi]=∑iP(Ii=1).E[I_i]=P(I_i=1),\qquad E\left[\sum_i I_i\right]=\sum_iP(I_i=1).

求数量的期望,往往只需要算单个对象被计入的概率。

问题 单个贡献的概率 期望
nn 个互异元素的均匀随机排列,逆序对数 每对下标为 1/21/2 n(n−1)/4n(n-1)/4
同上,前缀最大值个数 第 ii 位为 1/i1/i HnH_n
mm 个球独立均匀放入 nn 个盒子,非空盒子数 每盒为 1−(1−1/n)m1-(1-1/n)^m n[1−(1−1/n)m]n[1-(1-1/n)^m]

这里 Hn=∑i=1n1/iH_n=\sum_{i=1}^n1/i,H0=0H_0=0。

覆盖长度也可以按位置拆:整数位置求 ∑xP(x 被覆盖)\sum_xP(x\text{ 被覆盖}),连续区间求 ∫P(x 被覆盖) dx\int P(x\text{ 被覆盖})\,dx。

L-4. 尾和公式与最值#

非负整数变量:

E[X]=∑k=1∞P(X≥k),E[X2]=∑k=1∞(2k−1)P(X≥k).E[X]=\sum_{k=1}^{\infty}P(X\ge k),\qquad E[X^2]=\sum_{k=1}^{\infty}(2k-1)P(X\ge k).

证明只需把每个取值拆开:x=∑k=1x1x=\sum_{k=1}^x1,x2=∑k=1x(2k−1)x^2=\sum_{k=1}^x(2k-1)。

非负连续变量:

E[X]=∫0∞P(X>t) dt.E[X]=\int_0^{\infty}P(X>t)\,dt.

最值先求阈值概率。若 XiX_i 独立,Fi(t)=P(Xi≤t)F_i(t)=P(X_i\le t),则

P(max⁡iXi≤t)=∏iFi(t),P(min⁡iXi>t)=∏i(1−Fi(t)).P(\max_iX_i\le t)=\prod_iF_i(t),\qquad P(\min_iX_i>t)=\prod_i(1-F_i(t)).

求“最长长度、最大值、还能进行多少步”的期望时,可以先枚举阈值,算达到这个阈值的概率。

L-5. 成功次数与等待时间#

成功次数#

nn 次独立试验,每次成功率都是 pp,恰好成功 kk 次:

P(X=k)=(nk)pk(1−p)n−k,E[X]=np.P(X=k)=\binom nkp^k(1-p)^{n-k},\qquad E[X]=np.

成功率不同为 pip_i 时,E[X]=∑ipiE[X]=\sum_i p_i。恰好成功 kk 次的概率用 DP:

dp[i][k]=dp[i−1][k](1−pi)+dp[i−1][k−1]pi,dp[0][0]=1.dp[i][k]=dp[i-1][k](1-p_i)+dp[i-1][k-1]p_i, \qquad dp[0][0]=1.

从 NN 个物品中均匀不放回取 mm 个,其中 KK 个是目标物品:

P(X=k)=(Kk)(N−Km−k)(Nm),E[X]=mKN.P(X=k)=\frac{\binom Kk\binom{N-K}{m-k}}{\binom Nm},\qquad E[X]=\frac{mK}{N}.

不合法的组合数按 00 处理。

首次成功#

每次独立成功率为 p>0p>0,TT 包含成功那次:

P(T=k)=(1−p)k−1p,E[T]=1p.P(T=k)=(1-p)^{k-1}p,\qquad E[T]=\frac1p.

也可以写 E=1+(1−p)EE=1+(1-p)E,移项得 E=1/pE=1/p。

  • 只数成功前的失败次数:(1−p)/p(1-p)/p。
  • 等到累计 kk 次成功:k/pk/p。
  • 等到连续 kk 次成功:∑j=1kp−j\sum_{j=1}^k p^{-j}。

连续成功的式子可由状态方程推出。EjE_j 表示当前连续成功 jj 次,到结束还需的步数:

Ej=1+pEj+1+(1−p)E0(0≤j<k),Ek=0.E_j=1+pE_{j+1}+(1-p)E_0\quad(0\le j<k),\qquad E_k=0.

分阶段#

在阶段 ii,每次独立以概率 pi>0p_i>0 进入下一阶段,失败仍停在原阶段。总期望为

∑i1pi.\sum_i\frac1{p_i}.

每次独立均匀抽取 nn 种物品之一,已经有 kk 种时,抽到新种类的概率为 (n−k)/n(n-k)/n。集齐全部的期望为

E[T]=∑k=0n−1nn−k=nHn.E[T]=\sum_{k=0}^{n-1}\frac n{n-k}=nH_n.

只需集齐任意 mm 种,则为 n(Hn−Hn−m)n(H_n-H_{n-m})。各种物品概率不相等时,不能套这个式子。

L-6. 均匀分布#

设 L=r−lL=r-l,m=r−l+1m=r-l+1。

连续 U[l,r]U[l,r],L>0L>0 整数 l,l+1,…,rl,l+1,\dots,r 等概率
密度 / 单点概率 区间内密度 1/L1/L,单点概率为 00 每个整数概率 1/m1/m
E[X]E[X] (l+r)/2(l+r)/2 (l+r)/2(l+r)/2
Var⁡(X)\operatorname{Var}(X) L2/12L^2/12 (m2−1)/12(m^2-1)/12
E[X2]E[X^2] (l2+lr+r2)/3(l^2+lr+r^2)/3 ((l+r)/2)2+(m2−1)/12((l+r)/2)^2+(m^2-1)/12

连续分布除以 r−lr-l,整数分布除以 r−l+1r-l+1。l=rl=r 时是常数,期望为 ll、方差为 00。

连续均匀变量的分布函数:

FX(t)={0,t<l,(t−l)/L,l≤t≤r,1,t>r.F_X(t)=\begin{cases} 0,&t<l,\\ (t-l)/L,&l\le t\le r,\\ 1,&t>r. \end{cases}

区间概率等于交集长度除以 LL;整数分布则数交集中的整数个数,再除以 mm。

令 X=l+LUX=l+LU,U∼U[0,1]U\sim U[0,1],可以把一般区间化到 [0,1][0,1]。对整数 k≥0k\ge0:

E[Uk]=1k+1,E[Xk]=rk+1−lk+1(k+1)(r−l).E[U^k]=\frac1{k+1},\qquad E[X^k]=\frac{r^{k+1}-l^{k+1}}{(k+1)(r-l)}.

连续抽样:第 kk 小、最值和间隔#

在 [l,r][l,r] 中独立均匀取 nn 个点,排序后记为 X(1),…,X(n)X_{(1)},\dots,X_{(n)}:

E[X(k)]=l+kLn+1,E[X_{(k)}]=l+\frac{kL}{n+1},E[min⁡Xi]=l+Ln+1,E[max⁡Xi]=r−Ln+1,E[\min X_i]=l+\frac L{n+1},\qquad E[\max X_i]=r-\frac L{n+1},E[max⁡Xi−min⁡Xi]=n−1n+1L.E[\max X_i-\min X_i]=\frac{n-1}{n+1}L.

加上两个端点后,共有 n+1n+1 个间隔。各间隔同分布、总长为 LL,所以每个间隔的期望都是 L/(n+1)L/(n+1)。第 kk 小距左端点的长度是前 kk 个间隔之和。

整数抽样:有放回#

nn 次独立均匀取整数 l,…,rl,\dots,r,允许重复:

E[max⁡Xi]=l+∑j=1m−1(1−(jm)n),E[\max X_i]=l+\sum_{j=1}^{m-1}\left(1-\left(\frac jm\right)^n\right),E[min⁡Xi]=l+∑j=1m−1(m−jm)n.E[\min X_i]=l+\sum_{j=1}^{m-1}\left(\frac{m-j}{m}\right)^n.

由尾和公式得到,m=1m=1 时空和为 00。

整数抽样:不放回#

从 1,…,N1,\dots,N 中均匀选出 mm 个不同数,排序后为 S1<⋯<SmS_1<\cdots<S_m:

E[Sk]=k(N+1)m+1.E[S_k]=\frac{k(N+1)}{m+1}.

选中元素前后及之间共有 m+1m+1 个空隙,未选中元素共 N−mN-m 个。每个空隙中未选中元素数的期望为 (N−m)/(m+1)(N-m)/(m+1),于是 E[Sk]=k+k(N−m)/(m+1)E[S_k]=k+k(N-m)/(m+1)。

L-7. 均匀分布的距离#

点到区间#

X∼U[l,r]X\sim U[l,r],L=r−l>0L=r-l>0,固定点为 pp:

E[∣X−p∣]=(r−p)∣r−p∣−(l−p)∣l−p∣2L.E[|X-p|]=\frac{(r-p)|r-p|-(l-p)|l-p|}{2L}.

分段写法:

E[∣X−p∣]={(l+r)/2−p,p≤l,((p−l)2+(r−p)2)/(2L),l<p<r,p−(l+r)/2,p≥r.E[|X-p|]=\begin{cases} (l+r)/2-p,&p\le l,\\ \big((p-l)^2+(r-p)^2\big)/(2L),&l<p<r,\\ p-(l+r)/2,&p\ge r. \end{cases}

两个区间#

X∼U[a,b]X\sim U[a,b]、Y∼U[c,d]Y\sim U[c,d] 独立,A=b−a>0A=b-a>0、B=d−c>0B=d-c>0:

E[∣X−Y∣]=∣b−c∣3+∣a−d∣3−∣a−c∣3−∣b−d∣36AB.\boxed{E[|X-Y|] =\frac{|b-c|^3+|a-d|^3-|a-c|^3-|b-d|^3}{6AB}}.

推导:联合密度为 1/(AB)1/(AB),而

∫cd∣x−y∣ dy=(x−c)∣x−c∣−(x−d)∣x−d∣2,\int_c^d|x-y|\,dy =\frac{(x-c)|x-c|-(x-d)|x-d|}{2},∫ab∫cd∣x−y∣ dy dx=[∣x−c∣3−∣x−d∣36]ab.\int_a^b\int_c^d|x-y|\,dy\,dx =\left[\frac{|x-c|^3-|x-d|^3}{6}\right]_a^b.

区间相离、相交、包含都适用。一个区间退化为点时用“点到区间”;两个都是点时直接取绝对差。

若 b≤cb\le c,直接算 E[Y]−E[X]=(c+d−a−b)/2E[Y]-E[X]=(c+d-a-b)/2。

同一区间#

X,YX,Y 独立同分布:

| | E[∣X−Y∣]E[|X-Y|] | E[(X−Y)2]E[(X-Y)^2] | | --- | --- | --- | | 连续区间,长度 LL | L/3L/3 | L2/6L^2/6 | | 整数区间,共 mm 个数 | (m2−1)/(3m)(m^2-1)/(3m) | (m2−1)/6(m^2-1)/6 |

整数绝对差按距离枚举:距离 k>0k>0 的有序数对有 2(m−k)2(m-k) 对,所以

E[∣X−Y∣]=2m2∑k=1m−1k(m−k)=m2−13m.E[|X-Y|]=\frac2{m^2}\sum_{k=1}^{m-1}k(m-k)=\frac{m^2-1}{3m}.

同一连续区间中,距离不超过 tt 的概率为

P(∣X−Y∣≤t)=2tL−t2L2,0≤t≤L.P(|X-Y|\le t)=\frac{2t}{L}-\frac{t^2}{L^2},\qquad 0\le t\le L.

可在边长为 LL 的正方形中,减掉 ∣x−y∣>t|x-y|>t 对应的两个三角形来推。

两个数的大小关系#

仍设两个区间非退化且独立,记 z+=max⁡(z,0)z_+=\max(z,0):

P(X≤Y)=(d−a)+2−(d−b)+2−(c−a)+2+(c−b)+22AB.P(X\le Y)=\frac{(d-a)_+^2-(d-b)_+^2-(c-a)_+^2+(c-b)_+^2}{2AB}.

由 P(X≤Y)=1B∫cdFX(y) dyP(X\le Y)=\frac1B\int_c^dF_X(y)\,dy 积分得到。

这里 P(X=Y)=0P(X=Y)=0。整数分布则需要另算相等概率,不能混用 << 和 ≤\le。

L-8. 二阶矩与方差#

Var⁡(X)=E[X2]−E[X]2.\operatorname{Var}(X)=E[X^2]-E[X]^2.

计算总贡献平方时,展开成单项和成对贡献:

E[(∑iXi)2]=∑iE[Xi2]+2∑i<jE[XiXj].E\left[\left(\sum_iX_i\right)^2\right] =\sum_iE[X_i^2]+2\sum_{i<j}E[X_iX_j].

对指示变量,Ii2=IiI_i^2=I_i,E[IiIj]=P(Ii=Ij=1)E[I_iI_j]=P(I_i=I_j=1)。因此计数的方差通常需要算“两件事同时发生”的概率。

独立时:

Var⁡(∑iXi)=∑iVar⁡(Xi).\operatorname{Var}\left(\sum_iX_i\right)=\sum_i\operatorname{Var}(X_i).

独立试验的成功次数,方差为 ∑ipi(1−pi)\sum_i p_i(1-p_i)。

两个独立变量的平方差:

E[(X−Y)2]=Var⁡(X)+Var⁡(Y)+(E[X]−E[Y])2.E[(X-Y)^2]=\operatorname{Var}(X)+\operatorname{Var}(Y)+(E[X]-E[Y])^2.

L-9. 期望 DP#

正推#

按步数分层或在 DAG 上,维护:

  • PsP_s:到达状态 ss 的概率。
  • FsF_s:到达状态 ss 的所有情况中,累计得分乘概率的和。

边 s→ts\to t 的转移概率为 pp,新增得分为 ww:

Pt+=pPs,Ft+=p(Fs+wPs).P_t\mathrel{+}=pP_s,\qquad F_t\mathrel{+}=p(F_s+wP_s).

初始状态 P=1,F=0P=1,F=0,答案为所有终止状态的 FF 之和。FsF_s 已经包含到达概率,新增得分仍需乘 PsP_s。

倒推#

EsE_s 表示从状态 ss 出发,到结束还需要的期望代价。转移概率为 pstp_{st}、单步代价为 wstw_{st}:

Es=∑tpst(wst+Et).E_s=\sum_t p_{st}(w_{st}+E_t).

没有终点奖励时 Eend=0E_{\mathrm{end}}=0。每步代价都是 11 时:

Es=1+∑tpstEt.E_s=1+\sum_t p_{st}E_t.

自环概率为 q<1q<1,移项:

Es=1+∑t≠spstEt1−q.E_s=\frac{1+\sum_{t\ne s}p_{st}E_t}{1-q}.

有一般环依赖时写线性方程组,不能直接记忆化递归。先检查是否可能进入无法到达终点的状态;若能以正概率进入,结束步数的期望为无穷大。

状态需包含决定后续转移的全部信息。例如连续成功题要记当前连击长度,不能只记已经进行多少次。

二阶矩转移#

QsQ_s 表示从 ss 出发,剩余总代价平方的期望。边代价 wstw_{st} 固定时:

Qs=∑tpst(wst2+2wstEt+Qt).Q_s=\sum_t p_{st}(w_{st}^2+2w_{st}E_t+Q_t).

先求 EsE_s,再求 QsQ_s,方差为 Qs−Es2Q_s-E_s^2。

相关:期望DP。

L-10. 取模#

有理数 P/QP/Q 的模表示为 P⋅Q−1P\cdot Q^{-1}。模数 MM 为质数且 Q≢0(modM)Q\not\equiv0\pmod M 时:

Q−1≡QM−2(modM).Q^{-1}\equiv Q^{M-2}\pmod M.
  • 百分比转为 p⋅100−1p\cdot100^{-1},固定分母的逆元只算一次。
  • 比较大小、取绝对值、取 z+z_+,都在取模前做。
  • 连乘逐步取模,三次方不要直接在原整数上计算。
  • 自环移项的 1−q1-q 也要检查是否可逆。实数意义下非零,不代表模意义下非零。
  • 大量非零分母可用前缀积和倒推批量求逆,只求一次总乘积的逆元,复杂度 O(n+log⁡M)O(n+\log M)。
  • 分母模 MM 为 00 时不能硬求逆。先在有理数层面约分,最终分母仍与 MM 不互质,则这种模表示不存在。

M. 切比雪夫距离与曼哈顿距离#

设 P=(x1,y1),Q=(x2,y2)P=(x_1,y_1),Q=(x_2,y_2):

  • 曼哈顿距离:d1(P,Q)=∣x1−x2∣+∣y1−y2∣d_1(P,Q)=|x_1-x_2|+|y_1-y_2|。
  • 切比雪夫距离:d∞(P,Q)=max⁡(∣x1−x2∣,∣y1−y2∣)d_\infty(P,Q)=\max(|x_1-x_2|,|y_1-y_2|)。

将每个点变换为 T(x,y)=(x+y,x−y)T(x,y)=(x+y,x-y),则:

d1(P,Q)=d∞(T(P),T(Q))\boxed{d_1(P,Q)=d_\infty(T(P),T(Q))}d∞(P,Q)=12d1(T(P),T(Q))\boxed{d_\infty(P,Q)=\frac12d_1(T(P),T(Q))}

即:原曼哈顿 = 新切比雪夫;原切比雪夫 = 新曼哈顿的一半。


N. 离散介值性质与非单调二分#

N-1. 使用场景#

固定长度的窗口每次右移一格,只移出左端点、加入右侧新点。若每个位置的贡献为 0 或 1,窗口统计量每次只能变化 −1,0,1-1,0,1。

当题目要求找到 f(s)=kf(s)=k 的某个位置时,可以检查相邻位置的差值是否至多为 1。此时即使 ff 不单调,只要找到函数值位于 kk 两侧的两个端点,也能二分出一个解。

N-2. 离散介值性质#

命题:设整数区间 [L,R][L, R] 上的整数值函数 f:Z∩[L,R]→Zf: \mathbb{Z}\cap[L, R]\to\mathbb{Z} 满足对任意整数 x∈[L,R−1]x\in[L, R-1] 均有 ∣f(x+1)−f(x)∣≤1|f(x+1) - f(x)| \le 1。 对任意整数 kk:

  • 若 f(L)>k≥f(R)f(L) > k \ge f(R) 且 L<RL < R,则必存在整数 s∈(L,R]s \in (L, R] 满足 f(s)=kf(s) = k。
  • (反向跨越版本)若 f(L)<k≤f(R)f(L) < k \le f(R) 且 L<RL < R,则同样必存在整数 s∈(L,R]s \in (L, R] 满足 f(s)=kf(s) = k。

证明(以 f(L)>k≥f(R)f(L) > k \ge f(R) 为例): 考虑集合 S={x∈[L,R]∣f(x)≤k}S = \{x \in [L, R] \mid f(x) \le k\}。

  1. 因为 R∈SR \in S,故 SS 是有限非空整数集,必存在最小元素 s=min⁡Ss = \min S。
  2. 因为 f(L)>kf(L) > k,故 L∉SL \notin S,由此可知 s>Ls > L。
  3. 由 ss 的最小性,其前驱位置 s−1∉Ss - 1 \notin S,即 f(s−1)>kf(s-1) > k。由于函数值为整数,这意味着 f(s−1)≥k+1f(s-1) \ge k + 1。
  4. 根据单步差分约束,每步至多下降 1:f(s)≥f(s−1)−1≥kf(s) \ge f(s-1) - 1 \ge k。
  5. 结合 s∈Ss \in S 的定义 f(s)≤kf(s) \le k,两式夹逼立得 f(s)=kf(s) = k。

N-3. 非单调二分#

这里不要求 ff 单调,也不要求判定式 f(s)>kf(s)>k 构成一个连续前缀。

算法维护当前搜索区间 [L,R][L, R],其循环不变式始终为:

f(L)>k且f(R)≤kf(L) > k \quad \text{且} \quad f(R) \le k
  1. 取 mid=⌊(L+R)/2⌋\mathrm{mid} = \lfloor(L + R) / 2\rfloor。
  2. 若 f(mid)>kf(\mathrm{mid}) > k,更新 L←midL \leftarrow \mathrm{mid};否则更新 R←midR \leftarrow \mathrm{mid}。
  3. 循环终止条件为 L+1=RL + 1 = R(区间长度缩减为 1,两端点为相邻整数)。
  4. 相邻端点收敛正确性:终止时由不变式可知 f(L)≥k+1f(L) \ge k + 1 且 f(R)≤kf(R) \le k。又由单步变化约束 ∣f(R)−f(L)∣≤1|f(R) - f(L)| \le 1,两端至多相差 1,因此两个不等式必然同时取等,推导出 f(L)=k+1f(L) = k + 1 且 f(R)=kf(R) = k。

被丢弃的半边可能也有解,但保留下来的两端始终分别满足 f(L)>kf(L)>k 与 f(R)≤kf(R)\le k。二分只利用这两个端点的跨越关系,直到它们相邻;并不是在求单调分界点。

N-4. 实例:CF Target Infection#

题意抽象:数轴上给定若干互不相交的闭区间 [li,ri][l_i, r_i](均为感染点,其余为 0)。给定检测窗口长度 mm 与目标感染数 kk,求是否存在窗口 [s,s+m−1][s, s + m - 1] 使得其中的感染点数恰好为 kk。

  1. 单步变化性质: 设 a(x)∈{0,1}a(x) \in \{0, 1\} 为坐标 xx 是否被感染的示性函数。窗口以 ss 为左端点,包含感染点数为 f(s)f(s),则平移一步的变化为: f(s+1)−f(s)=a(s+m)−a(s)∈{−1,0,1}f(s+1) - f(s) = a(s+m) - a(s) \in \{-1, 0, 1\}
  2. 全局最大值必可在某个 lil_i 处取到: 设某个窗口 [s∗,s∗+m−1][s^*, s^* + m - 1] 取得全局感染点数最大值:
    • 若 s∗s^* 为非感染点且右侧还有感染区间,向右平移至下一个区间左端点 lil_i。平移时左端移出的全是 0,右端移入点数非负,ff 不减。若 s∗>rns^*>r_n,则 f(s∗)=0f(s^*)=0,而 f(ln)≥1f(l_n)\ge1,因此这不可能是最大值点;
    • 若 s∗s^* 落在某个感染区间内部且 s∗>lis^* > l_i,向左平移窗口至 lil_i。平移期间左端移入的全是 1,右端移出点数至多等于移入点数,ff 不减。
    • 故枚举所有区间的左端点 lil_i,必能覆盖到至少一个全局最大值。
  3. 算法流程与边界处理:
    • 遍历所有 lil_i 计算 f(li)f(l_i):
      • 若中途直接命中 f(li)=kf(l_i) = k,直接输出 lil_i 即可(包含 k=0k = 0 时若恰好有 f(li)=0f(l_i) = 0);
      • 若存在 f(li)>kf(l_i) > k,记录任意一个满足条件的端点作为二分左端点 LL;
    • 若所有 lil_i 均满足 f(li)<kf(l_i) < k,由于最大值亦严格小于 kk,问题直接无解;
    • 确定 LL 后,取右端点 R=rn+1R = r_n + 1。因为窗口完全落在所有感染区间右侧,窗口内感染数为 f(R)=0f(R) = 0。对于任意非负目标 k≥0k \ge 0,均满足 f(R)=0≤kf(R) = 0 \le k;特别地若 k=0k = 0,此处可直接确定有解;
    • 此时满足 L<RL < R 且 f(L)>k≥f(R)f(L) > k \ge f(R),直接调用非单调二分,返回收敛时的 RR 即可。
  4. O(log⁡n)O(\log n) 快速求 f(s)f(s):
    • 令 F(x)F(x) 为坐标 ≤x\le x 的感染点总数,则 f(s)=F(s+m−1)−F(s−1)f(s) = F(s + m - 1) - F(s - 1)。
    • 区间互不相交,维护各区间长度的前缀和。用 std::upper_bound 找到最后一个满足 lj≤xl_j\le x 的区间,再计算 pre[j−1]+min⁡(x,rj)−lj+1pre[j-1]+\min(x,r_j)-l_j+1;没有这样的区间时取 0。即使 xx 位于两个区间的空隙中,公式也成立。单次计算为 O(log⁡n)O(\log n)。
    • 坐标与前缀长度可能达到 101510^{15},相关计算需统一使用 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;
ll L = -1;
for (int i = 1; i <= n; ++i) {
ll val = f(l[i]);
if (val == k) return l[i];
if (val > k) {
L = l[i];
break;
}
}
if (L == -1) return -1; // 最大感染数小于 k
ll R = r[n] + 1; // f(L) > k,f(R) = 0 <= k
while (L + 1 < R) {
ll mid = L + (R - L) / 2;
if (f(mid) > k) L = mid;
else R = mid;
}
return R; // 相邻时必有 f(R) == k
};
cout << find_s() << '\n';

局限:若每步可跳过整数目标(如 2→02\to0 找 1),结论不成立;两端未跨越 kk 时也不适用。


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保留。结构证明、输入边界与可运行代码分别见:

算法竞赛 Classic Tricks 复习笔记
https://sanzenin.top/posts/obsidian/经典trick/
作者
Sanzenin 凪
发布于
2026-11-16
许可协议
CC BY-NC-SA 4.0

分享文章

生成精美分享图或复制链接,与更多人分享本文。

继续阅读

沿着主题读

基于共同的标签与分类

换条路线

从其他文章中稳定抽取