4038 字
20 分钟
算法竞赛板子检查报告

算法竞赛板子检查报告#

本轮检查的是《算法竞赛模板大全》的全部第一至八章主代码与其中的专题代码,外加上轮新增的自包含模板。结论:旧板子存在可复现的逻辑错误、编译损坏、越界以及标题与代码不符;已在手册生成层修订,原刷题文件和Neovim全局配置没有批量改写。

先记住这些明确错误#

章节 原问题 修订与验证
2.7 动态线段树 vector扩容后使用父节点子字段引用;已有节点整段查询漏祖先tag 返回节点编号;查询补carry;随机区间加和对照数组
2.11 扫描线 y编号从0开始却维护从1开始的树,依赖-999哨兵,x用int 去哨兵、统一0-based、128位面积,单位格覆盖对照
2.18/2.19 左偏树 DSU初始化写到fa[N];持久化版本宏被换行破坏 边界修复;独立持久化堆接口,多版本不可变性检查
2.22/2.23 Splay 插入0误认空哨兵;根上重复插入size不更新;kth使用cnt代替size 与multiset对照5000轮插删和kth
4.5 Trie 插入减’a’,查询减’0’ 统一字符映射,按需分配节点
5.7 严格次小MST 等权环把不存在的次大边当成可替换边 初始化缺失值;用所有小图生成树权值集合对照
5.18 割点 混入城市删除整题,未真正删除城市且状态残留 换成真正的割点/桥接口,逐点/逐边删除检查连通分量
5.21 Hall 一般区间邻域不能只检查连续左部编号片段;最大子段和无建模 给出反例;改为右部区间条件与有证明的区间匹配贪心
5.27 0-1 BFS 三桶实现未及时处理当前桶新进入的0权边 改deque,边权严格0/1;对照Floyd
6.11 高斯 跳过零主元后仍回代除0 显式返回无解/唯一/无穷多解
6.14 BSGS baby/giant方向与答案指数不一致,逆元默认费马 规范baby表、巨步与一般逆元;小模数完全穷举
6.16 EXCRT 缺差值能否被gcd整除的判定 无解nullopt、负余数归一化、lcm越界抛异常
6.25 康托 upper_bound后删了下一元素 lower_bound与0-based序位;穷举n<=7全部排列正逆
7.9/7.16 点在多边形 用有限远端点射线且不处理顶点重数 半开纵向交叉、128位叉积,边界单独判断
7.13 直线圆交 沿垂直向量找交点,结果不在原直线上 改原直线方向,补相切和退化点检查
8.5 哈密顿路径 换行字符被写成两行,无法编译 修复字面量,和小图排列枚举核对
8.6 斜率DP 整数除法截断斜率、dp用int、重复横坐标epsilon代替证明 128位离散Li Chao;正负/重复前缀对照二重循环
8.7 树背包 默认两个儿子,son[1]可越界 一般树逐子树合并,负边和恰选数量对照子集枚举

几个最小复现:动态线段树先整段+5,再对子段更新/查询;等权三角形不存在严格次小树;插入字符串az后查询az;直线y=0与单位圆的交点必须是(-1,0)、(1,0);同余x=0 mod2和x=1 mod2无解;排列(2,1)的1-based排名应为2。

两类误收不再混用#

原“最小圆覆盖”文件是角度扫描整题,现换成经过小规模最优支持圆枚举对照的二维最小圆覆盖。原“三维最小球”文件没有z坐标,亦为二维圆扫描,已隔离并移出可复制代码;本书不宣称已经提供可用的三维最小球实现。

可持久化数组与区间第k小、单模与双模哈希、隐式Treap与Splay、所有递增子序列与最长递增子序列计数,也已纠正名称和适用范围。

半平面交改为与给定边界方框求交的裁剪版,最坏O(k²),不是原先声称的O(k log k)通用半平面交;不能用它推断原问题无界性。

验证证据与范围#

  • 第一至八章的129段代码均按GNU C++17语法检查:125个主代码块及专题中的4段。片段补足原有骨架中的n、m、Point等依赖,不代表每段都可脱离依赖直接运行。
  • checked/verify_checked.cpp:707000项检查,开启ASan/UBSan;用独立暴力、数学不等式、最优DP或另一套算法比较结果。
  • ready/verify.cpp:97881项检查,开启ASan/UBSan,覆盖上轮新增模板。
  • audit/verify_programs.py:16039项程序输入输出检查,包括康托全部排列、Hall枚举匹配、课程DP、权值线段树、左偏堆、哈密顿路径。
  • 合计820920项检查,不是820920道题或远程AC数;没有进行远程判题。
  • PDF由Pandoc与XeLaTeX在WSL ext4生成,检查中文、公式、图片、页码、目录/书签、内部链接与代码自动折行;源文件支持重建。

编译通过不等于所有算法在任意题意下都正确。保留整题的输入限制、静态数组上界、非负权、递归栈、哈希碰撞和几何精度仍需按题目审查。浮点几何不是任意尺度的精确计算;所有“128位安全”均以中间值未超出128位范围为前提。

复现命令#

在 /home/sanzenin/algo_templates 运行:

Terminal window
python3 audit/compile_handbook.py
g++ -std=c++17 -O1 -g -fsanitize=address,undefined -fno-omit-frame-pointer \
-Wno-return-type -Wno-unused-result checked/verify_checked.cpp -o /tmp/checked-verify
/tmp/checked-verify
python3 audit/verify_programs.py
bash compile_pdf.sh

全部校订清单#

以下包含算法修复、边界/前提补充和名称校订,不能把条目数理解为相同数量的独立算法错误。修订代码位于本项目checked目录,清单来自checked/corrections.json,生成器按章节号替换,可追溯原来源。

章节 名称 校订原因
1.6 双向分层搜索(梦魇专用实例) 先检查坐标再访问地图,并注明这是3:1速度和扩散危险区的专用实例。
1.7 八数码 A*(曼哈顿启发式) 原双向搜索未按层扩展,遇不可达状态可能对空队列front且无返回;替换带奇偶判无解的A*。
2.6 线段树上二分 (Segment Tree Walk) 修正递归lambda调用示例中漏传自身参数;计数须非负且1<=k<=总数。
2.7 动态开点线段树 (Dynamic Segment Tree) 修复vector扩容导致子节点引用悬空;完整覆盖查询补上祖先懒标记。
2.9 权值线段树 (Weight Segment Tree) 空前缀区间[1,0]会无限递归,补上区间无交检查。
2.10 李超线段树(项目收益实例) 明确原代码默认0收益,不是支持任意负直线的通用最大值初始化。
2.11 矩形面积并(0-based离散化,128位面积) 修复y离散化哨兵依赖、0-based区间遗漏、x坐标int截断;同x事件合并,零面积忽略。
2.12 可持久化数组(历史版本单点修改/查询) 修正标题/说明与实际代码用途不一致。
2.16 单调栈 (Monotone Stack) 注释中>=弹栈得到的是右侧首个不大于元素,不能称严格更小。
2.17 二叉堆(C++动态数组) 原演示固定pop十次,小输入会空堆下溢;改完整动态二叉堆接口。
2.18 可并堆:左偏树 (Leftist Tree / Mergable Heap) 修复初始化写越界fa[N],设置新叶子dist=1。
2.19 可持久化左偏树 (Persistent Leftist Tree) 原代码宏被换行破坏且误混入整题;改为可独立使用的持久化左偏堆。
2.20 笛卡尔树构造与特定 XOR 子树检查实例 修正标题/说明与实际代码用途不一致。
2.21 Treap 平衡树(FHQ 分裂合并版本) 修正标题/说明与实际代码用途不一致。
2.22 Splay 伸展树 (Standard Splay) 修复插入0命中空哨兵、根上重复计数后size未更新;第二版kth比较cnt改size。
2.23 Splay 伸展树 (第二实现版本) 修复插入0命中空哨兵、根上重复计数后size未更新;第二版kth比较cnt改size。
2.24 隐式 FHQ Treap(区间翻转) 修正标题/说明与实际代码用途不一致。
3.4 PBDS 哈希表 (gp_hash_table) gp_hash_table的Hash_Fn是第三模板参数,原注释写第四。
4.3 单模哈希应用:对称分块 修正标题/说明与实际代码用途不一致。
4.4 Manacher 最长回文子串算法 原哨兵扩展无显式边界,改为奇/偶半径数组,支持任意普通字符及空串函数调用。
4.5 字典树 Trie(小写字母,动态节点) 修复插入减’a’而查询减’0’的不一致;改按实际节点分配。
4.6 01-Trie 最大异或对(uint32_t) 完整uint32位宽,移位使用无符号值,节点数按实际分配。
5.1 单源最短路 Dijkstra 竞赛骨架同时using std和PBDS时priority_queue歧义;明确std命名空间。
5.4 带权并查集 (完整题解版) 同堆合并会自连成环;自身查询距离不应为-1。
5.7 严格次小生成树 (Strict Second Minimum Spanning Tree) 原严格次小MST把缺失次大值当真实边,等权环可输出不存在的答案;修复不同最大/次大值与不连通处理。
5.11 树的直径完整实现 (带权与距离维护) 修复pair<ll,int>与pair<ll,ll>比较不能编译,删除重复输出0。
5.18 无向图割点与桥(重边/非连通) 原整题没有真正删除城市且cut残留,不能当通用割点板;换成按边id的割点与桥函数。
5.21 Hall 婚姻定理 (Hall’s Marriage Theorem) 旧稿将一般区间邻域错误归结为连续左部片段,且最大子段和代码缺少建模;给出反例与正确区间贪心。
5.23 网络流:Dinic 独立实现版 add参数使用int会截断64位容量;点数数组按n分配。
5.24 网络流:Edmonds-Karp (EK 增广路算法) add参数使用int会截断容量;边数组静态上界保留,须满足2m<N。
5.25 第 K 短路 A*(允许重复点边的 walk) 把起点与时间上限比较误写为st;改se,并限制每点弹出次数与不可达扩展。
5.27 0-1 BFS(边权仅0或1) 原三桶队列没有在当前距离处理完新加入的0权边,访问顺序可能错误;换成严格0/1 deque。
6.4 扩展欧几里得算法 (EXGCD) 修正递归lambda调用示例;该有符号版本按a,b非负使用。
6.8 扩展欧拉降幂(十进制大指数) 模数1与0次幂返回错误,phi和大指数缩减存在窄类型溢出;用128位中间值。
6.11 高斯普通消元法 (Gauss-Jordan Elimination) 原稿遇零主元仍回代除零;现在区分无解、唯一解与无穷多解。
6.13 Miller-Rabin 素性测试 (大素数判定) 实现参数是signed long long,原注释误声称覆盖完整unsigned范围。
6.14 BSGS 离散对数算法 (Baby-step Giant-step) 修复baby/giant步方向、指数符号和复合模数逆元;最小解用穷举验证。
6.15 中国剩余定理 CRT (Chinese Remainder Theorem) 统一为可检查无解的CRT接口,避免大乘积公式中间溢出;lcm限制64位。
6.16 扩展中国剩余定理 EXCRT (Extended CRT) 补上(r2-r1)%g可解性检查,规范化负余数,检查lcm溢出。
6.17 莫比乌斯反演与数论分块 (P3455 ZAP-Queries) 线性筛循环访问下标N,原bitset越界。
6.20 K 个数的异或最大/特定统计 rank=63时1ll<<63会产生错误的有符号比较;改无符号位宽。
6.22 高精度乘法(幂的数位统计实例) 注明这是乘法类的题目应用,主程序输出a^n各数位的奇偶数量差,不能当乘积输出。
6.23 有界生成函数计数(滑动窗口DP) 原d[j+k]没有限制总次数,固定数组可越界;改滑动窗口DP和大整数精确计数。
6.24 卡特兰与括号前缀补全 修复损坏头文件,并以组合数反射原理代替每项两次快速幂的低效递推。
6.25 康托展开与逆康托展开 (Cantor Expansion / Obsidian / 知乎) 康托排名应删除当前值而非其upper_bound位置;改lower_bound与0-based序位。
6.27 错排问题 (Derangement) 原截取缺少f、mod定义且n=0无限递归;改完整迭代错排函数。
7.2 整数点极角排序(128位叉积) 浮点版本误称无浮点误差,原点等价关系破坏严格弱序;改整数128位比较并处理零向量。
7.5 二维凸包 (CSES g_andrew.cpp 实战版) 去重,补空集/单点/全共线退化;避免共线点往返重复输出。
7.6 半平面交(有界多边形裁剪) 原半平面交未处理平行/重合线,可能除零;提供明确有界的多边形裁剪版。
7.7 线段相交判定 (CSES Line Segment Intersection) 改用128位几何谓词;点在多边形用半开纵向交叉,避免有限射线端点与顶点重数。
7.8 多边形面积计算 (CSES Polygon Area) 改用128位几何谓词;点在多边形用半开纵向交叉,避免有限射线端点与顶点重数。
7.9 点在多边形内部判定 (CSES Point in Polygon) 改用128位几何谓词;点在多边形用半开纵向交叉,避免有限射线端点与顶点重数。
7.10 二维最小圆覆盖(随机增量) 原文件是二维角度扫描整题,与最小圆覆盖不符;换成随机增量最小圆。
7.11 三维最小球覆盖(误收代码已隔离) 原文件是二维圆交角度扫描,误标三维最小球,已从可用代码中移除。
7.12 两直线交点计算 (Line Intersection) 平行/退化直线显式返回nullopt。
7.13 直线与圆的交点计算 (Line-Circle Intersection) 原交点沿法向偏移,改沿直线方向;补退化点与相切处理。
7.14 平面最近点对 (Closest Pair of Points / 分治法) 128位距离平方转回long long再开方会截断;扩大无穷大并直接转long double。
7.15 Pick 定理与多边形格点 (Pick’s Theorem & Polygon Area) 改用128位几何谓词;点在多边形用半开纵向交叉,避免有限射线端点与顶点重数。
7.16 光线投射算法 (Point in Polygon / 射线法判定点在多边形内部) 改用128位几何谓词;点在多边形用半开纵向交叉,避免有限射线端点与顶点重数。
8.4 树状数组统计所有严格递增子序列 修正标题/说明与实际代码用途不一致。
8.5 状压 DP 求解哈密顿路径 (CSES Hamiltonian Flights) 修复生成器把换行字符字面量写成两行,导致无法编译。
8.6 二次代价 DP(离散李超树优化) 原斜率先整数除法再转double,DP用int会溢出;改用128位整数离散Li Chao,支持重复/非单调前缀。
8.7 树形背包(恰选q条与根连通的边) 原稿默认恰有两个孩子并直接访问son[1],一条边的树即失效;改一般树子树背包。
8.8 树形背包 DP (DFS 序展开优化版) 恰选m课程时不可达状态不能初始化0,否则负学分会少选冒充可行。
8.10 集合 Nim 博弈与 SG 函数 (Sprague-Grundy) 补cstring头文件、SG枚举上界和EOF退出条件。
8.12 剪纸博弈 (Cutting Game) 固定bitset无法容纳两子游戏SG异或结果,改set收集可达SG。
9.2 贡献法应用 组合数补非法参数返回0,避免k<2的负下标;模答案规范化。

相关:算法竞赛整理索引、算法竞赛模板大全、算法竞赛增补核对记录。

算法竞赛板子检查报告
https://sanzenin.top/posts/obsidian/算法竞赛板子检查报告/
作者
Sanzenin 凪
发布于
2026-10-25
许可协议
CC BY-NC-SA 4.0

分享文章

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

继续阅读

沿着主题读

基于共同的标签与分类

换条路线

从其他文章中稳定抽取