C++ 竞赛编程:USACO 学习指南

🌐 English Version | 📖 当前:中文版

章节数 难度 语言

本书是专为参加 USACO(美国计算机奥林匹克竞赛) 的同学编写的 C++ 竞赛编程完整指南,覆盖从 Bronze 到 Platinum 级别所需的核心知识。也可用于 NOIP/CSP 等国内竞赛的算法学习。

📚 本书结构

部分内容目标等级
C++ 基础语法、控制流、函数、结构体入门
核心数据结构数组、排序、双指针、哈希Bronze/Silver
贪心算法贪心策略与经典应用Silver
图论算法图的遍历、最短路、MST、SCC、网络流、树上算法、搜索专题Silver/Gold
动态规划DP 入门、经典模型、进阶模式、树形 DPSilver/Gold
USACO 竞赛指南竞赛流程、解题策略、Ad Hoc全级别
数学数论、筛法、组合、矩阵快速幂、博弈论Silver/Platinum
字符串算法基础操作、KMP、Trie、Manacher、AC 自动机Bronze/Platinum
计算几何叉积、凸包、多边形面积Gold/Platinum
附录速查手册、题集、技巧、模板、调试指南全级别

每章页首徽章标注对应级别:🥉 Bronze / 🥈 Silver / 🥇 Gold / 💎 Platinum,可据此按需选读。

🗺️ USACO 分级学习路线

USACO 分为 Bronze → Silver → Gold → Platinum 四级逐级晋升,赛制详见理解 USACO。各级别对号入座:

🥉 Bronze — 语言基础与暴力思维

模块章节
C++ 基础第 2 部分:C++ 基础(2.x 各章)
数据结构入门数组与前缀和 等 3.1–3.4
贪心第 4 部分:贪心算法(4.x 各章)
模拟与枚举枚举与模拟(2.8)、各章中的暴力/枚举题型
倍增与构造倍增与构造(2.9,倍增起步 Bronze、构造题 Silver 常见)

🥈 Silver — 图论与 DP 入门

模块章节
图论基础图的基础(5.1)、BFS 与 DFS(5.2)、并查集(5.6)
DP 入门DP 入门(6.1)至 进阶 DP 模式(6.3)
数据结构排序与搜索、二分答案 等(3.5–3.9)
字符串入门字符串基础(9.1)、字符串匹配:前缀函数与 KMP(9.2)、Trie 树(9.3)
数学基础数论基础(8.1)

🥇 Gold — 本书核心进阶内容

模块章节
最短路最短路径(5.4,含负环与差分约束)
数据结构线段树(5.7)、树状数组(5.8)
图论进阶MST(5.9)、拓扑排序(5.10)、SCC(5.11)、树链剖分(5.12)、欧拉序(5.13)、网络流(5.14)、树上差分与点分治(5.15)、搜索专题(5.16:剪枝/IDDFS/A*)
DP 进阶6.4 折半搜索 至 树形 DP(6.8)
数学素数筛法与积性函数(8.2)、组合数学(8.3)

💎 Platinum — 高阶专题

模块章节
DP 优化DP 优化(6.6:单调队列/斜率/决策单调)
矩阵加速矩阵快速幂(8.4)
字符串进阶Manacher 与 Z 函数(9.4)、AC 自动机(9.5,Gold/Platinum 常客)
博弈论博弈论入门(8.5)
计算几何计算几何基础(10.1)

🔗 Gold 依赖链

Gold 各章环环相扣,按依赖关系学习事半功倍:

5.6 并查集 ──→ 5.9 MST ──→ 5.14 网络流(割与连通性思想)
                  │
5.1 树的表示 ──→ 5.13 欧拉序/LCA ──→ 5.12 树链剖分
                  │                    │
                  └──→ 5.15 树上差分与点分治
5.2 BFS/DFS ──→ 5.10 拓扑排序 ──→ 5.11 SCC(缩点后回到 DAG)
5.4 最短路(Dijkstra)──→ 6.8 树形 DP(树上路径计数/换根)

🚀 如何使用本书

  1. 入门学习者 — 从 C++ 基础 开始,按目录顺序学习
  2. 有一定基础 — 直接进入核心数据结构或按上方路线表对号入座
  3. 赛前冲刺 — 用附录速查手册和算法模板库快速复习

💡 学习建议

  • 每章都有配套练习题(🟢 简单 / 🟡 中等 / 🔴 困难 / 🏆 挑战),先尝试自己解答再参考题解
  • 代码示例均为 C++17,注意竞赛中常见的 I/O 优化写法
  • 卡住时用调试指南的对拍流程验证思路

📝 翻译说明:本书中文版正在持续完善中。如遇内容缺失,可参考 英文原版。