算法竞赛个人易错点
这份清单以“发现性质 → 定义状态 → 证明正确 → 检查实现”为顺序。目标是每个问题都有一个可以立刻执行的动作,而不是泛泛地提醒仔细。
证据范围
- 对话摘要:2026-07至10 算法三个月回顾(用户提供) 与 2026-10 算法对话回顾(用户提供)。名义范围 2026-07-25 至 10-25,主要记录集中在 8 月中下旬后;没有独立读取原始网页会话,不把摘要中的追问算成错误次数。
- 本地核对:读取
/home/sanzenin/test/algo的代码及相关讲解;当前版本可能已经修复当时错误。 - 实现复现:对明确的整数移位问题运行 UBSan。其余条件性风险会写明输入前提,不能等同于原题 WA。
- 优先级是复习建议,不是统计错误率;本次没有批量修改你的题目解答。
- 归因:Hydra 首版 WA 来自先前助手代码,不算用户代码错误;只作为历史信息不足的模型反例。
1. 动态过程:太早进入算法,漏掉不变量
对话摘要中的最高位递归和 Slot Machine,都属于“自然模型复杂,换个状态很短”。
开写前花两分钟做这三件事:
- 手动操作三个状态,写出共同保留的对象。
- 把“历史”改写成已保留集合、极值、差值、计数或顺序统计量。
- 检查只给这个压缩状态,是否能恢复下一次操作。
例:Slot Machine 在“先删最大、再补新数”的规则下,状态是历史最小 个数加最新值。原理和最终样本数见 算法竞赛数学套路。
停止条件:找不到性质时再进入 DP / 搜索;不要因为“像按位题”就默认每位独立。若某操作重置了连续计数,逐位状态必须体现重置,或按最高位分段处理。
2. DP:同时检查“少存了什么”和“多存了什么”
充分性判据:同一状态的任意两段历史,未来允许的决策和最优剩余代价是否相同?相同才能合并。
冗余性判据:某个维度能否由其他维度唯一算出?能就不必存。
| 本人近期场景 | 判断 | 立刻执行 |
|---|---|---|
状压分组 dp[mask][rem] |
rem=sum[mask]%T 可恢复 |
删余数维,单独检查 T>0、空集与答案换算 |
| Cryptarithm 当前块位置 | 对话里提出的是合理质疑 | 看状态定义是否含最后选到的位置 |
| 括号树 | 深度、已处理兄弟和祖先前缀是不同量 | 画含两棵子树的括号森林再标状态 |
| 树形 DP | 同一节点不同父边约束可能影响未来 | 明确树根、状态参数和转移依赖 |
可直接查看 本地 Cryptarithm 讲解。其中 已定义为“当前副本最后选在位置 ”,没有缺少这个位置。副本数已计入费用,不必再存。预收整份删除费 后,每保留一项退还 ,转移为
不要把你对状态的追问误写成“你提交了状态不足的错误解”。
3. 概率:先用一句中文说清事件
对话摘要明确记录过把 当成最大值恰为 的概率。
这其实固定了一个样本等于 ,其他样本不超过 。正确事件应为“所有样本不超过 ,但不全小于 ”:
固定反例 n=2,m=2:四种结果,最大值为 2 的有三种,概率 。若你的式子算不出它,先修事件再写代码。
连续顺序统计的分母为“参与排序样本数 + 1”。Slot Machine 最新样本被单独保留时,不参与旧历史最小值的排序;本地 nowcoder_2026_summer/10/e.cpp:17 分母为 ,要从 个旧样本解释,不能死背。
4. SOS:先画包含方向,费用另算
对话摘要中的 Retest Queue 涉及超集方向、拒绝费用;没有完整题面,不能补造它的费用公式。
通用检查用两位掩码:
01的子集是00,01。01的超集是01,11。- 所有“包含我要求的特征”的候选,应查询超集。
x & y == 0应查询固定位宽补集的子集,不是超集。
写注释 dp[S] = ... 后再写循环。费用必须按接受/拒绝事件分别列式,不能因为 SOS 统计了人数就默认这些人都支付同样费用。
5. 计数:先固定见证对象
对话摘要中 Matrix Game 的 漏了“相同取值属于同一组行”的要求。
以后每个乘法因子旁写含义:“先选哪组行”“再选颜色”“后选列”。如果两个因子都在重新挑行组,它们通常不能直接相乘。鸽巢前把鸽子和巢写成具体元组。
最小验证:取 2–3 行、2–3 列,枚举矩阵或选择对象,检查“同一行组”是不是被多个局部选择偷换。
6. 贪心 / 博弈:可行不等于最优
循环排列奇偶策略等问题在摘要中属于证明理解,不直接记为错误。
用两段式证明:
- 能保证:给出一个合法策略,说明不变量如何持续。
- 不能更好:给出对手反制、下界或交换论证,封住更优结果。
若证明“只考虑这几种情况”,必须说明任意其他方案如何归约到它们。小规模 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 起 | ()、()()、(()) |
| 反对角线 | 时 max(1,d-m)<=i<=min(n,d-1) | 1x1、1xm、nx1、2x3 |
如果同时处理相邻对角线的并集,范围可能要包含哨兵 0,必须注明;不能用一个看似宽松的区间默默访问真实数组以外的位置。
本地 nowcoder_2026_summer/3/j.cpp 对新节点设置 dist=1,空点默认 0;它体现了正确的一套约定。
11. 递归必须有严格下降的量
摘要记录最高位递归在 可能不缩小。本地 cf/cf1129/d1.cpp 目前只有小值分支和未完成的主体,不是可直接用的模板,也不能从它推断完整递推正确。
对每条递归边写出 ;可用 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,且各次独立,理论漏掉概率至多 。仍需证明行内压缩位数小,否则 无法承受。
- 个
int约 16 MiB,long long约 32 MiB;有多份数组时按峰值相加。时间按轮数乘 ,不能只看一次 SOS。 - 哈希/随机化要注明正确性概率;
TODO、空 solve、未完成函数不能仅凭能编译就收入可用模板。本地cf/453A.cpp是空壳,应使用已推导的公式而非复制这个文件。
13. 已核对的笔记错误
本次修正 DIRICHLET卷积以及莫比乌斯反演.md 的两处数学表达:
- 欧拉函数为 ,示性条件在方括号内。
- Dirichlet 卷积与莫比乌斯反演对任意算术函数成立,不要求积性。积性是在需要利用质因子独立计算时附加的性质。
这两处是笔记校订证据,不等于近期对话里反复出错。
三个月新增:相同模式在不同题型中的表现
重复键不是可以随意丢弃的历史
摘要中树上碰撞的 rev[x][dep[x]+s]=i 覆盖前一人。最小反例:一个节点、两个人同在时刻 0 出生,应该立即碰撞。
插入映射前先问:同 key 的两个对象是否等价,还是它们相遇就是事件? 对应处理可为计数、保存全部 ID、插入失败即触发;不是一律把 map 改 multimap。比如只维护最小费用时,同 key 取 min 就合理。
树上差分:先确定恢复的是边还是根路径
两端点 XOR 标记 d[u]^=1,d[v]^=1 后,恢复边覆盖奇偶要子传父。对子树边 ,删边形成的割中,每条路径跨割当且仅当一个端点在子树内,因此子树 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 再乘 ;不要把判定扫描误认为一次总共只扫一遍。
最短路边内部必须比较两个入口
CF144D 边 上、距 u 为 x 的点:
候选 必须满足 ,以及另一方向 。等号表示从两端得到同一个候选,要去重。最小反例:只有一条长度 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 删维、最高位递归收缩、同坐标事件。每题写五行状态 / 证明,比重复复制模板更有针对性。
分享文章
生成精美分享图或复制链接,与更多人分享本文。
继续阅读
换条路线
从其他文章中稳定抽取
最后更新于 ,距今已过 22 天
部分内容可能已过时