USACO 教程.pdfVIP

USACO 教程 USACO 教程 目录 Section 1.2 Complete Search 枚举搜索2 Section 1.3 Greedy Algorithm 贪心算法4 Section 1.3 Winning Solutions 竞赛中的策略6 Section 1.4 More Search Techniques 更多的搜索方式9 Section 1.5 Binary Numbers 二进制算法 13 Section 2.1 Graph Theory 图论知识 15 Section 2.1 Flood Fill 种子染色法22 Section 2.2 Data Structures 数据结构26 Section 2.2 Dynamic Programming 动态规划33 Section 2.4 Shortest Paths 最短路径40 Section 3.1 Minimal Spanning Trees 最小生成树(MST) 45 Section 3.2 Knapsack Problems 背包问题47 Section 3.3 Eulerian Tour 欧拉通路50 Section 3.4 Computational Geometry 计算几何59 Section 4.1 Optimization 最优化64 Section 4.2 Network Flow 网络流67 Section 4.3 Big Number 高精度72 Section 5.1 Two Dimensional Convex Hull 二维凸包77 Section 5.3 Heuristic Search 启发式搜索84 ·1 · USACO 教程 Section 1.2 Complete Search 枚举搜索 思想： 写枚举搜索时应遵循KISS 原则（Keep it simple stupid ，译为“写最单纯愚蠢的程序”，意思是应把程序写得尽 量简洁），竞赛时写程序的最终目标就是在限制时间内求出解，而不需太在意否还有更快的算法。 枚举搜索具有强大的力量，他用直接面向答案并尝试所有方案的方法发现答案。这种算法几乎总是解题时你 第一个想到的方法。如果它能在规定的时间与空间限制内找出解，那么它常常很容易编写与调试。这就意味着你 可以有时间去解答其他难题，即那些不能显示枚举算法强大的题目。 如果你面对一道可能状态小于两百万的题目，那么你可以考虑使用枚举搜索。尝试所有的状态，看看它们是 否可行。 小心！小心！ 有时，题目不会直接要求你使用枚举算法。 例题1：派对灯 [IOI 98] 在一次IOI 派对上有N 个灯和4 个灯开光，第一个开关可以使所有灯改变状态（关上开着的灯，开启关着 的灯），第二个开关可以改变所有偶数位上灯的状态，第三个开关可以改变所有奇数位上灯的状态，第四个开关 控制着灯 1、4、7、10…… （3n+1 ）。 告诉你N 的值和所有按开关的次数（小于10,000 次）。并告诉你某些灯的状态（例如：7 号灯是关着的，10 号 灯是开着的）请编程输出所有灯可能的最后状态。 很明显，每次按开关你都要偿试4 种可能。那么总共要试 4 10000 次（大约 106020），那意味着你没有足 够的时间去使用枚举搜索，但是我们将枚举方法改进一下，那就可以使用枚举了。因为无论有多少个灯，由于开 关控制的特殊性，都会出现6 个灯一次循环的情况，即1 号灯的状态永远与7 号灯，