算法竞赛增补核对记录
本轮范围
本地代码根目录 /home/sanzenin/test/algo 共发现 2354 份 .cpp。按文件修改时间筛出 2026-09-25 至 10-25 的 126 份代码(排除 tempCodeRunnerFile.cpp);修改时间不是提交时间、AC时间或对话日期。本次读取了这些文件的目录与元信息,针对下表等候选阅读核心实现,不是逐题审查2354份代码。
读取vault算法目录及根目录CSES相关笔记的目录,重点核对《经典Trick》、FFT/NTT、Dirichlet卷积、概率期望、虚树与可并堆等现有内容。抽象代数课程笔记不作为本次全部重写的对象。
对话来源是用户本次提供的两份回顾,见 2026-07至10 算法三个月回顾(用户提供)、2026-10 算法对话回顾(用户提供)。Windows侧Kimi桥接可用,但ChatGPT显示登录页;用户已要求先整理本地、网页稍后补。没有独立抓取原始会话,不补造缺失时间段记录。
已有代码 → 原记录缺口 → 本次落点
“缺口”指9月手册/专题未完整覆盖或没有便于直接使用的接口,不代表这项知识完全不在你的其他笔记中。
| 本地来源(均相对代码根目录) | 可归纳内容 | 原记录状况 | 本轮落点 |
|---|---|---|---|
| cf/165E.cpp | 固定位宽补集查询子集见证 | 原手册没有SOS专题 | Trick O、subset_witness |
| cf/449D.cpp | 超集zeta + AND=0容斥 | 原手册未完整收录 | Trick O、count_and_zero,预处理2的幂 |
| cf/1523D.cpp | 随机抽样、压缩活跃位、超集统计 | 未说明误差与复杂度 | 个人易错点的概率与规模检查 |
| cf/cf1125/f.cpp | 指数奇偶向量、前缀对称差 | Trick只有基础位运算 | Trick P、数学套路3 |
| luogu/P5664.cpp | 严格多数坏事件互斥、差值DP | 原手册缺模型说明 | Trick Q、数学套路6 |
| atcoder/atcoder480/f.cpp | sum[mask]决定余数、删维 | 缺独立状态审查 | Trick R、数学套路7 |
| nowcoder_2026_summer/8/m.cpp | 下一次使用、缓存淘汰、Trie对象 | PBDS代码有,应用模型没提炼 | Trick S、单项缓存模板与批次限制 |
| reginonals/26xian/h.cpp | 截断函数断点、斜率扫描 | 原手册仅几何扫描线 | Trick T、clipped_cost_min |
| reginonals/21nanjing/j.cpp | 差值质因子、向上下倍数调整 | 数论代码未写触发器 | Trick U、数学套路1 |
| reginonals/23xian/f.cpp | 原根指数域、循环卷积、快速幂 | FFT/NTT专题已有,旧全集未收全 | Trick V、数学套路13 |
| luogu/P4245.cpp、atcoder/practice2/f.cpp | 多模/单模卷积、逆变换归一化 | 旧全集缺NTT直接用接口 | 固定模数convolution、约束说明 |
| cf/144D.cpp | 边内部距离取两端min,相等去重 | 旧全集只有Dijkstra基础 | 三个月易错点,当前代码已考虑两端 |
| cf/1418E.cpp | 强/弱两类不同贡献概率 | 旧概率笔记缺该边界反例 | 数学套路22;当前代码已含两类 |
| nowcoder_2026_summer/10/e.cpp | 历史最小值不变量、样本数 | 期望表有,但不变量需解释 | 数学套路16 |
| nowcoder_2026_summer/6/f.cpp | Z函数、前缀与后缀字典序、偏序 | 原手册字符串只有KMP/Trie等 | z_function;题面特定26位DP未直接模板化 |
| atcoder/atcoder477/f.cpp | 行范围前缀差 + 双BIT区间加和 | 原数据结构专题已有部分 | 阅读后保留原专题,未重复贴整题 |
| atcoder/atcoder479/e.cpp、f.cpp | 删边子树/补集贡献、排名与逆序对 | BIT/逆序对旧手册已有 | 贡献法触发器,未把题面特定式冒充通用公式 |
| cf/cf1128/e.cpp | 括号树祖先路径与已处理子树 | 原手册缺近期边界 | 结构不变量检查 |
| nowcoder_2026_summer/3/j.cpp | 左偏树合并与空点dist约定 | 旧手册已有左偏树 | 核对新点初始化,避免重复收录 |
| cf/cf1077/d.cpp | 数位关系与重建位宽 | 当前代码存在确定的32位移位UB | 最小输入UBSan复现,易错点7 |
| cf/cf1129/d1.cpp、cf/453A.cpp | 未完成递归、空solve | 不能视为可用模板 | 明确未收录为已验证实现 |
来自用户回顾、没有冒称独立读到原提交的增补:RGB前缀差转二维偏序、Canal Crossing边路径XOR差分、DSU on Tree回滚、碰撞重复键。其通用实现另外做了对拍。
旧笔记与生成器修复
- 《经典Trick》原A–N保留,新补O–Z共12条,增加完整整理入口。
- 欧拉函数示性条件写回方括号内;纠正Dirichlet卷积/莫比乌斯反演“不要求积性”。
- 旧生成器按已不存在的早期标题切片,可能空截取;改为完整导入当前Trick,不再依赖这些字符串。
- 贡献法全文保留为Markdown说明,避免把整篇公式说明塞进cpp块。
- 新目录使用显式稳定锚点;导入专题标题下移并跳过代码块,防止源代码中的
#include被改坏。 - 生成前检查每节非空,完成后原子替换输出;源文件缺失会停止,不覆盖现有手册。
- 后续按用户要求补齐Pandoc/XeLaTeX生成流程,PDF已更新为校订合订本;代码修订与检查见 算法竞赛板子检查报告。
验证记录
环境:本机g++,GNU C++17;-Wall -Wextra;ASan与UBSan。随机种子固定为20261025。
ready/verify.cpp:PASS 97881 independent checks。这是断言检查数,不是评测题数或AC数量。
- floor/ceil通过整数不等式检查,含
LLONG_MIN / -1;逆元与gcd互质性核对;组合数对照Pascal递推。 - floor_sum对照逐项整除;子集/超集zeta对照双重集合枚举并做逆变换。
- AND=0计数对照枚举所有非空下标子集;GCD对与区间计数对照直接枚举。
- Z对照逐后缀字符匹配;NTT对照二重循环卷积,覆盖空输入、负系数与跨多层变换。
- 离线缓存对照枚举所有缓存状态的最优DP:穷举三种对象、长度0至7、容量0至3的访问序列。
- 断点扫描对照小整数参数完全枚举;树差分对照逐条BFS恢复路径;二维最大值对照已插入点逐个扫描,含重复坐标、负数、空结构。
ready/example.cpp编译并核对预期输出;笔记中的头文件代码与真实头文件一致。
确定问题复现:只读编译 cf/cf1077/d.cpp,输入 1\n1 1\n,UBSan报告第71行 shift exponent 32 is too large for 32-bit type int。没有改原刷题代码。
验证范围补充:本页97881项是上轮通用增补的记录。后续已逐段检查第一至八章并修复明确问题,报告见 算法竞赛板子检查报告;仍未远程判题,也未通过Obsidian GUI逐页验收。PDF另外检查中文、公式、图片和代码排版。用户应按接口前提和原题模型选择模板。
文件与维护
主入口 算法竞赛整理索引;可复制接口 算法竞赛模板增补;证明与触发器 算法竞赛数学套路;个人复盘 算法竞赛个人易错点。
本地整理稿 /home/sanzenin/algo_templates/notes;refresh_notes.py 刷新与代码同源的模板笔记,build_book.py 生成全集,sync_vault.py 同步vault,verify_notes.py 检查链接、同步和实际复制代码。代码主仓库保持原样。
修改前原文备份位于 /home/sanzenin/algo_templates/.backups/20261025-205142,包含sha256清单。备份在WSL ext4中,不混入Obsidian检索。
分享文章
生成精美分享图或复制链接,与更多人分享本文。
继续阅读
换条路线
从其他文章中稳定抽取
最后更新于 ,距今已过 22 天
部分内容可能已过时