/algorithm

算法竞赛笔记：数据结构、动态规划、数论与字符串模板，按知识体系分组整理。

10 篇文章 19 分钟

这里是从日常竞赛笔记里挑出的十篇，覆盖并查集、树状数组、拓扑排序、背包与序列 DP、二维前缀和、逆元与高精度、KMP 以及位运算。

每篇都保留了可直接复制的 C++ 模板，配合「思路 → 模板 → 易错点」的顺序阅读效果更好。

数据结构 4

并查集入门用森林维护等价关系：路径压缩加按秩合并，把查询与合并都压到近似常数。并查集 C++ 图论 2 分钟

树状数组：统计左侧大于当前值的元素个数离散化加树状数组，把「左侧有多少个比当前数大」从 O(n²) 降到 O(n log n)。树状数组离散化 C++ 2 分钟

拓扑排序：Kahn 算法与 AOV/AOE 网不断取出入度为零的点，顺便判断有向图是否存在环，并顺带理解 AOV 与 AOE 的区别。拓扑排序图论 C++ 2 分钟

单调队列：滑动窗口的最值队列里存下标而不是值，靠单调性把区间最值的复杂度压到 O(n)。单调队列滑动窗口 C++ 1 分钟

动态规划 2

01 背包详解：从二维方程到滚动数组把二维状态压成一维、为什么容量要倒序枚举，以及恰好装满时的初始化技巧。动态规划背包 C++ 2 分钟

子序列 DP：五个常用模板 LIS、LCS、最大子段和、子序列计数、不相邻取数，五个模板覆盖绝大多数子序列题。动态规划 LIS LCS C++ 2 分钟

前缀和与差分 1

二维前缀和与二维差分容斥原理写对四个角标，子矩阵查询与区间修改都能做到 O(1)。前缀和差分 C++ 2 分钟

数学与数论 2

乘法逆元：模意义下的除法模运算里没有分数，除以 a 要改成乘 a 的逆元；模数为质数时用费马小定理配快速幂。数论逆元快速幂 2 分钟

高精度四则运算模板用字符串模拟加减乘除与取模，覆盖超出 long long 范围的整数运算。高精度 C++ 模板 2 分钟

字符串 1

KMP 算法：next 数组与线性匹配匹配失败时只回退模式串指针，文本串指针永不回退，这是 KMP 能做到 O(n+m) 的原因。字符串 KMP C++ 2 分钟