4363 字
22 分钟
算法竞赛个人易错点

算法竞赛个人易错点#

这份清单以“发现性质 → 定义状态 → 证明正确 → 检查实现”为顺序。目标是每个问题都有一个可以立刻执行的动作,而不是泛泛地提醒仔细。

证据范围#

  • 对话摘要:2026-07至10 算法三个月回顾(用户提供) 与 2026-10 算法对话回顾(用户提供)。名义范围 2026-07-25 至 10-25,主要记录集中在 8 月中下旬后;没有独立读取原始网页会话,不把摘要中的追问算成错误次数。
  • 本地核对:读取 /home/sanzenin/test/algo 的代码及相关讲解;当前版本可能已经修复当时错误。
  • 实现复现:对明确的整数移位问题运行 UBSan。其余条件性风险会写明输入前提,不能等同于原题 WA。
  • 优先级是复习建议,不是统计错误率;本次没有批量修改你的题目解答。
  • 归因:Hydra 首版 WA 来自先前助手代码,不算用户代码错误;只作为历史信息不足的模型反例。

1. 动态过程:太早进入算法,漏掉不变量#

对话摘要中的最高位递归和 Slot Machine,都属于“自然模型复杂,换个状态很短”。

开写前花两分钟做这三件事:

  1. 手动操作三个状态,写出共同保留的对象。
  2. 把“历史”改写成已保留集合、极值、差值、计数或顺序统计量。
  3. 检查只给这个压缩状态,是否能恢复下一次操作。

例:Slot Machine 在“先删最大、再补新数”的规则下,状态是历史最小 n−1n-1 个数加最新值。原理和最终样本数见 算法竞赛数学套路。

停止条件:找不到性质时再进入 DP / 搜索;不要因为“像按位题”就默认每位独立。若某操作重置了连续计数,逐位状态必须体现重置,或按最高位分段处理。

2. DP:同时检查“少存了什么”和“多存了什么”#

充分性判据:同一状态的任意两段历史,未来允许的决策和最优剩余代价是否相同?相同才能合并。

冗余性判据:某个维度能否由其他维度唯一算出?能就不必存。

本人近期场景 判断 立刻执行
状压分组 dp[mask][rem] rem=sum[mask]%T 可恢复 删余数维,单独检查 T>0、空集与答案换算
Cryptarithm 当前块位置 对话里提出的是合理质疑 看状态定义是否含最后选到的位置
括号树 深度、已处理兄弟和祖先前缀是不同量 画含两棵子树的括号森林再标状态
树形 DP 同一节点不同父边约束可能影响未来 明确树根、状态参数和转移依赖

可直接查看 本地 Cryptarithm 讲解。其中 fj(i)f_j(i) 已定义为“当前副本最后选在位置 ii”,没有缺少这个位置。副本数已计入费用,不必再存。预收整份删除费 W=x+nzW=x+nz 后,每保留一项退还 zz,转移为

fj(i)=min⁡(min⁡t<ifj−1(t),min⁡tfj−1(t)+W)+y∣ai−bj∣−z.f_j(i)=\min(\min_{t<i}f_{j-1}(t),\min_tf_{j-1}(t)+W)+y|a_i-b_j|-z.

不要把你对状态的追问误写成“你提交了状态不足的错误解”。

3. 概率:先用一句中文说清事件#

对话摘要明确记录过把 1m(k/m)n−1\frac1m(k/m)^{n-1} 当成最大值恰为 kk 的概率。

这其实固定了一个样本等于 kk,其他样本不超过 kk。正确事件应为“所有样本不超过 kk,但不全小于 kk”:

P(max⁡Xi=k)=(k/m)n−((k−1)/m)n.P(\max X_i=k)=(k/m)^n-((k-1)/m)^n.

固定反例 n=2,m=2:四种结果,最大值为 2 的有三种,概率 3/43/4。若你的式子算不出它,先修事件再写代码。

连续顺序统计的分母为“参与排序样本数 + 1”。Slot Machine 最新样本被单独保留时,不参与旧历史最小值的排序;本地 nowcoder_2026_summer/10/e.cpp:17 分母为 n+kn+k,要从 n+k−1n+k-1 个旧样本解释,不能死背。

4. SOS:先画包含方向,费用另算#

对话摘要中的 Retest Queue 涉及超集方向、拒绝费用;没有完整题面,不能补造它的费用公式。

通用检查用两位掩码:

  • 01 的子集是 00,01。
  • 01 的超集是 01,11。
  • 所有“包含我要求的特征”的候选,应查询超集。
  • x & y == 0 应查询固定位宽补集的子集,不是超集。

写注释 dp[S] = ... 后再写循环。费用必须按接受/拒绝事件分别列式,不能因为 SOS 统计了人数就默认这些人都支付同样费用。

5. 计数:先固定见证对象#

对话摘要中 Matrix Game 的 kak^a 漏了“相同取值属于同一组行”的要求。

以后每个乘法因子旁写含义:“先选哪组行”“再选颜色”“后选列”。如果两个因子都在重新挑行组,它们通常不能直接相乘。鸽巢前把鸽子和巢写成具体元组。

最小验证:取 2–3 行、2–3 列,枚举矩阵或选择对象,检查“同一行组”是不是被多个局部选择偷换。

6. 贪心 / 博弈:可行不等于最优#

循环排列奇偶策略等问题在摘要中属于证明理解,不直接记为错误。

用两段式证明:

  1. 能保证:给出一个合法策略,说明不变量如何持续。
  2. 不能更好:给出对手反制、下界或交换论证,封住更优结果。

若证明“只考虑这几种情况”,必须说明任意其他方案如何归约到它们。小规模 Minimax 可帮助发现策略,但打表一致不能代替证明;有循环的博弈还需定义终止和和局。

7. 位操作:类型由左操作数决定#

本地确定问题:cf/cf1077/d.cpp 循环包括 i=32,重建时使用 (bit_p << i)、(bit_q << i);bit_p 是 int。即使赋给 long long,右侧也已按 32 位移位。UBSan 对输入 1\n1 1\n 可复现“shift exponent 32 … 32-bit type int”。

修正形式:(1ULL * bit_p << i),并保证 0<=i<64。若结果必须为有符号数,还需保证最高位不会越过可表示范围。

// GNU C++17;只对非零 unsigned long long x 调用
int low = __builtin_ctzll(x); // 最低 1 的位号
int high = 63 - __builtin_clzll(x); // 最高 1 的位号

0 要先特判;1 << k 的位宽仍是 int,1ULL << k 才是无符号 64 位。

8. 128 位:把强制转换移到第一个危险运算前#

摘要记录过中间乘法先溢出的问题。本地 26xian/h.cpp 也保留了条件性风险:

cur += (__int128)(pos - last) * (x - y * cnt);
// y*cnt 与 pos-last 都先以 long long 计算。
// 如果参数上界允许超过 long long,改为:
cur += ((__int128)pos - last) * ((__int128)x - (__int128)y * cnt);

是否触发依赖原题上界,本次未把它宣判为原题 WA。sum、累加量和最终 (long long)ans 也要核对范围。打印 128 位使用配套 to_string128,不要为了输出强行缩回 64 位。

9. 扫描线:每次只推进一个明确动作#

摘要记录过 i++, cnt += events[i].second 先跳索引的错误。当前 26xian/h.cpp 已使用先读再递增,不能记为仍未修复。

推荐固定写法:

while (i < events.size() && events[i].first == pos) {
cnt += events[i].second;
++i;
}

顺序固定为“用旧斜率走到 pos → 记录值 → 合并 pos 的全部事件”。测试同坐标两个开始事件、开始与结束重合、零长度区间。没有证明单峰时,不把断点扫描随意替换成三分。

10. DFS、左偏树、括号树:结构检查不能只靠样例#

摘要中的结构错误建立以下固定检查:

对象 不变量 极小数据
DFS 从根调用;无向边跳父亲;孩子先算完再合并 单点、长度 3 的链、星形树
DP 叶子值正确,不可达不会被普通 0 混入 不能选择任何对象的状态
左偏树 堆序;左 dist >= 右 dist;dist=右 dist+1 空堆合并、单点 pop、重复键
空堆 dist[0]=0、新叶子 dist=1(或统一另一套约定) merge(0,0)
括号树 0 仅作为虚拟根,真实点从 1 起 ()、()()、(())
反对角线 i+j=di+j=d 时 max(1,d-m)<=i<=min(n,d-1) 1x1、1xm、nx1、2x3

如果同时处理相邻对角线的并集,范围可能要包含哨兵 0,必须注明;不能用一个看似宽松的区间默默访问真实数组以外的位置。

本地 nowcoder_2026_summer/3/j.cpp 对新节点设置 dist=1,空点默认 0;它体现了正确的一套约定。

11. 递归必须有严格下降的量#

摘要记录最高位递归在 n=2,3n=2,3 可能不缩小。本地 cf/cf1129/d1.cpp 目前只有小值分支和未完成的主体,不是可直接用的模板,也不能从它推断完整递推正确。

对每条递归边写出 measure(next)<measure(cur)measure(next)<measure(cur);可用 n、剩余位数、未处理节点数或字典序二元组。把 0、1、2、3 逐个代入,若出现自己调自己,增加基例或改递推。

12. 状态规模与内存是实现的一部分#

  • nowcoder/8/m.cpp 分配约一百万个 vector<int>(28):仅 int 负载约 106.8 MiB,另有约 22.9 MiB 的 vector 对象(典型 64 位实现)和一百万次堆分配开销。更适合连续 vector<array<int,26>> 或按实际 Trie 节点数分配。
  • cf/1523D.cpp 抽样 20 次;若一次命中支持最优答案的样本概率至少 1/2,且各次独立,理论漏掉概率至多 2−202^{-20}。仍需证明行内压缩位数小,否则 2siz2^{siz} 无法承受。
  • 2222^{22} 个 int 约 16 MiB,long long 约 32 MiB;有多份数组时按峰值相加。时间按轮数乘 B2BB2^B,不能只看一次 SOS。
  • 哈希/随机化要注明正确性概率;TODO、空 solve、未完成函数不能仅凭能编译就收入可用模板。本地 cf/453A.cpp 是空壳,应使用已推导的公式而非复制这个文件。

13. 已核对的笔记错误#

本次修正 DIRICHLET卷积以及莫比乌斯反演.md 的两处数学表达:

  1. 欧拉函数为 φ(n)=∑i=1n[gcd⁡(i,n)=1]\varphi(n)=\sum_{i=1}^n[\gcd(i,n)=1],示性条件在方括号内。
  2. Dirichlet 卷积与莫比乌斯反演对任意算术函数成立,不要求积性。积性是在需要利用质因子独立计算时附加的性质。

这两处是笔记校订证据,不等于近期对话里反复出错。

三个月新增:相同模式在不同题型中的表现#

重复键不是可以随意丢弃的历史#

摘要中树上碰撞的 rev[x][dep[x]+s]=i 覆盖前一人。最小反例:一个节点、两个人同在时刻 0 出生,应该立即碰撞。

插入映射前先问:同 key 的两个对象是否等价,还是它们相遇就是事件? 对应处理可为计数、保存全部 ID、插入失败即触发;不是一律把 map 改 multimap。比如只维护最小费用时,同 key 取 min 就合理。

树上差分:先确定恢复的是边还是根路径#

两端点 XOR 标记 d[u]^=1,d[v]^=1 后,恢复边覆盖奇偶要子传父。对子树边 (parent[v],v)(parent[v],v),删边形成的割中,每条路径跨割当且仅当一个端点在子树内,因此子树 XOR 就是边覆盖奇偶。

父传子通常恢复已定义的根到点前缀;它不能替代端点标记的子树汇总。调用 cp::tree_path_xor_edges 可得到按输入边顺序的覆盖奇偶,采用迭代遍历避免深链递归。

回滚与清理是算法的一部分#

DSU on Tree 的 keep=false 分支,对自己临时加入的状态必须清理,即使已经找到答案。虚树的邻接边、访问标记、多测答案集合也都要明确归属。

固定写法是先保存 found,继续执行必要清理,再返回。也可让每次 check 拥有独立局部容器,或用作用域恢复器。不能把 keep=true 的保留状态一并清空,应逐项说明哪些状态归本层所有。

测试:连续调用同一 check 两次应得相同结果;交换兄弟处理顺序应不改变答案;两组测试用例交换顺序后输出只交换、不变化。

数值域、位置域、压缩编号分清#

约数扫描线摘要中的 divisors[i]/divisors[a[i]]、扫 ma/扫 n,与 MEX 中 j*i/j*x、pre/dp 混用,根源都是变量含义漂移。

对每个数组写一句 数组[谁] = 什么:divisors[value]、last[valueId]、dp[prefixLength]、events[position]。把 idx、value、rank 分开命名,离散编号只能用于比较/索引,原始距离不能用编号差代替。

差值 DP 封装 idx(d)=d+offset,包括初始化 idx(0);切勿只给转移加 offset。

二分必须证明边界与整个检查复杂度#

Gas Station 的“容量至少最大边权”仅在不能在边内部增设站、完整走边需要足够油量的模型下成立;若允许边内加站,结论要重证。题名不能代替题意。

开区间二分先写 check(lo)=false,check(hi)=true(或相反),推导上界或在有可行性保证时扩大上界;无解和乘二溢出单独处理。复杂度按 轮数 × check 算,嵌套 LCA 再乘 log⁡n\log n;不要把判定扫描误认为一次总共只扫一遍。

最短路边内部必须比较两个入口#

CF144D 边 (u,v,w)(u,v,w) 上、距 u 为 x 的点:

D(x)=min⁡(dis[u]+x,dis[v]+w−x).D(x)=\min(dis[u]+x,dis[v]+w-x).

候选 x=L−dis[u]x=L-dis[u] 必须满足 0<x<w0<x<w,以及另一方向 dis[v]+w−x≥Ldis[v]+w-x\ge L。等号表示从两端得到同一个候选,要去重。最小反例:只有一条长度 10 的边,却有另一条路让 dis[u]=dis[v]=0;从 u 看 x=7 是 L=7,但实际最短距离是 3。(可用两端与源点各连零权边实现;若原题边权要求正,可统一把两端距离改为 1、目标改为 8。)

本地 cf/144D.cpp 当前已比较另一端,等号用顶点编号约束去重;摘要中的错误不应写成当前版本仍存在。

概率必须覆盖全部类别#

Erratic Lights 的“方案数漏除总方案数”和 CF1418E 的“漏弱怪贡献”是两类错误。前者核对样本空间权重;后者把对象分类后逐类写指示变量。

强怪被挡不代表弱怪永远不造成伤害:盾牌破后遇到弱怪仍可能贡献。强怪数量恰等于耐久时,是检测“强怪贡献为 0、弱怪仍可能非零”的有效边界。公式与假设见 算法竞赛数学套路。

BFS、容器与几何的固定动作#

  • BFS 每次取队首后立即 pop;visited/距离在入队时更新,避免重复入队。
  • erase(first,last) 使用半开区间;空范围是 first==last,别把结尾迭代器解引用。
  • 先明确输出是否需要操作数,再输出完整操作序列;回放操作验证最终状态与每步合法性。
  • 反三角函数前检查几何是否有解,再对理论在 [-1,1] 的值 clamp;不能靠 clamp 掩盖本来无交点的情况。
  • 构造图的父边来自指定遍历树,验证源点可达及构造后算法产生的顺序;输入顺序不天然等于遍历顺序。

三个月二刷清单#

这些题名来自用户提供的回顾;没有完整题面/官方编号的条目暂不补造链接。每题完成的标准是恢复性质、证明和代码,而不是读完题解。

  • 树上碰撞:两个相同键触发事件,不被覆盖。
  • Gas Station:解释站点位置限制、可行上下界、深链。
  • Erratic Lights:每项权重说明概率空间、全部下标合法。
  • Canal Crossing:用割解释子传父,手算三点链。
  • RGB 分段:两个前缀差推偏序,query在insert前。
  • MEX 区间计数:变量含义不漂移、空区间、重叠约束、小规模暴力。
  • DSU on Tree + XOR:keep=false清理、重复check、兄弟顺序无关。
  • CF1418E:强怪和弱怪两类贡献、强怪数等于耐久。
  • CF144D:两个入口、边端点、相等候选去重。
  • Cryptarithm:说清最后位置、开新副本、P更新时机。

提交前九项检查#

  • 写出一个可验证的不变量 / 单调性 / 结构化简。
  • DP 状态足以决定未来,没有可推导的多余维度。
  • 贪心或博弈有“能保证”和“不能更好”两部分。
  • 概率事件、计数见证、子集 / 超集方向写成一句中文。
  • DFS 有入口,父亲与叶子处理一致,深链考虑递归栈。
  • 每个递归分支严格缩小,0、1、2、3 都能终止。
  • 空集、虚拟点、闭区间、同坐标事件合法。
  • 乘法、减法、移位先确定类型;模减法规范化;分母可逆。
  • 手算重复值与边界;需要时用不同思路的暴力对拍。

一轮复盘怎么用#

每道题只记四行:题面触发器 → 我漏掉的性质 → 最小反例 → 下次固定动作。没有出错、只是认真追问证明的题,记录为“证明待巩固”。

优先补:最大值概率、SOS 方向、mask 删维、最高位递归收缩、同坐标事件。每题写五行状态 / 证明,比重复复制模板更有针对性。

相关:算法竞赛数学套路、算法竞赛模板增补、经典Trick。

算法竞赛个人易错点
https://sanzenin.top/posts/obsidian/算法竞赛个人易错点/
作者
Sanzenin 凪
发布于
2026-10-25
许可协议
CC BY-NC-SA 4.0

分享文章

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

继续阅读

沿着主题读

基于共同的标签与分类

换条路线

从其他文章中稳定抽取