1844 字
9 分钟
算法竞赛增补核对记录

算法竞赛增补核对记录#

本轮范围#

本地代码根目录 /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检索。

算法竞赛增补核对记录
https://sanzenin.top/posts/obsidian/算法竞赛增补核对记录/
作者
Sanzenin 凪
发布于
2026-10-25
许可协议
CC BY-NC-SA 4.0

分享文章

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

继续阅读

沿着主题读

基于共同的标签与分类

换条路线

从其他文章中稳定抽取