C++ 竞赛编程:USACO 学习指南
🌐 English Version | 📖 当前:中文版
本书是专为参加 USACO(美国计算机奥林匹克竞赛) 的同学编写的 C++ 竞赛编程完整指南,覆盖从 Bronze 到 Platinum 级别所需的核心知识。也可用于 NOIP/CSP 等国内竞赛的算法学习。
📚 本书结构
| 部分 | 内容 | 目标等级 |
|---|---|---|
| C++ 基础 | 语法、控制流、函数、结构体 | 入门 |
| 核心数据结构 | 数组、排序、双指针、哈希 | Bronze/Silver |
| 贪心算法 | 贪心策略与经典应用 | Silver |
| 图论算法 | 图的遍历、最短路、MST、SCC、网络流、树上算法、搜索专题 | Silver/Gold |
| 动态规划 | DP 入门、经典模型、进阶模式、树形 DP | Silver/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(树上路径计数/换根)
🚀 如何使用本书
💡 学习建议
- 每章都有配套练习题(🟢 简单 / 🟡 中等 / 🔴 困难 / 🏆 挑战),先尝试自己解答再参考题解
- 代码示例均为 C++17,注意竞赛中常见的 I/O 优化写法
- 卡住时用调试指南的对拍流程验证思路
📝 翻译说明:本书中文版正在持续完善中。如遇内容缺失,可参考 英文原版。