竞赛算法与算法训练总笔记

• 第1章 竞赛解题闭环与复杂度预算：从题意、数据范围和暴力基线建立可验证解题流程。
• 第2章 排序、二分与分治：把有序性变成边界单调性，并用分治控制子问题。
• 第3章 前缀结构、双指针与滑动窗口：把重复区间计算压成可增量维护的状态。
• 第4章 基础数据结构的算法化使用：按操作契约选择栈、队列、堆、并查集和树状数组。
• 第5章 图的表示、遍历与有向无环结构：把状态空间变成顶点和边，用遍历不变量覆盖且不重复。
• 第6章 最短路与最小生成树：区分路径最优和连通成本最优，掌握松弛与安全边证明。
• 第7章 树上算法：利用树的唯一路径和层级结构，把全局询问压成局部合并。
• 第8章 贪心算法与交换证明：每次选择都要证明可扩展为全局最优，而不是凭局部直觉。
• 第9章 动态规划基础模型：把问题压成最小充分状态，写清转移来源、顺序与初始化。
• 第10章 区间、树形与状态压缩DP：在更复杂依赖图上组织区间长度、子树后序和子集枚举。
• 第11章 字符串与竞赛数论：用前缀匹配结构和模运算消除重复比较。
• 第12章 网络流、匹配与赛场综合：把增广、不变量、压力测试和时间分配整合成比赛能力。

固定解题流程

契约→数据范围→暴力→重复工作→状态/不变量→正确性→复杂度→实现→反例→对拍→复盘。竞赛训练不是题型背诵；每次优化都要说清减少了哪类重复操作，并由不变量保证答案没有改变。