赛用模板打印稿 V1.8.8, 2024.11.19

概述

一次代码现代化更新。

更新日志

按时间的说明见此。以下是按章节的说明：

重要问题修复

• 《几何→求解点到圆的切线数量与切点》调用公式错误，已修复，感谢 BingBong. 在QQ的沟通。
• 【1.8.7 Patch】《图论→缩点（Tarjan 算法）→（无向图）割边缩点》代码有误，重构。

修复

• 《几何→两点式转一般式》返回值由 int 修改为 T 。
• 《基础算法→常用函数》mypow 修改为 i64 。
• 《数据结构→小波矩阵树：高效静态区间第 K 大查询》修改偏移，使得能够以 $\texttt{1-idx}$ 运行。

新增内容

• 《卡常》大章节新增，将一些相关内容移入这个章节归档，并且在原文中使用荧光高亮标注链接。
• 《卡常→数论 | 取模运算类 | 蒙哥马利模乘》新增；
• 《卡常→数论 | 质数判定 | Miller-Rabin》新增；
• 《卡常→数论 | 质因数分解 | Pollard-Rho》新增；
• 《数论→球盒模型》代码整理重构，并扩充到全部十二种模型；
• 《基础算法→最大公约数 gcd→位运算加速》移动至《卡常》章节；
• 《网络流→最大流→HLPP》移动至《卡常》章节；
• 《数论→质数判定→预分类讨论加速》移动至《卡常》章节；
• 《图论→无向图简单环检查、输出》新增；

优化

• 《常用例题→高精度进制转换》重构，封装。
• 《数据结构→线段树→快速线段树》合并入树状数组，作为最值查询扩展的第二种实现形式
• 《常用例题→逆序对（归并排序解）》由于已经有树状数组解了，所以直接删除；
• 《杂类→快读》移动至《卡常》章节；
• 《常用例题》整个章节与《杂类》合并；
• 《动态规划→背包问题求具体方案》重构；
• 《数论→质数判定》章节重构，合并原《数论→Miller-Rabin》；
• 《常用函数→快速幂》章节重构，并移动至《数论》；
• 《数论→质因子分解》章节重构，合并原《数论→Pollard-Rho》；
• 《图论→有向图简单环检查、输出》代码重构；
• 《图论→（负权图、判负环）Bellman-ford 算法》代码重构，合并原《数论→判负环》；
• 《数据结构→二维树状数组》章节重构；
• 《数据结构→树状数组》章节重构，大改；

赛用模板打印稿 V1.8.7, 2024.10.07

概述

时间飞逝，一眨眼就退役大半年了，值此国庆假期空闲之际重新整理了一下内容。成稿于2024第一场区域赛前夕，祝大家新赛季取得好成绩。

额外内容

Important

2024.10.21更新：

这里有一个重要的更新，由 @doyowhat 提出的 #5 ，由于代码错误较大，即便已经封装我依旧将其列入这一版本的更新。以附件的形式给出。

• 《图论→缩点（Tarjan 算法）→（无向图）割边缩点》代码有误，重构。

2024.10.22更新：

收集的 jiangly 的模板也更新了一波。为了节约空间，删去了部分旧版本的内容、以及去除了代码中的 ::std 。

2024.10.29更新：

收集的 jiangly 模板封面更新。

更新日志

按时间的说明见此。以下是按章节的说明：

重要问题修复

• 《图论→缩点（Tarjan 算法）→（无向图）割点缩点》修改，计数器修改为先加后使用 ++now 。感谢 @doyowhat 提出的 #4 、@coolarec 在QQ的沟通。
• 《获取二维静态凸包（Andrew算法）》小于号写错，修正，感谢 @xxxxbc 在微信的沟通。
• 《图论→二分图最大匹配→HopcroftKarp算法（基于最大流）解》重构，此前的版本可能被卡（时间与正确性均）。
• 【1.8.6增量更新】《线段树 区间加法修改、区间最小值查询》rmq 函数初始值赋值错误，min 应该对应 ::max()
• 【1.8.6增量更新】《线段树 区间最值》初始赋值错误。懒标记应该赋值为 $-1$ ，而不是 $0$ 。

新增内容

• 《基础算法→常用函数》新增两个 log2 函数。
• 《串→子序列自动机》新增。
• 《数据结构→小波矩阵树：高效静态区间第 K 大查询》新增。
• 《杂类》新增一段测速代码。
• 《exgcd》新增对 $0$ 的特判（还不完美，在改）。
• 【1.8.6增量更新】《OJ测试》新增 numbers 库测试。
• 【1.8.6增量更新】图论新增结论——竞赛图三元环计数。
• 【1.8.6增量更新】《bitset》新增 _Find_next 和 _Find_fisrt 两个函数

优化

• 《图论→常见概念》强对应代码的概念分散到代码附近。
• 《常用例题→选数（DFS 解）》重构。
• 《数据结构→树状数组→最值查询扩展（常规+区间最值查询+单点赋值）》优化了单点赋值部分的代码，例题。
• 《串→KMP→统计原串中某个子串重复出现的次数（例题）》删除，通过全串匹配可以以相同复杂度实现（仅常数区别），无需这个额外的版本。
• 《串→KMP→全串匹配》重构。
• 《差分约束》代码重构。

赛用模板打印稿 V1.8.5, 2024.06.01

1.8.5 整合

概述

这是第一次系统性的发布打印件整合包，由于整理时间仓促，此次版本仅包含两个文件：

• XCPC Algorithm Template(I) WIDA's Onfine version
• XCPC Algorithm Template(II) Jianly's Online version
  成稿于参加江西省赛前夕。

版本更新小计

2024.04.12

《最长路（topsort+DP算法）》重构

2024.02.06

《快读》代码微调
《扩展欧几里得 exgcd》重构

2023.12.20

《网络流》新增”最小割树 Gomory-Hu Tree“

2023.12.19

《STL》新增“其他函数一章，重构《bit 库与位运算函数 _builtin》

2023.11.20

《Python》在增加输出流长度一小节中新增“递归深度”