第七部分：USACO 竞赛指南

随时可读——无前置条件

第七部分与本书其他部分不同，不是教算法，而是教你如何参赛——如何读题、管理时间、在压力下调试，以及策略性地思考如何得分。

涵盖的主题

什么时候读这部分

• 第一次参加 USACO 之前： 读第 7.1 章了解形式
• 练习题做不动时： 第 7.2 章的算法决策树有帮助
• 完成第 2-6 部分后： 第 7.2 章的清单告诉你是否准备好了 Silver

本部分关键内容

第 7.1 章：了解 USACO

• 竞赛日程（每年 4 场：12 月、1 月、2 月、US Open）
• 级别结构：Bronze → Silver → Gold → Platinum
• 评分：约 1000 分，750+ 晋级
• 部分分策略： 如何在没有完美解法时也得分
• 常见错误及如何避免

第 7.2 章：解题策略

• 算法决策树： 根据约束选择合适的算法
  • N ≤ 20 → 暴力/状压
  • N ≤ 1000 → O(N²)
  • N ≤ 10^5 → O(N log N)
  • 网格 + 最短路 → BFS
  • 最优决策 → DP 或贪心
• 测试方法： 样例、边界情况、对拍
• 调试技巧： cerr、assert、AddressSanitizer
• Bronze → Silver 检查清单

第 7.3 章：Ad Hoc 题型

• 什么是 ad hoc： 无标准算法；需要特定于题目的洞察
• ad hoc 思维方式： 小例子 → 找规律 → 证明不变量 → 实现
• 6 个类别： 观察/规律、模拟捷径、构造、不变量/不可能性、贪心观察、几何/网格
• 核心技术： 奇偶论证、鸽巢原理、坐标压缩、对称化简、逆向思考
• 9 道练习题（简单 → 困难 → 挑战）含提示

竞赛日检查清单

竞赛当天参考：

• 模板已编译并测试通过
• 在编写任何代码之前先读完全部三道题
• 手动推演样例
• 确认约束条件和相应的算法层级
• 先解最简单的题
• 提交前用样例测试
• 若卡住：为小数据范围编写暴力以获取部分分
• 剩 30 分钟时：停止添加代码，专注于测试
• 再检查一遍：需要 long long 的地方用了吗？数组边界正确吗？

🏆 USACO 技巧： 竞赛前一周最值得做的事是从记忆中重新解 5-10 道你以前做过的题。速度和准确性与知识积累同样重要。