# USACO教程

USACO 教程

USACO 教程

Section 1.2 Section 1.3 Section 1.3 Section 1.4 Section 1.5 Section 2.1 Section 2.1 Section 2.2 Section 2.2 Section 2.4 Section 3.1 Section 3.2 Section 3.3 Section 3.4 Section 4.1 Section 4.2 Section 4.3 Section 5.1 Section 5.3 Complete Search 枚举搜索 ............................................................................................................................ 1 Greedy Algorithm 贪心算法........................................................................................................................... 2 Winning Solutions 竞赛中的策略 .................................................................................................................. 4 More Search Techniques 更多的搜索方式 .................................................................................................... 6 Binary Numbers 二进制算法 ....................................................................................................................... 10 Graph Theory 图论知识 ............................................................................................................................... 12 Flood Fill 种子染色法 .................................................................................................................................. 19 Data Structures 数据结构 ............................................................................................................................. 22 Dynamic Programming 动态规划 ................................................................................................................ 29 Shortest Paths 最短路径 ............................................................................................................................... 35 Minimal Spanning Trees 最小生成树(MST)................................................................................................ 40 Knapsack Problems 背包问题 ...................................................................................................................... 42 Eulerian Tour 欧拉通路 ................................................................................................................................ 44 Computational Geometry 计算几何 ............................................................................................................. 53 Optimization 最优化..................................................................................................................................... 58 Network Flow 网络流................................................................................................................................... 60 Big Number 高精度 ...................................................................................................................................... 64 Two Dimensional Convex Hull 二维凸包 .................................................................................................... 68 Heuristic Search 启发式搜索 ....................................................................................................................... 76

Section 1.2

Complete Search 枚举搜索

USACO 教程 2 号灯的状态也永远与 8 号灯，14 号灯，20 号灯……相同。同样，无论你按了多少次开关，按同一个开关两次 就相当于没有按该开关，那么每一个开关就只需要考虑按一次或没有按，那么这题的枚举量就很小了。 例题 2: 时钟调整 [IOI 94] 有九个钟被摆放在一个 3 X 3 的矩阵中，它们各自指向 12：00，9：00，6：00，3：00 中的一种，你的目的 是将它们的指针全部调向 12：00。很遗憾，每一次调整你都只能从九种调整方案中选择一种执行（九种方案已 被从 1 到 9 编号），每一种方案可以改变固定钟的状态（例如：方案 1 控制钟 1，2，3，方案 2 控制钟 1，4，7， 方案 3 控制钟 5，6，8，9……），即将方案指定的所有钟向前拨快 3 小时（使时针向顺时针方向旋转 90 度）， 请你输出一个数列，使得按该数列表示方案执行后，所有钟都指向 12：00。并且如果把整个序列看作一个数， 要求该数最小。 最容易想到的方法是用递归枚举 1 到 9 的方案在该步使用。很可怕，由于递归的层数在此没有限定，所以将 用掉 9k 的时间（k 为层数），那可能是相当巨大的。其实，不用紧张，细心的你一定会发现：当一个方案执行 4 次后，就相当于没有执行，又因为题目要求输出最优解，那么任意一个方案都没有必要 4 次以上执行。也就是 说，只需要枚举每一个方案的 4 种情况（没执行，执行 1，2，3 次）就可以了。他仅有 49 ，约 262,072 此枚举， 我们的计算机 1s 内就可以算完，应该算是极快了。 类似问题： 挤牛奶 [USACO 1996 初赛] 给出一个挤牛奶的顺序（农夫 A 在 300 秒到 1000 秒时挤牛奶, 农夫 B 从 700 秒到 1200 秒），要求输出： 最长的有人挤牛奶的时间。 最长的没人挤牛奶的时间。 完全数牛与完全数牛群 [USACO 1995 决赛] 如果一个数可以由它的某几个约数相加得到，那么我们叫它完全数，如 28 = 1 + 2 + 4 + 7 + 14。而一对完全 对数就是指两个数都可以由对方的约数相加得出。 同样一个完全数组就是一个数组的第一个数可以由第二个数的 约数加和得到，第二个数也可以由第三个数的约数相加得到……最后一个数可以由第一个数的约数加和得到。 现在 Farmer John 已经将它的牛儿们编好了号（1 到 32000）请找出其中所有的完全数牛与完全数牛群。

Section 1.3

Greedy Algorithm 贪心算法

USACO 教程 但你得到了 N = 5 时的最优解后，你只需要在已用上的 5 块木板中寻找最靠近的两块，然后贴上中间的几个牛 棚，使两块木板变成一块。这样生成的 N = 4 的解必定最优。因为这样木板的浪费最少。同样，其他的贪心题 也会有这样的性质。正因为贪心有如此性质，它才能比其他算法要快。 ② 贪心的正确性： 要证明贪心性质的正确性， 才是贪心算法的真正挑战， 因为并不是每次局部最优解都会与整体最优解之间有 联系，往往靠贪心生成的解不是最优解。这样，贪心性质的证明就成了贪心算法正确的关键。一个你想出的贪心 性质也许是错的，即使它在大部分数据中都是可行的，你必须考虑到所有可能出现的特殊情况，并证明你的贪心 性质在这些特殊情况中仍然正确。这样经过千锤百炼的性质才能构成一个正确的贪心。 在样例中，我们的贪心性质是正确的。如下： 假设我们的答案盖住了较大的空牛棚连续列，而不是较小的。那么我们把那部分盖空牛棚的木板锯下来，用 来把较小的空牛棚连续列盖住，还会有剩余。那么锯掉它们！还给木材商！同时我们的解也变小了。也就是说， 我们获得更优的解。所以，靠盖住较大空牛棚连续列的方法无法获得最优解，我们也应该尽量贪心那些距离小的 木板合并。 如果仍有一个空牛棚连续列与我们的答案盖住的那个相同， 我们同样使用上述的方法。 会发现获得的新解与 原解相同，那么不论我们选哪个，结果都将一样。 由此可见，如果我们合并的两块木板间距离最短，那么总能获得最优解。所以，在解题的每一步中，我们都 只需要寻找两块距离最小的木板并合并它们。这样，我们获得的解必定最优。 结论： 如果有贪心性质存在，那么一定要采用！因为它容易编写，容易调试，速度极快，并且节约空间。几乎可以 说，它是所有算法中最好的。但是应该注意，别陷入证明不正确贪心性质的泥塘中无法自拔，因为贪心算法的适 用范围并不大，而且有一部分极难证明，若是没有把握，最好还是不要冒险，因为还有其他算法会比它要保险。 类似问题： 三值排序问题 [IOI 1996] 有一个由 N 个数值均为 1、2 或 3 的数构成的序列（N<= 1000） ，其值无序，现要求你用最少的交换次数将 序列按升序顺序排列。 算法：排序后的序列分为三个部分：排序后应存储 1 的部分，排序后应存储 2 的部分和排序后应存储 3 的部 分，贪心排序法应交换尽量多的交换后位置正确的（2，1）（3，1）和（3，2）数对。当这些数对交换完毕后， 、 再交换进行两次交换后位置正确的（1，2，3）三个数。 分析：很明显，每一次交换都可以改变两个数的位置，若经过一次交换以后，两个数的位置都由错误变为了 正确，那么它必定最优。同时我们还可发现，经过两次交换后，我们可以随意改变 3 个数的位置。那么如果存在 三个数恰好为 1，2 和 3，且位置都是错误的，那么进行两次交换使它们位置正确也必定最优。有由于该题具有 最优子结构性质，我们的贪心算法成立。 货币系统 -- 一个反例 [已删节] 奶牛王国刚刚独立，王国中的奶牛们要求设立一个货币系统，使得这个货币系统最好。现在告诉你一个货币 系统所包含的货币面额种类（假设全为硬币）以及所需要找的钱的大小，请给出用该货币系统找出该钱数，并且 要求硬币数尽量少。 算法：每次都选择面额不超过剩余钱数但却最大的一枚硬币。例如：有货币系统为{1，2，5，10}，要求找 出 16，那么第一次找出 10，第二次找出 5，第三次找出 1，恰好为最优解。

·3·

USACO 教程 错误分析: 其实可以发现，这种算法并不是每一次都能构成最优解。反例如：货币系统{1，5，8，10}，同 样找 16，贪心的结果是 10，5，1 三枚，但用两枚 8 的硬币才是最优解。因为这样，贪心的性质不成立，如此解 题也是错的。 拓扑排序 给你一些物品的集合，然后给你一些这些物品的摆放顺序的约束，如"物品 A 应摆放在物品 B 前"，请给出 一个这些物品的摆放方案，使得所有约束都可以得到满足。 算法：对于给定的物品创建一个有向图，A 到 B 的弧表示"物品 A 应摆放在物品 B 前”。以任意顺序对每个 物品进行遍历。每当你找到一个物品，他的入度为 0，那么贪心地将它放到当前序列的末尾，删除它所有的出弧， 然后对它的出弧指向的所有结点进行递归，用同样的算法。如果这个算法遍历了所有的物品，但却没有把所有的 物品排序，那就意味着没有满足条件的解。

Section 1.3

Winning Solutions 竞赛中的策略

USACO 教程
? ? ? ?

USACO 教程
? ? ? ?

Section 1.4

More Search Techniques 更多的搜索方式

USACO 教程 2 3 4 5 6 7 8 if filled all columns print solution and exit for each row if board(row, col) is not attacked place queen at (row, col) search(col+1) remove queen at (row, col)

·7·

USACO 教程 样例：骑士覆盖问题[经典问题] 在一个 n x n 的棋盘中摆放尽量少的骑士， 使得棋盘的每一格都会被至少一个骑士攻击到。 但骑士无法攻击 到它自己站的位置. 广度优先搜索 (BFS) 在这里，最好的方法莫过于先确定 k 个骑士能否实现后再尝试 k+1 个骑士，这就叫广度优先搜索。通常， 广度优先搜索需用队列来帮助实现。 1 process(state) 2 for each possible next state from this one 3 enqueue next state 4 search() 5 enqueue initial state 6 while !empty(queue) 7 state = get state from queue 8 process(state) 广度优先搜索得名于它的实现方式：每次都先将搜索树某一层的所有节点全部访问完毕后再访问下一层, 再 利用先前的那颗搜索树，广度优先搜索以如下顺序遍历：

·8·

USACO 教程 4 5 6 7 8 9 if depth == 0 return for i from nextpos to n*n put knight at i truncated_dfsearch(i+1, depth-1) remove knight at i

10 dfid_search 11 for depth = 0 to max_depth 12 truncated_dfsearch(0, depth) 复杂度： ID 时间复杂度与 DFS 的时间复杂度（O(n)）不同，另一方面，它要更复杂，某次 DFS 若限界 k 层，则耗 时 ck 。若搜索树共有 d 层，则一个完整的 DFS-ID 将耗时 c0 + c1 + c2 + ... + cd 。如果 c = 2 ，那么式子的和 是 cd+1 - 1 ，大约是同效 BFS 的两倍。当 c > 2 时（子节点的数目大于 2） ，差距将变小：ID 的时间消耗不可 能大于同效 BFS 的两倍。 所以，但数据较大时，ID-DFS 并不比 BFS 慢，但是空间复杂度却与 DFS 相同，比 BFS 小得多。 算法选择： 当你已经知道某题是一道搜索题，那么选择正确的搜索方式是十分重要的。下面给你一些选择的依据。 简表： 搜索方式 DFS BFS DFS+ID 时间 O(c k) O(c d ) O(c d) 空间 O(k) O(c d ) O(d) 适用情况 必须遍历整棵树，要求出解的深度或经的过节点，或者你并不需要解的深度最小。 了解到解十分靠近根节点，或者你需要解的深度最小。 需要做 BFS，但没有足够的空间，时间却很充裕。

d ：解的深度 k ：搜索树的深度 d <= k 记住每一种搜索法的优势。 如果要求求出最接近根节点的解， 则使用 BFD 或 ID。 而如果是其他的情况， DFS 是一种很好的搜索方式。如果没有足够的时间搜出所有解。那么使用的方法应最容易搜出可行解，如果答案可能 离根节点较近，那么就应该用 BFS 或 ID，相反，如果答案离根节点较远，那么使用 DFS 较好。还有，请仔细小 心空间的限制。如果空间不足以让你使用 BFS，那么请使用迭代加深吧！ 类似问题： 超级质数肋骨[USACO 1994 决赛] 一个数，如果它从右到左的一位、两位直到 N 位（N 是）所构成的数都是质数，那么它就称为超级质数。 例如：233、23、2 都是质数，所以 233 是超级质数。要求：读入一个数 N（N <= 9） ，编程输出所有有 N 位的超 级质数。 这题应使用 DFS，因为每一个答案都有 N 层（最底层） ，所以 DFS 是最好的． Betsy 的旅行 [USACO 1995 资格赛] 一个正方形的小镇被分成 NxN (2 <= N <= 6）个小方格，Besty 要从左上角的方格到达左下角的方格，并且 经过每一次方格都恰好经过一次。编程对于给定的 N 计算出 Besty 能采用的所有的旅行路线的数目。 这题要求求出解的数量，所以整颗搜索树都必须被遍历，这就与可行解的位置与出解速度没有关系了。所以 这题可以使用 BFS 或 DFS，又因为 DFS 需要的空间较少，所以 DFS 是较好的． ·9·

USACO 教程 奶牛运输 [USACO 1995 决赛] 奶牛运输公司拥有一辆运输卡车与牧场 A ，运输公司的任务是在 A，B，C，D，E，F 和 G 七个农场之间 运输奶牛。每两个农场之间的路程（可以用 floyed 改变）已给出。每天早晨，运输公司都必须确定一条运输路线， 使得运输的总距离最短。但必须遵守以下规则： 农场 A 是公司的基地。每天的运输都必须从这开始并且在这结束。 卡车任何时刻都只能最多承载一头奶牛。 给出的数据是奶牛的原先位置与运输结束后奶牛所在的位置。 而你的任务是在上述规则内寻找最短的运输路线。 在发现最优解时必须比较所有可行解，所以必须遍历整棵搜索树。所以，可以用 DFS 解题． 横越沙漠 [1992 IOI] 一群沙漠探险者正尝试着让他们中的一部分人横渡沙漠。 每一个探险者可以携带一定数量的水， 同时他们每 天也要喝掉一定量的水。 已知每个探险者可携带的水量与每天需要的水量都不同。 给出每个探险者能携带的水量 与需要的水量与横渡沙漠所需的天数，请编程求出最多能有几个人能横渡沙漠。所有探险者都必须存活，所以有 些探险者在中途必须返回，返回时也必须携带足够的水。当然，如果一个探险者返回时有剩余的水（除去返回所 需的水以外） ，他可以把剩余的水送给他的一个同伴，如果它的同伴可以携带的话。 这题可以分成两个小问题， 一个是如何为探险者分组， 另一个是某些探险者应在何处返回。 所以使用 ID-DFS 是可行的。首先尝试每一个探险者能否独自横渡，然后是两个人配合，三个人配合。直到结束。

Section 1.5

Binary Numbers 二进制算法

(我狂晕，这个……明明是不知道谁直接在线翻译，根本不通顺就放上来的，奈何鄙人也不通鸟语，只能将一些 我看得懂的句子捋顺一下，望哪位大虾费神放个好的翻译上来) （额……我上学期刚学过口译，试着来完成前辈 未竟的事业） ---二进制数转换(基础)--电脑以 1 和 0 为基础操作的，这些被称为'二进制位'(bit)。 1 字节（Byte）内含有 8 位，例如：00110101。一个 整型数据（int）在我的计算机上是 4 个字节，32 位：10011010 11010101 10100010 10101011。其他计算机的字 节大小可能不同。 如你所见，32 个 1 和 0 记录下来或阅读起来有点麻烦。 因此，按照惯例人们把数字分成几组，每组 3 或 4 位： 1001.1010.1101.0101.1010.0010.1010.1011 10.011.010.110.101.011.010.001.010.101.011 < - (注意，从右往左开始计数 3) 这些分组，映射到数字，要么每 4 位表示一个 16 进制数（这里指个位数)或每 3 位表示一个 8 进制数。 很明 显，需要一些新的十六进制数字（小数点后数字只去 0 .. 9，我们还需要 6 个数字） 。现在，字母'A'..'F' 被用来表示这些新的数字：10 .. 15。 下面的这一张表，显而易见地表现了它们的转化方式： 替换：十六进制： 000 - > 0 100 - > 4 0000 - > 0 0100 - > 4 1000 - > 8 1100 - > C 001 - > 1 101 - > 5 0001 - > 1 0101 - > 5 1001 - > 9 1101 - > D 010 - > 2 110 - > 6 0010 - > 2 0110 - > 6 1010 - > A 1110 - > E 011 - > 3 111 - > 7 0011 - > 3 0111 - > 7 1011 - > B 1111 - > F 所以现在我们很快地用 C 语言或其他语言表示以上陈述那些十六进制和八进制整数： 1001.1010.1101.0101.1010.0010.1010.1011 - > 9 A D 5 A 2 A B- > 0x9AD5A2AB （0x 为在十六进制数前面的标志） 10.011.010.110.101.011.010.001.010.101.011 2 3 2 6 5 3 2 1 2 5 3 - > 023265321253 ·10·

USACO 教程 （这是前一个数字'0'）八进制的优点是可以比较容易、快速地写下来，但十六进制字节的更容易分离（这是因为 数字是成对的） 。 ---位运算(进阶)--有时为了效率将数字储存为位数字，而不是存储为整型。 比如在数组中记录选择（每个元素只可以是一个'是' 或'不'的状态） ，用数组对选项进行标记（相同的状态，即'真'，每个位是'是'就是'假'） ，或者记录一些小的连续整 数（例如对位元素 0 .. 3） 当然，有时问题其实包含'位串'。 。 在 C/C++和其语言中，如果你知道它的八进制或十六进制表示形式，指定一个二进制数是很容易的： i= 0x9AD 5A2AB;或 i= 023265321253; 更常见的是我们会用一个整数的权来记录状态。 比如下面这个例子： i= 0x10000 + 0x100; 直到同一位上都是 1 之前它都是符合要求的： i= 0x100 + 0x100; 在这种情况下会发生进 位，然后就得到了 0x200 而不是我们所希望得到的 0x100。 （在此接着前辈的工作翻译下去，修改了前面一些翻 译的和原文对比不准确的地方）而 C/C++等语言中的'|'，即“按位或”操作，却能达到我们所希望的要求。 “按位 或”操作的规则如下： 0 | 0 - > 0 0 | 1 - > 1 1 | 0 - > 1 1 | 1 - > 1 在 C 语言里'|'的操作称为'按位或'， 以免与它的表兄'||'， 即所谓的'逻辑或'或'or',混淆。 '||'运算符会计算其左侧的数， 如果假（在 C 语言中为 0） ，再判断其右侧的数。 如果任意一个不为零，那么'||'的结果为真（为 1） 。这是将'|'和' +'操作区分开来的最终规则。有时候这样的操作符运算以如下真值表的形式给出： | | 0 1 ---+-----0 | 0 1 1 | 1 1 显而易见，'按位或'的操作方式可以用来设置记录状态的整数。当任何一方或双方都是'1'时，输出结果为'1'。 最简单的查询方法是'逻辑与'（也称为'andif'）算子，记为'&'。真值表如下： & | 0 1 ---+-----0 | 0 0 1 | 0 1 只有当输入的两个值均为'1'时， 输出值才为'1'。 因此， 如果你想知道一个整数的 0x100 位是否为'1'， 语句很简单： if (a & 0x100) { printf("yes, 0x100 is on\n"); } C/C++以及其他语言还包含其他的操作符，比如“异或” ，用'^'表示，真值表如下： ^ | 0 1 ---+-----0 | 0 1 1 | 1 0 “异或”有时表示成'xor'，为了打字时比较轻松。 当且仅当输入的两个值之一是'1'时，输出结果才为 1。这个操 作符能够很方便的来控制“开关” ，即将数字的某一位由'1'变成'0'，或反之亦然。 例如以下这句代码： a = a ^ 0x100; /* same as a ^= 0x100; */ 在 0x100 位处将从 0 - > 1 或从 1 - > 0，根据其当前的值。 将某个数置零等同于两个基本操作符的运算（译者按：事实上下面是在讲异或的置零功能，即一个数和它本身进 行异或操作得到结果是 0，例如 xor ax,ax 是将 ax 寄存器置零） 我们新介绍一个一元运算符，它将一个数的每 。 一位翻转，以创造一个数的“按位补”或者简称“补码” 。这个运算符称为“按位取反”或者简称为“取反” ，记 为波浪符'~'。 下面是一个简单的例子： char a, b; /* eight bits, not 32 */ ·11·

USACO 教程 a = 0x4A; /* 0100.1010 */ b = ~a; /* flip every bit: 1011.0101 */ printf("b is 0x%X\n", b); 最终得出了这样的结果： b == 0xB5 所以，如果一个数我们只有一位是 1（例如，0x100） ，那么~0x100 将所有其他的'0'位置'1'而将该位置'0'，得到： 0xFFFFFEFF（注意'E'处于右起第三位，和原数的'1'位相同） 。 以下两个操作符将一个数完全置零： a = a & (~0x100); /* swtch off the 0x100 bit */ /* same as a &= ~0x100; 因为取反后，原本所有为'0'的都变成了'1'，而所有为'1'的都变成了'0'，所以每一位都保证有 0 的存在再进行按位 与操作后，所有的位数都变成了'0'。 总结 总之，这些操作符能够设置，清除，转换和查找整数中的任意一位二进制位： a |= 0x20; /* turn on bit 0x20 */ a &= ~0x20; /* turn off bit 0x20 */ a ^= 0x20; /* toggle bit 0x20 */ if (a & 0x20) { /* then the 0x20 bit is on */ } （鉴于本人水平有限，如果有译得不准确的地方，欢迎大牛们予以辅正！ ）

Section 2.1

Graph Theory 图论知识

USACO 教程 奶牛的电信 (USACO 锦标赛 1996) 农夫约翰的奶牛们喜欢通过电邮保持联系，于是她们建立了一个奶牛电脑网络，以便互相交流。这些机器用 如下的方式发送电邮：如果存在一个由 c 台电脑组成的序列 a1,a2,...,a(c)，且 a1 与 a2 相连，a2 与 a3 相连，等等， 那么电脑 a1 和 a(c)就可以互发电邮。很不幸，有时候奶牛会不小心踩到电脑上，农夫约翰的车也可能碾过电脑， 这台倒霉的电脑就会坏掉。这意味着这台电脑不能再发送电邮了，于是与这台电脑相关的连接也就不可用了。有 两头奶牛就想： 如果我们两个不能互发电邮， 至少需要坏掉多少台电脑呢？请编写一个程序为她们计算这个最小 值和与之对应的坏掉的电脑集合。 图: 每个结点表示一台电脑，而边就相对应的成了连接各台电脑的缆线。 骑马修栅栏 农民 John 每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。John 是一个与其他 农民一样懒的人。他讨厌骑马，因此从来不两次经过一个一个栅栏。你必须编一个程序，读入栅栏网络的描述， 并计算出一条修栅栏的路径，使每个栅栏都恰好被经过一次。John 能从任何一个顶点(即两个栅栏的交点)开始骑 马，在任意一个顶点结束。每一个栅栏连接两个顶点，顶点用 1 到 500 标号(虽然有的农场并没有 500 个顶点)。 一个顶点上可连接任意多(>=1)个栅栏。所有栅栏都是连通的(也就是你可以从任意一个栅栏到达另外的所有栅 栏)。你的程序必须输出骑马的路径(用路上依次经过的顶点号码表示)。我们如果把输出的路径看成是一个 500 进制的数，那么当存在多组解的情况下，输出 500 进制表示法中最小的一个 (也就是输出第一个数较小的，如果 还有多组解，输出第二个数较小的，等等)。输入数据保证至少有一个解。 图: 农民 John 从一个栅栏交叉点开始，经过所有栅栏一次。因而，图的结点就是栅栏交叉点，边就是栅栏。 骑士覆盖问题 在一个 n x n 的棋盘中摆放尽量少的骑士，使得棋盘的每一格都会被至少一个骑士攻击到。但骑士无法攻 击到它自己站的位置. 图: 这里的图较为特殊，棋盘的每一格都是一个结点，如果骑士能从这一格跳到另一格，这就说在这两个格 相对应的结点之间有一条边。 穿越栅栏 [1999 USACO 春季公开赛] 农夫 John 在外面的田野上搭建了一个巨大的用栅栏围成的迷宫。幸运的是，他在迷宫的边界上留出了两段 栅栏作为迷宫的出口。更幸运的是，他所建造的迷宫是一个 完美的迷宫：即你能从迷宫中的任意一点找到一条走出迷宫的路。 这是一个 W=5,H=3 的迷宫： +-+-+-+-+-+ | | +-+ +-+ + + | | | | + +-+-+ + + | | | +-+ +-+-+-+ 如上图的例子，栅栏的柱子只出现在奇数行或奇数列。每个迷宫只有两个出口。 图: 如上图，图的每一个位置都是一个结点，如果两个相邻的位置之间没有被栅栏分开，则说在这两个位置 相对应的结点之间有一条边。 用语： ·13·

USACO 教程 我们再看刚才的图：

USACO 教程 如果结点 x 到 v 有一条路径，则我们从结点 x 开始通过边必定能访问到结点 v。 在一条路径序列中，如果所经过的结点都只在序列中出现一次，我们就称它为简单路径 环的定义是一条起始结点与中止结点为同一结点的路径，如果一个环除了起始结点（中止结点）以外的所有 结点都只在环中出现一次，那么这种环被称为简单环。 以上定义同样适用于有向图。 图的表示法 选择一个好的方法来表示一张图是十分重要的，因为不同的图的表示方法有着不同的时间及空间需求。 通常，结点被用数字编号来表示，我们可以通过它们的编号数字来对他们进行索引。 这样，似乎所有问题 都集中在如何表示边上了。 边集 边集表示法似乎是最明显的表示法，他将所有边列成一张表，用结点来表示边。 该表示法容易编写，容易调试且所需空间小。但是，它需要花费相当大的代价用于确定一条边是否存在，即 确定两个结点是否相连。利用边集添加新边是很快的，但删除旧边就很麻烦了，尤其是当需要删除的边在边集中 的所在位置不确定时。 对于带权图，该表示法也只需要在边集中添加一个元素，用于记录边权。同样，该表示法也适用于有向图和 稀疏图。 例： 一张无向无权图可以表示成边集如下： v1 v2 e1 4 3 e2 1 3 e3 2 5 e4 6 1 e5 3 6 邻接矩阵 邻接矩阵式表示图的另一种方法， 邻接矩阵是一个 N 乘以 N 的数组 （N 为结点数） 如果边集 E 中存在边(i, 。 j)，则对应数组的(i,j)元素的值为一。相反，如果数组元素的值为零，就意味着图中结点 i 与 j 之间没有边。无向 图的邻接矩阵总是关于左上右下对角线对称。 该表示法容易编写。但他对空间的需求和浪费较大，尤其是对于较大的稀疏图，调试起来也比较麻烦，并且 寻找与某一结点相连的结点也很慢。不过该表示法在判断两结点是否相连，以及在添加、删除结点方面速度都是 极快的。 对于带权图，数组的(i,j)元素的值被表示为边(i,j)的权。对于无权复杂图来说，数组的(i,j)元素的值可以用于 表示结点(i,j)之间边的个数。而对于有权复杂图来说，邻接矩阵很难将其表示清楚。 例： 下面是用邻接矩阵表示一幅无权图的例子： V1 V2 V3 V4 V5 V6 V1 0 0 1 0 0 1 V2 0 0 0 0 1 0 V3 1 0 0 1 0 1 V4 0 0 1 0 0 0 V5 0 1 0 0 0 0 V6 1 0 1 0 0 0 邻接表

·15·

USACO 教程 第三种表示图的方法是用一个列表列出所有与现结点之间有边存在的结点名称。 该方法可以用一个长度为 N 的数组来实现（N 为结点个数） ，数组的每一个元素都是一个链表表头。数组的第 i 元素所连接的链表连接了所 有与结点 i 之间有边的结点名称。 该表示方法较难编写，特别是对于复杂图，两结点之间边的个数不受限制的时候，链表可能要做成环，或者 要动态分配内存。邻接表的调试也同样十分麻烦，特别是使用了环形链表后。但是，这种表示法所需求的空间与 边集相同，寻找某结点的相邻结点也十分容易，然而，如果需要判断两结点是否相邻，就需要遍历该结点的所有 相邻结点以证明相邻性，这浪费了不少时间。添加边十分容易，但删除边就十分困难了。 将该表示法用于带权图， 就需要在链表的每一节上添加一个元素用于储存该节表示的两结点之间的权。 有向 图与复杂图同样可以用邻接表表示。对于有向图，我们只需存储单向的相邻即可。 例：邻接表表示无向图如下： 邻接 结点 结点 1 3, 6 2 5 3 6, 4, 1 4 3 5 2 6 3, 1 表示法的选择 对于某些图来说，我们并不需要考虑所有结点之间的关系，例如上面的骑士覆盖和穿越栅栏两题，我们只需 考虑与某结点相邻结点之间的关系，确定相连，我们就不用考虑存储两个不相邻结点之间的信息。当然，这些信 息来自于题目本身的暗示。 如果你发现一种表示方法可以在规定空间与时间范围内实现你的算法解决问题， 并且可以使你的程序变得简 洁、容易调试，那它通常就是对的。记住，编写与调试的简单是最重要的，我们不需要为一些毫无意义的加快程 序速度，减少使用空间来浪费编写与调试的时间。 我们还要通过题目给我们的信息，确定我们要对图进行哪些操作，权衡后来决定表示方法。下面的表示我们 为您提供的选择依据（N 为结点数，M 为边数，d max 为图中度的最大值） ： 功效表 消耗空间 连接判断的消耗时间 检查某结点所有相邻结点的消耗时间 添加边的消耗时间 删除边的消耗时间 边集 2xM M M 1 M 邻接矩阵 N2 1 N 1 2 邻接表 2xM d max d max 1 2xd max

USACO 教程

·17·

USACO 教程

·18·

USACO 教程

Section 2.1

Flood Fill 种子染色法

USACO 教程 深搜最容易写，但它需要一个栈。搜索显式图没问题，而对于隐式图，栈可能就存不下了。 广搜稍微好一点，不过也存在问题。搜索大的图它的队列有可能存不下。深搜和广搜时间复杂度均为 O(N+ M)。其中，N 为结点数，M 为边数。 广度扫描需要的额外空间很少，或者可以说根本不要额外空间，但是它很慢。时间复杂度是 O(N^2+M)。 （实际应用中，我们一般写的是 DFS，因为快。空间不是问题，DFS 可改用非递归的栈操作完成。但为了 尊重原文，我们还是译出了广度扫描的全过程。——译者） 广度扫描的伪代码 代码中用了一个小技巧，因此无须额外空间。结点若未访问，将其归入连通子图（-2） ，就是代码里的 comp onent -2。这样无须额外空间来记录结点是否访问，请读者用心体会。 # component(i) denotes the # component that node i is in 1 function flood_fill(new_component) 2 do 3 num_visited = 0 4 for all nodes i 5 if component(i) = -2 6 num_visited = num_visited + 1 7 component(i) = new_component 8 for all neighbors j of node i 9 if component(j) = nil 10 component(j) = -2 11 until num_visited = 0 12 function find_components 13 num_components = 0 14 for all nodes i 15 component(node i) = nil 16 for all nodes i 17 if component(node i) is nil 18 num_components = num_components + 1 19 component(i) = -2 20 flood_fill(component num_components) 算法的时间复杂度是 O(N 2)，每个结点访问一次，每条边经过两次。 实例 考虑刚才的那张图：

·20·

USACO 教程

USACO 教程 这类问题一般很清晰，求解关于“连通”的问题会用到 Flood Fill。它也很经常用作某些算法的预处理。 扩展与延伸 有向图的连通性比较复杂。 同样的填充算法可以找出从一个结点能够到达的所有结点。每一层递归时，若一个结点未访问，就将其标记 为已访问（表示他可以从源结点到达)，然后对它所有能到达且为访问的结点进行下一层递归。 若要求出可以到达某个结点的所有结点，你可以对后向弧做相同的操作。 例题 控制公司 [有删节, IOI 93] 已知一个带权有向图，权值在 0-100 之间。 如果满足下列条件，那么结点 A“拥有”结点 B： A = B 从 A 到 B 有一条权值大于 50 的有向弧。 存在一系列结点 C 1 到 C k 满足 A 拥有 C 1 到 C k, 每个节点都有一条弧到 B，记作 x 1 ，x 2 ...x k，并且 x 1 + x 2 + ... + x k > 50。 找出所有的（A，B）对，满足 A 拥有 B。 分析：这题可以用上面提到的“给出一个源，在有向图中找出它能够到达的结点”算法的改进版解决。要计算 A 拥有的结点，要对每个结点计算其“控股百分比” 把它们全部设为 0。现在，在递归的每一步中，将其标记为 。 属于 A 并把它所有出弧的权加到“控股百分比”中。对于每个“控股百分比”超过 50 的结点，进行同样的操作（递 归） 。 街道赛跑 [IOI 95] 已知一个有向图，一个起点和一个终点。 找出所有的 p，使得从起点到终点的任何路径都必须经过 p。 分析：最简单的算法是枚举 p，然后把 p 删除，看看是否存在从起点到终点的通路。时间复杂度为 O(N (M + N))。题目的数据范围是 M 牛路 [1999 USACO 国家锦标赛, 有删节] 连通图的直径定义为图中任意两点间距离的最大值，两点间距离定义为最短路的长。 已知平面上一个点集，和这些点之间的连通关系，找出不在同一个连通子图中的两个点，使得连接这两个点 后产生的新图有最小的直径。 分析：找出原图的所有连通子图，然后枚举不在同一个连通子图内的每个点对，将其连接，然后找出最小直 径。 笨蛋建筑公司 Farmer John 计划建造一个新谷仓。不幸的是，建筑公司把他的建造计划和其他人的建造计划混淆了。Far mer John 要求谷仓只有一个房间，但是建筑公司为他建好的是有许多房间的谷仓。已知一个谷仓平面图，告诉 Farmer John 它一共有多少个房间。 分析：随便找一个格子，遍历所有与它连通的格子，得到一个房间。然后再找一个未访问的格子，做同样的 工作，直到所有的格子均已访问。虽然题目给你的不是直接的图，但你也可以很容易地对其进行 Flood Fill。

Section 2.2

Data Structures 数据结构

·22·

USACO 教程 如何选择最完美的数据结构 从一些数据结构中选择一个合适的数据结构来表示一个题目中的数据。 可否工作？ 如果数据结构将不能正常工作，这是完全没有用的。对于一个问题，什么样的算法可以决定什么样的数据结构， 并确保数据结构可以处理算法。如果不能，那么要么必须添加一些数据结构，或者你需要找到另外的数据结构来 构建这个算法。 可否编码？ 如果您不知道或不记得如何编写一个给定的数据结构，选择其他的数据结构。确保你有一个清醒的认识，知道每 一个操作对数据结构的影响。在此，另一个要考虑的是内存。这个数据结构能在适当大小的内存空间里运行吗？ 如果不能就简化它，或选择一个新的数据结构。否则，从一开始就注定了它不能正常工作。 按时完成？ 由于比赛是限定时间的，5 小时内解决 3 至 5 道题。如果你在第一题上为了数据结构就花了一个半小时，那么你 基本上已经悲剧了。 可否调试？ 在选择数据结构的时候很容易忘掉调试这部分。请记住一点，一个程序除非它能正常工作，否则它就是无用的。 不要忘记，在整个比赛的时间中，调试占的比例是很大的，因此必须把调试时间考虑到写程序的时间中。一个数 据结构是否容易调试取决于下面两个属性。 ? 静态的数据结构更易于检查 通常来说，规模更小、更紧凑的表达形式更容易检查。此外，静态分配的数 组比链表甚至于动态数组更容易检查。 ? 静态的数据结构更容易被显示 对于更复杂的数据结构，最简单的检验方法是写一个小例子来输出数据。 可惜，由于时间的限制，你可能想限制自己的文本输出。这意味着，像树和图的结构将难以检查。 是否快速？ 很奇怪，速度是在选择数据结构的时候是最后一个要考虑的。一个慢的程序很容易发现是什么导致了慢，但是一 个快速的错的程序却不容易发现什么导致了错，除非运气很好。 结论 总的说来，遵循 KISS 原则: “使其简单，傻瓜化。 ”(Keep It Simple, Stupid.) 有时候一定的复杂度是有必要的， 但请确保它值得。请牢记：在开始的时候花时间去确保你选择了一个合适的数据结构，比之后不得不用另一个数 据结构去替代它，要划算得多。 避免动态内存 通常情况下，你应当避免使用动态内存，因为： 使用动态内存会很容易犯错误！ 重写已分配的内存，忘记释 ！ 放内存，忘记分配内存，只是使用动态内存时引入的一点错误。此外，这些错误的出错代码很难告诉我们发生错 误的位置，因为它可能发生在一个（可能更晚）内存操作时。 检查数据结构的含义太难了！ 集成开发环境不 ！ 能很好地操作动态内存，尤其对于 C 语言更是一塌糊涂。尝试考虑使用并行数组来实现动态内存，比如使用链 表时用另一个数组来存储 next 值序列。有时你可以动态分配这些，但是因为它只需要完成一次，所以用数组来 实现插入或删除操作会比分配释放内存更简单。尽管如此，有时动态内存也是一种好的办法，特别是对于未知数 据范围的大型数据结构。 避免猎奇想法 不要掉进“猎奇”的陷阱。你可能刚发现了最有趣的结构，但是要记住： ? 好点子，不工作，没有用。 ·23·

USACO 教程 酷想法，编不出，也没用。 你的数据结构是有效的，比你如何改进你的数据结构更加重要。 基本结构 有五种基本数据结构：数组、链表、栈、队列和双向队列。你可能在之前已经见过这些东西；如果没有，可以问 你老师。 二叉查找树 二叉查找树使您能够迅速搜索对象的集合（实型或整数）以确定给定的数值是否在集合中。基本上，二叉查找树 是一个加权， 有根的二叉规则树。 这样的描述意味着树中的每个节点可能有一个'右 ‘子节点和一个`左'子节点 （但 双方或一方可能会丢失） 。此外，每个节点都有与之相关联的对象，权值是对象在该节点的数值。二叉查找树有 这样的属性：每个节点的左子树上的值小于该节点的值，每个节点的右子树的值大于或等于它。
?

USACO 教程 集合里。另一方面，把 'ACT' 代入散列函数得到 7，所以程序必须检验条目 'COB' 和 'ACT' 是否相同。考虑如 下函数： #define NHASH 8999 /* 保证它是素数 */ hashnum(p) char *p; { unsigned int sum = 0; for ( ; *p; p++) sum = (sum << 3) + *p; return sum % NHASH; } 对每个输入， 函数返回 0..NHASH-1 的某个数。 它的输出是均匀随机的。 这个简单的函数要求 NHASH 是素数。 把上面的函数与下面的主程序合在一起： #include main() { FILE *in; char line[100], *p; in = fopen ("/usr/share/dict/words", "r"); while (fgets (line, 100, in)) { for (p = line; *p; p++) if (*p == '\n') { *p = '\0'; break; } printf("%6d %s\n", hashnum(line), line); } exit (0); } 就会产生类似这样的英文单词表（当然这得在 Linux 下运行） ： 4645 aback 4678 abaft 6495 abandon 2634 abandoned 4810 abandoning 142 abandonment 7080 abandons 4767 abase 2240 abased 7076 abasement 4026 abasements 2255 abases 4770 abash 222 abashed 237 abashes 2215 abashing 361 abasing 4775 abate 2304 abated 3848 abatement ·25·

USACO 教程 ... ... 你可以看到函数产生的数字全部是均匀随机的，并且起码在这个例子中没有重复。当然，如果你有 NHASH+1 个单词，鸽笼定理证明了至少会有两个单词返回值相同，这就叫“冲突” 。实际上，散列表使用链表技术解决了 这种冲突，即相同值的单词列在同一区域。看看散列表究竟该怎么用吧。首先，建立散列表的链表结构，就像这 样： struct hash_f { struct hash_f *h_next; char *h_string; int }; struct hash_f *hashtable[NHASH]; /* 每个链表的头指针 */ /* 全局变量自动置空 */ 产生如此散列表，比如用两个元素为父亲： hashtable *hash_f *hash_f +------------+ 0 | | +-----------+ +-----------+ +------------+ | *|-+ | 0| 1 | | +-----------+ | +-----------+ +------------+ | 'string1' | | | 'abc def' | 2 | * |->+-----------+ +->+-----------+ +------------+ | val=1234 | | val=43225 | 3 | | +-----------+ +-----------+ +------------+ ... 8998 | | +------------+ 下面是插入操作： struct hash_f * hashinsert(p, val) char *p; int val; { int n = hashnum(p); /* 表的位置 */ char *h = malloc( sizeof (struct hash_f) ); /* 新建散列元素 */ /* 链接到表头： */ h->h_next = hashtable[n]; hashtable[n] = h; /* 可选值： */ h->h_val = val; /* 然后在链中找到适合元素放置的地方: */ h->h_string = malloc( strlen(p) + 1 ); strcpy (h->h_string, p); h_value; /* 一些和字符串相关的值*/ /* 完全自由选择如何使用或它已经存在*/

·26·

USACO 教程 return h; } 下面是查找操作（若找到则返回其指针） ： struct hash_f * hashlookup(p) { struct hash_f *h; int n = hashnum(p); /* 初始位置 */

for (h = hashtable[n]; h; h=h->h_next) /* 遍历链表 */ if (0 == strcmp (p, h->h_string)) /* 匹配？完成！ */ return h; return 0; } 现在你可以快速地插入和查找了，平均需要(链表大小/2)次字符串比较。 为何散列表可用？ 散列表只占用一点点内存，而程序查找元素几乎只要常数时间。通常程序要评估函数的价值，并且可能需要在表 中比较一次或若干次【这句话翻得不好】 。 散列函数 经常忘记的是，更精确点说，避免冲突的方法是找一个好的散列函数。举个例子，以单词前三个字母作为散列值 显然很悲催。在此散列函数下，前缀 "CON" 会产生一个巨大的序列。你选择的函数要尽可能使不同的元素分配 到不同的位置: ? 把巨大值用表的大小求模（选一个素数会干得特别好） 。 ? 素数是你的朋友。用它们相乘。 ? 试着用小的 changes 映射到完全不同的地方。 ? 不要想用两个小 changes 就能撤销映射到表外的函数（如一个变换） 。 ? 有一个研究的全域，要求创造一个“完美散列函数”以至于没有冲突，但是，完全产生均匀随机显然是 要大量工作的；希望以后会有吧，起码现在木有啊。 散列变量 只用数值处理信息经常十分有用。比如当在一个大集合中搜寻一个小子集，用散列表处理已访问域，你可能想把 它的搜索的价值定位在哈希表中. 甚至一个小散列表通过彻底减少搜寻空间都能改进运行时间。比如用首字母标 识字典，你只需要找首字母就可以了。 一种特殊的树——“Trie” /* 未找到 */

·27·

USACO 教程 简单来说，Trie 就是指有根树。它有不受限制的出度(即一个节点可能有任意多个子节点). 一个节点的子节点存 储在一个链表之中, 所以一个节点有两个指针, 下一个兄弟和第一个子节点（这样实际上就把一个普通的树转化 为了一棵普通的二叉树） Tries 存储一个序列集合. 每条从根节点指向叶子节点的路径都对应集合中的一个元素. . 比如, 对于图中的 trie, 指定了的集合是"CAR", "CAT", 和 "COB"假定没有其它节点存在.要测定一个序列是否 在集合之中, 可以从根开始, 在它的子节点中寻找序列的起始元素. 如果没有匹配的, 这个序列就不在集合中. 否则, 再在这个节点的子节点中寻找后面的元素, 以此类推. trie 有几个不错的特点。如果一个字符串在列表中， 检索的时间复杂度将不超过字符串的长度乘以一个节点的的最大子节点数。此外，比起其他的来说，这个数据结 构往往可以使用较少的内存，因为前缀只出现一次（在我们的例子中，虽然'CAR'和'CAT'同时存在，但是只有一 个'CA'的节点出现） 。在一般情况下，对于已知前缀，查找字符序列（语句，多位数的号码，等等）的问题，trie 是很好用的。 Trie 优化 一些常见的轻微改动有： 对于节点增加标记信息。如果列表里可能包含一个是其他单词前缀的词，你必须添加一个标志在每个节点上说' 一个字到此为止'。如上例中，如果'CA'也作为单词出现在你的列表中，它会被标记。在链表中保持子节点有序。 这增加了时间来建立树，但减少了查询时间。建立字符串节点；如果你有很多单词前缀一致但后缀独立，有时为 其建立“特殊节点”更好。例如，存储“CARTING”“COBBLER”“CATCHING”这三个词，用“RTING” ， ， 、 “BBLER”“TCHING”这三个节点显然可以节约内存。注意这同时增加了复杂性。 、 堆 堆（有时称为优先级队列）是一个完全二叉树，每个节点的值小于其两个孩子的值: {{./pasted_image002.png}} 堆的表示法 如果树(tree) 是一层一层地从左到右地填入的（也就是说除了树最底层以外其他层都是完整的，最底层的元素是 按从左到右填入的） ，那么这个堆（heap）能存储为一个数组，这个数组中元素的排列顺序是从根到底层，每层 从左到右。这个例子中的堆可以表示为 3 5 9 6 12 13 10 8 11 在这个表示方法中，位于 x 的节点（node）的子节点（children）位于 2x 和 2x＋1 ，(假设变址为 1)，x 的父节 点（parent）是向下取整（truncate）x/2 堆中结点的插入和移动操作 将结点置于数组末端， 接着交换结点与父节点的位置， 直到找到一个合适的父节点。 例如， 插入数字 4 的过程中， 堆数组（小根堆）变化如下: 3 5 9 6 12 13 10 8 11 4 3 5 9 6 4 13 10 8 11 12 3 4 9 6 5 13 10 8 11 12 删除一个结点相对来说也很简单。用数列末尾的结点取代要删除的，再进行调整：当结点的孩子比它小时，与较 小的孩子交换。例如，删除数字 3 的过程： 11 5 9 6 12 13 10 8 5 11 9 6 12 13 10 8 5 6 9 11 12 13 10 8 5 6 9 8 12 13 10 11 如果我需要修改一个变量的值呢？ 要把一个变量加大，则改变它的值，然后如果需要的话不断和它的父变量交换位置。T 要把一个变量的值减小， 则改变它的值，然后如果需要的话和它的子变量中较小的交换位置。 堆的适用范围 ·28·

USACO 教程 对于动态的一组数询问最小值时，用堆处理十分便利。它结构紧凑，便于调整。Dijkstra 算法的堆优化就是一个 很好的例子。 Heap Variations In this representation, just the weight was kept. Usually you want more data than that, so you can either keep that data and move it (if it's small) or keep pointers to the data. Since when you want to fiddle with values, the first thing you have to do is find the location of the value you wish to alter, it's often helpful to keep t hat data around. (e.g., node x is represented in location 16 of the heap).

Section 2.2

Dynamic Programming 动态规划

USACO 教程 考虑长度为 1 的序列从末端开始的情况。任意长度为 1 的序列都满足最长序列的所有标准。本例将‘bestsofa r’数组标记为‘1’ 。 考虑序列的最后两个元素。如果倒数第二个数字比最后那个大，那么‘bestsofar’为 2（1+最后那个数字的‘bes tsofar’ 。否则为 1。 ） 考虑在最后两个元素之前的任一元素。它总是比接近末尾的那个元素大。它的‘bestsofar’元素至少比找到的 较小元素的大 1。最后‘bestsofar’的最大值就是最长递减子序列的长度。 这很明显是一个 O(N 2)算法。代码如下： 1 #include 2 #define MAXN 10000 3 main () { 4 long num[MAXN], bestsofar[MAXN]; 5 FILE *in, *out; 6 long n, i, j, longest = 0; 7 in = fopen ("input.txt", "r"); 8 out = fopen ("output.txt", "w"); 9 fscanf(in, "%ld", &n); 10 for (i = 0; i = 0; i--) { 13 bestsofar[i] = 1; 14 for (j = i+1; j = bestsofar[i]) { 16 bestsofar[i] = bestsofar[j] + 1; 17 if (bestsofar[i] > longest) longest = bestsofar[i]; 18 } 19 } 20 } 21 fprintf(out, "bestsofar is %d\n", longest); 22 exit(0); 23 } 同样地， 行建立了末尾条件。 11 12-20 行以‘i’循环从后计数和‘j’循环从前计数的巧妙直接的方法运行 O （N2） 算法。尽管比前面的那个算法多 1 行，运行时间却更佳： N Secs 1000 0.080 2000 0.240 3000 0.550 4000 0.950 5000 1.450 6000 2.080 7000 2.990 8000 3.700 9000 4.700 10000 6.330 11000 7.350 当 N=9000 时由于竞争，算法依就很慢。 内部循环（ “寻找任意较小的数” 乞求用一些存储空间来交换时间。 ） 一组不同的值最好存在辅助数组中。数组‘bestrun’的指针是最长子序列的长度，其值是率领子序列的第一个 （也被证明是最佳的）整数。执行该数组。当遇到一个整数比在这个数组中的值大时就意味着可能会产生一个新 的更长的序列。新整数可能是一个新的“序列最佳首部” 也可能不是。看下面这个序列： ， 10 8 9 4 6 3 从右向左浏览（从后向前） ，遇到 3 之后‘bestrun’数组有且只有一个元素： ·30·

USACO 教程 0：3 继续浏览，6 比 3 大， ‘bestrun’数组变成： 0:3 1:6 4 不比 6 大，但它比 3 大，所以数组变为： 0:3 1:4 9 使数组增大为： 0:3 1:4 2:9 8 同 4 使数组变成： 0:3 1:4 2:8 l0 再次扩增数组为： 0:3 1:4 2:8 3:10 于是结果出来了：4（数组中有 4 个元素） 。 因为‘bestrun’数组可能比处理过的序列长度增长得慢，这个算法可能比上一个运行得要快。实际上是增速很 多。代码如下： 1 #include 2 #define MAXN 200000 3 main () { 4 FILE *in, *out; 5 long num[MAXN], bestrun[MAXN]; 6 long n, i, j, highestrun = 0; 7 in = fopen ("input.txt", "r"); 8 out = fopen ("output.txt", "w"); 9 fscanf(in, "%ld", &n); 10 for (i = 0; i = 0; i--) { 14 if (num[i] = 0; j--) { 19 if (num[i] > bestrun[j]) { 20 if (j == highestrun - 1 || num[i] #define SIZE 200000 #define MAX(x,y) ((x)>(y)?(x):(y)) int best[SIZE]; // best[] holds values of the optimal sub-sequence int main (void) { FILE *in = fopen ("input.txt", "r"); FILE *out = fopen ("output.txt", "w"); int i, n, k, x, sol = -1; fscanf (in, "%d", &n); // N = how many integers to read in for (i = 0; i x; k++) ; best[k] = x; ·31·

USACO 教程 sol = MAX (sol, k + 1); } printf ("best is %d\n", sol); return 0; } 为了不溢出，Tyler Lu 指出： 目前存在的算法使用线性查找来寻找合适的位置在‘bestrun’数组中插入一个整数。但是，因为辅助数组已分 好类，我们可以用二叉查找（O（logN）。这样对于大型序列我们的运行时间就降下来了。下面是将上面代码修 ） 改后的解法： #include #define SIZE 200000 #define MAX(x,y) ((x)>(y)?(x):(y)) int best[SIZE]; // best[] holds values of the optimal sub-sequence int main (void) { FILE *in = fopen ("input.txt", "r"); int i, n, k, x, sol; int low, high; fscanf (in, "%d", &n); // N = how many integers to read in // read in the first integer fscanf (in, "%d", &best[0]); sol = 1; for (i = 1; i = best[0]) { k = 0; best[0] = x; } else { // use binary search instead low = 0; high = sol-1; for(;;) { k = (int) (low + high) / 2; // go lower in the array if(x > best[k] && x > best[k-1]) { high = k - 1; continue; } // go higher in the array if(x best[k] && x best[k+1]) best[++k] = x; break; } } sol = MAX (sol, k + 1); } printf ("best is %d\n", sol); fclose(in); return 0; ·32·

USACO 教程 } 摘要 这些程序证明了动态规划背后的主要构想： 在先前找到的算法的基础上建立更大的算法。 这种逐步建立的解 法通常能产生速度非常快的程序。 由于前面编程的挑战，主要的子问题是：在已知元素的右侧数字中找到最大的递减子序列（及其第一个值） 。 这种方法可解决被称为“一维的”一类问题。 二维动态规划 有时可能会创建如此的多维问题：已知两个整数序列，求二者的最长公共子序列。 这里，子问题就是较小序列（原来子序列末端部分）的最长公共子序列。首先，如果两序列之中的一个序列 只含有一个元素，那解法就不重要了（或者所求元素在另一个序列中或者不在） 。 考虑在第一个序列最后 i 个元素和在第二个元素最后 j 个元素中找到最长公共子序列的问题。有两种可能。 第一个末尾部分的首元素可能在最大公共子序列中也可能不在。 不包含第一个末尾部分首元素的最长公共序列就 是第一个序列最后 i-1 个元素和第二个序列最后 j 个无素的最长公共子序列。第二个序列的末尾部分中某元素同 第一个序列末尾部分的首元素一样且能找到在那些匹配元素之后元素的最长公共子序列，这导致了第二种可能。

USACO 教程 15 maxlen = length[loc+1,element] # longest common subsequence includes first element 16 if list1[loc] = list2[element] 17 &nbs p; ; length[loc+1,element+1]+1 > maxlen 18 maxlen = length[loc,element+1] + 1 19 length[loc,element] = maxlen 这个程序的运行时间是 O（NxM） 和 M 分别为序列的长度。 ，N 本算法并不直接计算最长公共子序列。但是，如果给出长度矩阵，你就可以很快地确定子序列了： 1 location1 = 1 2 location2 = 1 3 while (length[location1,location2] != 0) 4 flag = False 5 for element = location2 to length2 6 if (list1[location1] = list2[element] AND 7 length[location1+1,element+1]+1 = length[location1,location2] 8 output (list1[location1],list2[element]) 9 location2 = element + 1 10 flag = True 11 break for 12 location1 = location1 + 1 动态规划的技巧就是找到子问题来解决它。有时它需要多个参数： 振荡（？？？）序列是指第一部分递增且第二部分递减的序列。求一整数列的最长振荡序列（振荡可以是先 增再减也可以是先减再增，但本问题只考虑先增加再减少的情况） 。 这个问题的子问题是最长振荡序列和序列前缀的最长递减序列。 有时子问题被很好的隐藏起来了： 你刚赢得一场比赛，奖励是一份免费到加拿大的旅游。你必须乘飞机游玩，城市从东到西依次排列。另外， 根据规则，你必须从最西侧的城市开始一直向东游览，直到你到达最东边的城市，再一直向西飞回到起点。另外 每个城市参观一次（当然起点城市除外） 。 已知城市顺序和乘坐的航班（你只能在某些城市间飞，因为你可以从 A 城飞到 B 城不意味着你可以向其它 方向下） ，求你最多能参观多少个城市。 若使用动态规划应注意的是你的位置和你的方向， 但重要的是你采用的路径 （因为在回程时你不能再次参观 某个己参观过的城市） ，而且路径数不能太多，否则将无法解出（并存贮）所有子问题的答案。 但是，如果不是寻找上面描述的路径，而是用另一不同的方式，那么状态数将大大减少。想像一下，有两个 旅行者从最西侧的城市出发。两旅行者轮流向东走，而旅行者走的下一站总是最西侧的城市，但是两旅行者不能 在同一个城市，除非他们在第一个或最后一个城市。但是，其中一个旅行者只允许使用“相反的班次” 即他可以 ， 从 A 城飞到 B 城当且仅当有一架从 B 城飞往 A 城的航班飞机。 从两个旅行者的路径中找到可以组合成一个环程旅行 （用一个旅行者的正常路径飞到最东边的城市， 然后再 用另一个旅行者相反的路径返回最西侧的城市）并不太困难。而当旅行者 x 走了，你知道旅行者 y 除了他现在所 在的城市外没参观过任何一个旅行者 x 东边的城市， 否则 x 在 y 西侧时旅行者 y 已经走过一次了。 于是两旅行者 的路径就无法接在一起了。此算法能产生参观城市最大值的原因留作练习。 通过动态规划将问题求解 一般地， 动态规划解法应用在那些可能会花费指数级时间的算法上， 因此如果有界限问题在任意但输入较少 的情况下太大以至于不能以指数时间级运行时，可考虑使用动态规划法。基本上，任何问题你只要考虑到用递归 下降的方法，如果输入不超过 30 就可以试试是否有动态规划的解法存在。 寻找子问题 ·34·

USACO 教程 如上所述，找到子问题是进行动态规划的重要一步。你的目的是用少量的数据，如一个整数、一对整数、一 个布尔数和一个整数等等，完整地描述出算法的状态。 若不失败，子问题会是一个问题的“尾端” 也就是说，有一个进行递归下降的方法这样每一步你只能处理一 。 小部分数据。举个例子，在飞行旅游的那道题中，你可从使用递归下降的方法找到完整的路径，那也意味着你得 记住你的位置和你已参观过的城市（记城列表或布尔数组的形式） 。这样动态规划要做的就太多了。但是在你向 东飞的一对城市问使用递归给已知常数是需要递归的非常小的一部分数据。 如果路线很重要，除非路径很短，你不要使用动态规划。但是正如飞行旅行问题，路线也许不重要，就看你 怎么看了。 示例题目 多边形游戏《1998 IOI》 想像一个均匀的 N 边形。结点处放入数字，边放入操作符‘+’或‘x’ 第一次去掉一条边。然后，合并边，即 。 计算出操作符两边结点的值，将其代替原来的边和结点，举例如下： ...-- 3 --+-- 5 --*-- 7 --... ...----- 8 ----*----- 7 --... ...-------- 56 -----------... 已知一作好标记的 N 边形，求最后计算出的最大值。 子集和《春季 98 USACO》 从 1 到 N（N 在 1 到 39 之间）的连续整数的集合，可将其分成和相等的两个集合，例如，若 N=3，将集合 《1，2，3》分成《3》和《1，2》两个子集合且其和相等。这计为单独划分（如，反序计为同样的划分，并不增 加划分数） 。 若 N=7，有 4 种方法将集合{1, 2, 3, ... 7} 分成和相等的两部分： {1,6,7} - {2,3,4,5} {2,5,7} - {1,3,4,6} {3,4,7} - {1,2,5,6} {1,2,4,7} - {3,5,6} 已知 N，打印将从 1 到 N 个整数的集合分成和相等的两个集合的各种方法。若没有则打印 0。 数字游戏《IOI96 ，maybe》 已知不超过 100 个整数（-32000_32000）列，两个对手依次轮流从数列的最左边或最后边去掉一个数。游戏 到最后每个玩家的分是他去掉的数的和。 已知一数列， 假设第二位玩家玩得非常好， 求第一位玩家赢时的最高分。

Section 2.4

Shortest Paths 最短路径

USACO 教程 +-+ +-+-+-+ 如上图的例子，栅栏的柱子只出现在奇数行或奇数列。每个迷宫只有两个出口。 The Abstraction 给出:一个边的权为非负的有向图 两个顶点间的一条路径是由图中相邻的边以任意的顺序连接而成的 两个顶点之间的最短路径是指图中连接这两个顶点的路径中代价最小的一条， 一条路径的代价是指路径上所 有边的权的和 题目常常只要求出最短路径的代价而不需要求出路径本身。 在这个例子中只用求出迷宫内部的点和出口之间 的最短距离(代价)。最别的，它需在求出所有代价中最大的一个。 用 Dijkstra 算法来求加权图中的最短路径 给出:所有的顶点、边、边的权，这个算法按离源点的距离从近到远的顺序来"访问"每个顶点。 开始时把所有不相邻顶点间的距离(边的权)标为无穷大,自己到自己的距离标为 0。 每次,找出一个到源点距离最近并且没有访问过的顶点 u。 现在源点到这个顶点的距离就被确定为源点到这个 顶点的最短距离。 考虑和 u 相邻的每个顶点 v 通过 u 到源点的距离。 考查顶点 v,看这条路径是不是更优于已知的 v 到源点的路 径,如果是,更新 v 的最佳路径。 [In determining the shortest path to a particular vertex, this algorithm determines all shorter paths from the sou rce vertex as well since no more work is required to calculate all shortest paths from a single source to vertic es in a graph. ] 参考: [Cormen, Leiserson, Rivest]的第 25 章 Pseudocode: # distance(j) is distance from source vertex to vertex j # parent(j) is the vertex that precedes vertex j in any shortest path # (to reconstruct the path subsequently) 1 For all nodes i 2 distance(i) = infinity # not reachable yet 3 visited(i) = False 4 parent(i) = nil # no path to vertex yet 5 distance(source) = 0 # source -> source is start of all paths 6 parent(source) = nil 7 8 while (nodesvisited 这个算法的时间效率为 O(V2)。你可以使用堆来确定下一个要访问的顶点来获得 O(E log V)的效率(这里的 E 是指边数 V 是指顶点数)，但这样做会使程序变得复杂，并且在一个大而稀疏的图中效率只能提高一点点。 Sample Algorithm Execution 考虑下面的图 这是问题的初始状态:

·36·

USACO 教程

·37·

USACO 教程

Sample Problem: Package Delivery 投递包裹 给出一个地点的集合，和连接它们的道路的长，和一个按排好的包裹要投递的地点的清单。找出按顺序投递 所有包裹的最短路程。 分析:对于每一次投递，使用 Dijkstra 算法来确定两个点间的最短路程。如果要投递的次数超过 N，我们就 用计算每对点之间的最短距离来代替计算每投递的最短路程， 最后只用简单把每一次投递一路程相加就是答案。 Extended Problem: All Pairs, Shortest Paths 每对点之间的最短路程 ·38·

USACO 教程 这个扩展问题就是确定一个表格 a： 这里 ai,j = 顶点 i 和 j 之间的最短距离，或者无穷大如果顶点 i 和 j 无法连通。 这个问题常常是其它大的问题的子问题，如投递包裹。 Dijkstra 算法确定单源最短路径的效率为 O(N2)。我们在每个顶点上执行一次的效率为 O(N3)。 如果不要求输出路径，还有一个更简单的算法效率也是 O(N3) The Floyd-Warshall Algorithm Floyd-Warshall 算法用来找出每对点之间的最短距离。它需要用邻接矩阵来储存边，这个算法通过考虑最佳 子路径来得到最佳路径。 注意单独一条边的路径也不一定是最佳路径。 从任意一条单边路径开始。一个两点之间的距离是边的权，或者无穷大如呆两点之间没有国相连。 对于每一对顶点 u 和 v， 看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。 如果是更新它。 不可思议的是，只要按排适当，就能得到结果。 想知道更多关于这个算法是如何工作的，请参考[Cormen, Leiserson, Rivest]第 26 章。 Pseudocode: # dist(i,j) is "best" distance so far from vertex i to vertex j # Start with all single edge paths. For i = 1 to n do For j = 1 to n do dist(i,j) = weight(i,j) For k = 1 to n do # k is the `intermediate' vertex For i = 1 to n do For j = 1 to n do if (dist(i,k) + dist(k,j) 这个算法的效率是 O(V3)。它需要邻接矩阵来储存图。 这个算法很容易实现，只要几行。 即使问题是求单源最短路径，还是推荐使用这个算法，如果时间和空间允许(只要有放的下邻接矩阵的空间， 时间上就没问题)。 Problem Cues 如果问题要求最佳路径或最短路程，这当然是一个最短路径问题。即使问题中没有给出一个图，如果问题要 求最小的代价并且这里没有很多的状态，这时常常可以构造一个图。最大的一点要注意的是:最短路径 = 搜索做 某件事的最小代价。 Extensions 如果图是不加权的，最短路径包括最少的边。这种情况下用宽优搜索(BFS)就可以了。如果图中有很多顶点 而边很少，这样会比 Dijkstra 算法要快(看例子 Amazing Barn) 如果充许负权边，那么 Dijkstra 算法就错了。幸运的是只要图中没有负权回路 Floyd-Warshall 算法就不受 影响(如果有负权回路，就可以多走几圈得到更小的代价)。所以在执行算法之前必须要检查一下图。 可以再增加一些条件来确定最短路径(如，边少的路径比较短)。只要用从距离函数中得到比较函数，问题就 是一样的。在上面的例子中距离函数包括两个值 代价和边数。两个值都要比较如果必要的话。 Sample Problems Graph diameter 图的直径 给出:一个无向无权的连通图,找出两点距离最远的顶点。 ·39·

USACO 教程 分析:找出所有点之间的最短距离，再找出最大的一个。 Knight moves 爵士的移动 给出:两个 N*N 的棋盘.确定一个爵士从一个棋盘移动到另一个所需的最少步数。 分析:把棋盘变成一个 64 个顶点的图。每个顶点有 8 条边表示爵士的移动。 Amazing Barn (abridged) [USACO Competition Round 1996] 考虑一个非常大的谷仓由 N(N "最中心的畜栏",一个畜栏到其它的平均距离最小则被认为是"最中心的畜栏" 的。 分析:计算每对顶点间的最短距离来确定平均距离。任何 O(N3)的算法在 N=2500 的情况下都是不行的。注意 到图中的边比较少(一个 4 条边)，用 BFS 加上队列是可行的，一次 BFS 的较率为 O(E)，所以 2500 x 10,000 = 2.5 x 106 比 25003 = 1.56 x 1010 要好的多。

Section 3.1

Minimal Spanning Trees 最小生成树(MST)

# # # 1 2 3 4 5 6 7 8

USACO 教程 9 10 11 12 13 distance(j) = weight(1,j) source(j) = 1 while (treesize < graphsize) find node with minimum distance to tree; call it node i assert (distance(i) != infinity, "Graph Is Not Connected") # add edge source(i),i to MST 14 treesize = treesize + 1 15 treecost = treecost + distance(i) 16 intree(i) = True # mark node i as in tree # update distance after node i added 17 for all neighbors j of node i 18 if (distance(j) > weight(i,j)) 19 distance(j) = weight(i,j) 20 source(j) = i 该算法的时间复杂度为 O(N2)。使用堆可以得到 O(N log N)的复杂度。图例： 考虑下图的权，边情况: 目标：生成最小生成树。 该算法将在 1）节点开始，它与节点 2） ，6） ，3）相连，权值情况如下： Node distance intree source 1 infinity True nil 2 30 False 1 3 20 False 1 6 25 False 1 已知不存在权为无穷大的情况。 （intree=False & source=nil） 可连接的最小权为 20, 所以节点 3）被连入树中： Node distance intree source 1 infinity True nil 2 9 False 3 3 20 True 1 6 25 False 1 7 7 False 3 注意：节点 3）现在已经“在树中”了，节点 2）的权已经从 20 变成的 9，且 source 也变成的 3。 可连接的最小权为 7, 所以节点 3）和 7）被连接: Node distance intree source 1 infinity True nil 2 9 False 3 3 20 True 1 6 10 False 7 7 7 True 3 可连接的最小权为节点 2）的 9。 连接节点 3)和 2） ： Node distance intree source 1 infinity True nil 2 9 True 3 3 20 True 1 4 21 False 2 5 9 False 2 6 10 False 7 7 7 True 3 连接节点 2）和 5） ： Node distance intree source 1 infinity True nil 2 9 True 3 3 20 True 1 4 8 False 5 5 9 True 2 6 10 Fa lse 7 7 7 True 3 8 12 False 5 下一步连接节点 5) 和 4）: Node distance intree source 1 infinity True nil 2 9 True 3 3 20 True 1 4 8 True 5 5 9 True 2 6 10 Fal se 7 7 7 True 3 8 12 False 5 连接节点 6）和 7）: Node distance intree source 1 infinity True nil 2 9 True 3 3 20 True 1 4 8 True 5 5 9 True 2 6 10 Tru e 7 7 7 True 3 8 11 False 6 最后，连接节点 6）和 8） ： Node distance intree source 1 infinity True nil 2 9 True 3 3 20 True 1 4 8 True 5 5 9 True 2 6 10 Tru e 7 7 7 True 3 8 11 True 6 最小生成树完成。注意： 必须知道某些情况下某些结点无法连入树中，应避免重复计算这些结点。 （即 intree=False & source=nil，在 例中没有该情况） 。题型提示： 如果某些问题需要一张最优的连通图，并且需要用以一个最小的花费来连接该系统或该系统的任意两个部 分，这样的问题就极类似最小生成树问题。 拓展： 如果你的生成树有任何约束条件的话（任意两个结点可能离得非常远，或者平均距离必须最小） ，这个算法 就玩完了，而且让程序适应这样的约束条件非常困难。 显而易见，任意两个结点之间不能有多边（你就留下权值最小的边，忽略其余的边） 。 Prim 算法无法扩展到有向图（如果你想要的是强连通图的话） 。例题：包裹寄送 ·41·

USACO 教程 给出：一些城市的位置，和轮船公司连接每对城市的航线的花费。找出使得一个包裹能够从任意一座城市送 到任意的另外一座城市的花费最小。高速公路建设 当然，为了经济效益，他们想要花最少的钱来做这件事。高速公路的花费正比于它的长度。给出 L.S. 州的 所有城市的 x,y 坐标，设计使得所有城市互相连通的最便宜的建造方案。 Bovile 电话(已删节) [USACO Traini ng Camp 1998, Contest 2] 给出：一些奶牛和田野中的干草堆（奶牛和干草堆在一起） ，连接任意的位置需要一定的花费。只用干草堆 和奶牛，计算哪些干草堆应该包含在干草堆网络中，并且使总花费最小。 分析：对于每一组可能的干草堆（也就是，共有 2 n 组） ，计算这组干草堆和奶牛的最小生成树。计算最小 生成树的组合，使得花费最小。

Section 3.2 Knapsack Problems 背包问题

·42·

USACO 教程 允许将小数表示的物品放入背包中的是小数背包问题。举例来说，如果物品是原油、飞机燃料、煤油而你的 背包是一只水桶，取 0.473 升的原油，0,263 升的飞机燃料和 0,264 升的煤油就是有意义的。这是形式最简单的要 解决的背包问题。 ●整数背包问题 整数背包问题中，只有完整的物品能放入背包里。此形式的一个例子就是：部分的曲子不允许放入包中。 ●多重背包问题 在多重背包问题中，需被填充的背包多于一个。如果允许有小数的物品放入，也就等于有一个大的背包，其 容量相当于所有可用背包的和。因此，此术语只用来指多重整数背包的情况。 小数背包问题 小数背包问题是三者中最简单的，其贪婪解法如下： ●找到“值密度” 物品值/尺寸）最大的物品 （ ●如果总容量仍就超过物品的可利用率，把所有满足条件的物品放入背包中，然后反复执行。 ●如果总容量少于物品的可利用率，尽可能多的使用可用空间，然后终止。 ●由于这个算法必须先按照值密度把物品分类，然后以降序将它们放入背包，直至容量用完，该算法以 N l og N 级运行。通常简单些的方法不是将它们分类，而是不停地找每次不用的最大值密度，这种算法的时间复杂 度是 O(N 2) 。 注意：对于这类问题，因为你可以做一个微小的变换使得所有的物品尺寸大小为一，且原始尺寸大小和可利 用率（当然用原始尺寸大小除值）的乘积就是总容量，同时有尺寸和可利用率是很少见的。 延伸：在这种情况下，物品的值和可利用率可以是实数。用这种算法处理有小数的尺寸大小也不是问题。 整数背包问题 这个问题有点难度，但是如果背包足够小，使用动态规划，它还是可解的。 ●依据背包大小的最大值设计动态的程序。 ●刷新用来表示大小为 S 的物品的数组，颠倒其次序，看将当前物品放入大小为 K 的背包中所产生的集合是 否比当前最好的大小为 K+S 的背包更符合条件。 ●这个算法运行 K*N 次，其中 K 是背包的大小，N 是物品的可利用率义之和。 ●如果背包太大了以至于无法分配此数组，递归下降是一种选择，即这个问题是 NP 完全的（给定 I 上的一 个语言 L，如果有一架非确定图灵机 M 和一个多项式 P(n)，对任何 I 上的长度为 n 的串 w，M 都可以在 P(n)步 内确定是否接受 w，则称 L 是非确定图灵机下多项式时间复杂性问题，简记为 NP 问题/语言。若 L 是属于 NP 的，且对 NP 中的每一个语言 L'，都存在一个从 L'至 L 的多项式时间转化，我们说 L 是 NP 完整的。--译者） 。当 然，递归下降在以小的物品填充的大背包情况下可以运行相当长的一段时间。 延伸： ●小数的值不是问题；数组可以用实数数组来代替整数数组。小数的可利用率并不影响什么，在没有大量损 失的条件下，缩短数字（如果你有 3,5 个物品，你可以仅用 3） 。 ●小数的尺寸是个讨厌的东西，它使得问题递归下降。 ●如果尺寸都相同，问题就能贪婪地解开，在下降的值排序中选择物品，直到背包满为止。 ●如果值都是 1.0，同样地使用贪心法，在上升的尺寸大小排序中选择物品，直到背包满为止。 多重背包问题 对于任何大小的多重背包，状态空间太大了以至于无法使用从整数背包算法中来的 DP 解法。于是递归下降 是解决这个问题的方法。 延伸： ●用递归下降，通常扩展就简单了。小数的尺寸和值就不是问题了，同样地值的计算功能也不是问题。 ·43·

USACO 教程 ●如果值都是同一个，那么如果能被放入所有背包中的物品的最大值是 n，则存在使用 n 个最小物品的解法。 它能大大减少查找时间。 示例问题 分数膨胀[1998 USACO National Championship] 你正试图设计一个有最高分数(<10,000)的比赛。 已知比赛长度， 一组问题， 问题的长度以及每个问题的分值， 计算满足长度约束的最高分数的比赛。 分析：这是一个整数背包问题，比赛是背包，尺寸是问题的长度，值是分数值。背包（比赛）尺寸的限制是 其足够小使得解法在存储器中运行。 篱笆栏[1999 USACO Spring Open] 农场主约翰准备在他的领地建一圈篱笆。他已装好了柱子，所以他知道所要的围栏长度。当地的木材店有各 种长度的木板（至多 50 个） 。已知木材店木板的长度，约翰要的围栏长度，计算约翰建篱笆所用的围栏最大值。 分析：这是个多重背包问题，木材店的木板是背包，物品是约翰用的围栏。物品的尺寸就是长度，值是一。 由于值都是一，如果存在用任意 K 个围栏的解法，则有用 K 个最小围栏的解法。 装满你的油箱 你在 Beaver 郡中部一百英里有一个加油站的城市中，想将你的油箱装满好能到达 Rita Blanca。幸运地是， 这个小镇有两三个加油站，但它们的油都好像要用光了。已知每个加油站的油价，每个加油站的油量，计算为了 花最少的钱，应该从每个加油站买多少汽油。 分析：这是一个小数背包问题，背包是油箱，物品是汽油。

Section 3.3

Eulerian Tour 欧拉通路
by 多维数组

USACO 教程 更加正式的说，寻找图的欧拉回路的方法是选取一个起点，并对它进行递归，递归的步骤为： ? 选取一个起点并在此结点上，按以下步骤递归： o 若此结点无邻结点，则添加该结点到回路中并退出。 o 若此结点有邻结点，则生成一个邻结点表并对表中的结点进行操作（遍历一个点，删除一个点） 直到列表为空。最后将处理的结点加入回路中。 ? 对表中结点的操作为：删去当前处理的结点（指的是当前递归下的结点）与表中的结点相连的边，然后 对这个结点（指表中的结点，我觉得好难表述，建议直接看伪代码......）进行递归。 以下是伪代码： # circuit is a global array find_euler_circuit circuitpos = 0 find_circuit(node 1) # nextnode and visited is a local array # the path will be found in reverse order find_circuit(node i) if node i has no neighbors then circuit(circuitpos) = node i circuitpos = circuitpos + 1 else while (node i has neighbors) pick a random neighbor node j of node i delete_edges (node j, node i) find_circuit (node j) circuit(circuitpos) = node i circuitpos = circuitpos + 1 寻找欧拉通路的方法是先找到一个含有奇数度的节点， 然后以它为参数调用 find_circuit。 如果你用邻接表存储图， 这两个算法的时间复杂度均为 O(m+n)，其中 m 为边的个数、n 为结点个数。若图非常的大，则很容易栈溢出。 所以你应该自己建栈。

·45·

USACO 教程

Stack: Location: 1 Circuit:

Stack: 1 Location: 4 Circuit:

Stack: 1 4 Location: 2 Circuit:

Stack: 1 4 2 Location: 5 Circuit:

·46·

USACO 教程

Stack: 1 4 2 5 Location: 1 Circuit:

Stack: 1 4 2 Location: 5 Circuit: 1

Stack: 1 4 2 5 Location: 6 Circuit: 1

Stack: 1 4 2 5 6 Location: 2 Circuit: 1

·47·

USACO 教程

Stack: 1 4 2 5 6 2 Location: 7 Circuit: 1

Stack: 1 4 2 5 6 2 7 Location: 3 Circuit: 1

Stack: 1 4 2 5 6 2 7 3 Location: 4 Circuit: 1

Stack: 1 4 2 5 6 2 7 3 4 Location: 6 Circuit: 1

·48·

USACO 教程

Stack: 1 4 2 5 6 2 7 3 4 6 Location: 7 Circuit: 1

Stack: 1 4 2 5 6 2 7 3 4 6 7 Location: 5 Circuit: 1

Stack: 1 4 2 5 6 2 7 3 4 6 Location: 7 Circuit: 1 5

Stack: 1 4 2 5 6 2 7 3 4 Location: 6 Circuit: 1 5 7

·49·

USACO 教程

Stack: 1 4 2 5 6 2 7 3 Location: 4 Circuit: 1 5 7 6

Stack: 1 4 2 5 6 2 7 Location: 3 Circuit: 1 5 7 6 4

Stack: 1 4 2 5 6 2 Location: 7 Circuit: 1 5 7 6 4 3

Stack: 1 4 2 5 6 Location: 2 Circuit: 1 5 7 6 4 3 7

·50·

USACO 教程

Stack: 1 4 2 5 Location: 6 Circuit: 1 5 7 6 4 3 7 2

Stack: 1 4 2 Location: 5 Circuit: 1 5 7 6 4 3 7 2 6

Stack: 1 4 Location: 2 Circuit: 1 5 7 6 4 3 7 2 6 5

Stack: 1 Location: 4 Circuit: 1 5 7 6 4 3 7 2 6 5 2

·51·

USACO 教程

Stack: Location: 1 Circuit: 1 5 7 6 4 3 7 2 6 5 2 4

Stack: Location: Circuit: 1 5 7 6 4 3 7 2 6 5 2 4 1

·52·

USACO 教程 The sequence corresponding to the Eulerian circuit is the sequence of N-1 cows of the first node in the circuit, followed by cows corresponding to the color of the edge.

Section 3.4

Computational Geometry 计算几何

z 分量为 0 时，上面式子就化为 2 维的两向量叉积了。结果只有 z 分量。 即： | Ux Uy | | Vx Vy | Ux*Vy-Uy*Vx （注意！二维的叉积较为猥琐。 。其实叉积最早就是定义在三维空间内的，当 z=0 时的特殊情形才是二维向量积。 “二维向量”表达式求出的是一个超出平面的向量。 。这个向量的方向我们不关心，但有时又要利用它。。 。（例如 求多边形面积）故上式不甚严格） 叉积有 3 个特点： ? 两个向量的叉积是一个与这两个向量同时垂直的向量。 ? 叉积的大小等于下面 3 个量的乘积: o u 的大小 o v 的大小 o u,v 夹角的正弦。 当然与 u,v 同时垂直的向量有两个方向，叉积的方向取决于 u 在 v 的右边还是在 v 的左边。

USACO 教程 点积的值由以下三个值确定： ? u 的大小 ? v 的大小 ? u,v 夹角的余弦。 在 u,v 非零的前提下，点积如果为负，则 u,v 形成的角大于 90 度；如果为零，那么 u,v 垂直；如果为正，那么 u, v 形成的角为锐角。 反正切 反正切函数对于一个给定的正切值，返回一个在-pi/2 到 pi/2 之间的角（即-90 度至+90 度） 中另外有一个函数 。C atan2，给出 y 分量和 x 分量（注意顺序！，计算向量与 x 正半轴的夹角，在-pi 到 pi 之间。它的优点就是不需担 ） 心被 0 除，也不需为了处理 x 为负的情况而写代码修改角。atan2 函数几乎比普通的 atan 函数更简单，因为只需 调用一次。 全面考虑问题 这些几何问题大多都产生很多特殊情况。注意这些特殊情况并且要保证自己的程序能处理所有的情况。 浮点运算也会带来新问题。浮点运算很难精确，因为注意：计算机只能计算有限的精度。特别地，要通过判断两 个值的差是否在一个很小的范围内来判断是否相等。 计算几何算法 这里是一些能帮助你计算几何问题的东西。 三角形面积 为了计算由点(A,B,C)构成的三角形的面积，先选取一个顶点（例如 A） ，再向剩余两个顶点作向量（令 u=b-a, v =c-a） 。三角形(A,B,C)的面积即为 u,v 叉积长度的一半。

USACO 教程 点 P 到直线 AB 的距离也可以由叉积给出，准确的说,d(P,AB) = |(P - A) x (B - A)| / | B - A| 。 点 P 到由点 A,B 和 C 确定的平面的距离，令 n = (B - A) x (C - A)，那么 d(P,ABC) = (P-A) · n / |n|。 点在直线上 如果点到直线的距离是 0，那么点在直线上。 点都在直线的同侧 只讲两个点的情况。如果要确定点 C 和 D 是否在直线 AB 同侧，计算(B - A) x (C - A)和(B - A) x (D - A) 的 z 分量。如果同号（或如果积为正） ，那么点 C,D 在直线 AB 同侧。 点在线段上 为了求出点 C 是否在线段 AB 上，先判断点 C 是否在直线 AB 上，再判断线段 AB 的长度是否等于线段 AC 长度 与线段 BC 长度之和。 点在三角形内 要确定点 A 是否在三角形内，首先选择一个三角形内部的点 B(重心就很不错)。接下来，判断点 A,B 是否都在三 边所在的三条直线的同侧。

USACO 教程 两条直线相交 平面内两条直线相交当且仅当直线不平行。 空间内，两直线 AB,CD 相交则 AB,CD 不平行，且点 A,B,C,D 共面。 两条线段相交 平面内，两条线段相交当且仅当 A,B 在直线 CD 异侧且 C,D 在直线 AB 异侧。

·56·

USACO 教程 这个方法也可以扩展到三维（或更高） ，但此时应相交于面（再判断） ，不是在点上或边上。

USACO 教程 给出一组直线所确定的多边形，判断多边形是否是简单的（任意两条不相邻的线段不会相交）和凸的.

Section 4.1 Optimization 最优化

USACO 教程 而这个程序的运行时间为 4609.81 秒。 评价：这只是勉强可以算是优化。虽然这避免了很多不必要的计算，但在一棵如此巨大的搜索树中确实不能起到 太大作用。 Observation #2 出现负数显然是愚蠢的，不要让它们出现在数列中。 （证明过程略...） 现在新的运行时间为 387.34 秒。 出现 0 甚至更愚蠢。 （证明过程略...） 新的运行时间：43.24 秒。 评价：两个简单的操作减少了 100 倍数量级地运算时间，并且它们的代码非常容易写，这非常好地体现了优秀的 优化。 Observation #3 最优解显然要小于前面出现过的最大值。 记录最大值， 当搜索结点超过最大值时， 即使得到了解也不会是最优解， 所以果断退出。 运行时间：0.15 秒。 增加数据规模 目前程序很快，我们应该增加数据规模了。新的数据中幂不大于 300，运行时间是 93.21 秒。 注意 4 为什么不使用可变下界搜索呢？结点的增长随着层数增长，所以结点的质量越来越小。 运行时间: 93.05 秒。 评价：既然这样,从数据看这是一个不强的优化(慢慢会好起来)。它使程序代码产生了很大的改变，出错的机会增 加了，还没有带来任何好处。这令我们有点惊讶，它一向有很大作用。 注意 5 最近的操作必须使用 next-to-last 数。如果不用，生成它干什么?（这句话是 The most recent operation must use the next-to-last number created. If it didn't, why bother generating that number， 我翻译不通） (现在就呈现出可 变下界深度优先搜索算法)。 [next-to-last 意为倒数第二的] 运行时间: 7.47 秒 。 注意 6 不要复制已有的数。 运行时间:：3.40 秒 检查 这样, 除了可变下深度优先搜索以外，只有“Don't Do Anything Stupid”这一原则被体现了，执行时间减少了约 842,510 倍。这是好的，但也许可以再提高。 增加数据规模 新的数据中幂不大于 500，运行时间是 206.71 秒。 注意 7 如果一个数列的前缀没有得到解，在后面加什么数也没有用。例如，如果 1 2 4 8 7 得不到解，就不用尝试 1 2 4 8 16 7 了。 运行时间： 53.70 秒 注意 8 如果选择了 i,数列中最大的数是 j,而且 i+j 小于下一个需要的数,那就不要选择 i。 运行时间: 44.52 秒。 注意 9 如果一个数列生成 x (x 不是目标)用了 j 项，而且存在另外一个数列用了少于 j 项，我们应该用这个短的数列把 它替换掉，获得一个“更好的”数列，这是最佳的。 错误! 第一个反例: 10,127.用这种方法得到的解是 17 项，但是存在一个 16 项的方法。 这就是优化的风险：有时候，会得到错误结论。确保你不会掉入陷阱. ·59·

USACO 教程 总结 8 个优化使运行时间缩小 400 万倍。 可以使不大于 500 的数据在 44.52 秒内出解。 有的程序可以在 640k 内存限制 的情况下 1.91 秒内出解(无限制时 0.85 秒)。看看你的程序有多快。

Section 4.2

Network Flow 网络流

6 # 找到从源到汇的最大的容量的路径 7 # 用修改过的 Dijkstra 算法 (在 Chapter 4 的 ditches 就要用 Bellman-Ford 了) 8 FOR 所有的顶点 i 9 前驱(i) = nil 10 flow(i) = 0 11 visited(i) = FALSE 12 13 14 flow(源点) = 无限大 WHILE (TRUE) 最大流 = 0 ·60·

USACO 教程 15 16 17 18 19 20 21 22 23 24 24 25 26 27 28 29 30 31 32 33 最大流节点 = nil # 找到最大容量的未访问节点 FOR 每个顶点 i IF ((flow(i)>最大流) AND (NOT visited(i))) 最大流 = flow(i) 最大流节点 = i IF (最大流节点 = Nil) 退出内层 While 循环 IF (最大流节点 = 汇点) 退出内层 While 循环 visited(最大流节点) = TRUE # 调整相邻节点 FOR 最大流节点的所有相邻节点 i IF (flow(i)<min(最大流, 最大流节点到 i 的容量)) 前驱(i) = 最大流节点 flow(i) = min(最大流, 最大流节点到 i 的容量)) IF (最大流节点 = Nil) # 没有路径 退出外层 While 循环 路径容量 = flow(汇点) 总流 = 总流 + 路径容量

# 把那个流加到网络里 适当调整容量 35 当前节点 = 汇点 # 对于增广路径上每条弧, 前驱(当前节点), 当前节点 36 WHILE (当前节点不为源点) 38 下一个节点 = 前驱(当前节点) 39 下一个节点到当前节点的容量减去路径容量 40 当前节点到下一个节点的容量加上路径容量 41 当前节点 = 下个节点 这个方法的运行时间为 O(FM)， 是最大流 M 是弧的数目. 运行时间通常更短, 因为算法每次总是尽可能大的提 F 升流。 为了确定每条弧上的流，比较开始的容量和最后的容量。如果最后的容量变少了，区别就在于通过这条弧的流。 当有回路的时候，这个算法可能产生死循环。 实例 考虑下面那个网络，源点为 5，汇点为 2

·61·

USACO 教程

·62·

USACO 教程

·63·

USACO 教程 您有一个通过网线连接的计算机网络。数据可能从任何一个方向流经网线。不幸的是，一台网络里的机器染上病 毒，您需要从中心服务器隔离这台机器来防止病毒传染。给出关闭一对机器连接的代价，计算控制病毒传染到服 务器的最小的代价。 这就是最小割问题。 伐木工人的计划 不同种类的树需要雇佣拥有不同的技巧的伐木工人来正确的砍树。不管哪种树或伐木工人，砍一棵树需要 30 分 钟。给出伐木工人的信息，和哪种树需要哪位才能正确的砍倒，以及树的信息，计算在半小时内砍倒的最多的树 的数目。对于每一个伐木工人，都有一种对应的他（她）能砍倒的树。所以，这个问题能用最大匹配算法来解决。 牛的电话联系（USACO 锦标赛 1996） 给出特定区域里的一组电脑，和电脑之间连着的网线，要想阻止给定两台电脑的联系 最少需要关掉多少网络中 的电脑。假定两台给出的电脑没有关掉。 这相当于最少节点割的问题。两台给出的电脑标上源点和汇点。电缆是双向的。把每个点拆成流入点和流出点， 这样我们就能够用 1 限制任何一台电脑。现在，网络里的最大流就相当于节点最小割了。 为了具体确定割，反复删除节点，直到您找到一个能降低网络流量的节点。 科学展览审定 一个科学展览由 N 个学科，和 M 个裁判。每个裁判愿意审定某些学科，每个学科需要一些裁判。每个裁判只能 够审定在给出的科学展览中的一个学科。您在这些条件下总共能分配给多少裁判任务？ 这是一个很类似最大匹配的问题， 除了每个学科需要可能多于一个裁判。 解决这个问题的最简单的方法是把从科 目到汇点的弧的容量赋予需要裁判数的值。 石油管道设计 给出阿拉斯加管道线的设计（每条管道的容量，和管道如何连接） ，以及每个交点的位置，您想提高朱诺和费尔 班柯斯之间最大流量，但您的钱只够添加一条容量为 X 的管道。此外，管道只能 10 英里长。这条管道添加在哪 两个交点能最大程度的提高流量？ 要解决这个问题，对于距离 10 英里以内的每一对交点，添加一条管道，再计算从朱诺到费尔班柯斯的流量增加 值。每一个子问题都是最大流。

Section 4.3

Big Number 高精度

·64·

USACO 教程 对于这种数据结构，想法完成各种操作需要我们回想一下怎样手动完成这些操作。最主要的问题是溢出，一定切 记检查确保所有的加法和乘法什么的不会造成算术上溢，否则整个操作只会得到错误的结果（Pascal 中直接程序 报错哦，亲） 方便起见，这里说明的算法都将基于数组进行说明，所以如果一个数字是 a0, a 1, ..., ak，那么对于所有的 i > k, ai = 0。对于链表，相关的算法会比较复杂一点（译者是 SB：别被吓到了，难不到哪里去） 。附加说明一下， 用于存储结果的数组每一项一般来说都应将被初始化为零。 数据的比较 要比较两个数据 a0, a1, ..., an 和 b0, b1, ..., bk 以及它们的符号位（用于标记正数和负数）signA（SA） 、signB （SB）的步骤如下： # 标注符号位 # sizeA = A 的数位个数 # signA = A 的符号 # (0 => 正, 1 => 负) 1 if (signA < signB) 2 3 4 5 6 7 8 9 10 11 12 return A 要小一些 else if (signA > signB) return A 要大一些 else for i = max(sizeA,sizeB) to 0 if (a(i) > b(i)) if (signA = 0) return A 要大一些 else return A 要小一些 return A = B

13 14 15 16 17 18 19 20 21 22 23 24

USACO 教程 "|B| > |A|; can't handle this") absolute_add(bignum A, bignum B, bignum C) carry = 0 for pos = 0 to max(sizeA,sizeB) C(pos) = A(pos)+B(pos)+carry carry = C(pos) / base C(pos) = C(pos) mod base if carry != 0 CHECK FOR OVERFLOW C(max(sizeA,sizeB)+1) = carry sizeC = max(sizeA,sizeB)+1 else sizeC = max(sizeA, sizeB)

25 add (bignum A, bignum B, bignum C) 26 if signA == signB 27 absolution_add(A,B) 28 signC = signA 29 else 30 if (Compare(A,B) = A is larger) then 31 absolute_subtract(A,B) 32 signC = signA 33 else 34 absolute_subtract(B,A) 35 signC = signB 减法 有了刚才的加法做铺垫，减法就很简单了。要计算 A - B, 反转 B 的符号位再加上 A 和 B. 与普通正整数相乘 确保在结果不超过最大表示范围的情况下进行和普通正整数的乘法，可以用和在纸上手动计算的类似方法。 1 if (s < 0) 2 signB = 1 - signA 3 s = -s 4 else 5 signB = signA 6 carry = 0 7 8 9 10 11 12 13 14 15 16 17 for pos = 0 to sizeA（*pos 是数位指针） B(pos) = A(pos) * s + carry carry = B(pos) / base B(pos) = B(pos) mod base pos = sizeA+1 while carry != 0 CHECK OVERFLOW B(pos) = carry mod base carry = carry / base pos = pos + 1 sizeB = pos - 1 ·66·

USACO 教程 高精度乘法 高精度乘法就是多次普通乘法然后在正确的数位相加。 一般来说，用另一个数的各个数位来直接乘，然后加起来（在正确的数位）和我们手算乘法是差不多的方法 1 multiply_and_add(bignum A, int s, int offset, bignum C) 2 carry = 0 3 for pos = 0 to sizeA 4 C(pos+offset) = C(pos+offset) + A(pos) * s + carry 5 carry = C(pos+offset) / base 6 C(pos+offset) = C(pos+offset) mod base 7 pos = sizeA + offset + 1 8 while carry != 0 9 CHECK OVERFLOW 10 C(pos) = C(pos) + carry 11 carry = C(pos) / base 12 C(pos) = C(pos) mod base 13 pos = pos + 1 14 if (sizeC < pos - 1) 15 sizeC = pos - 1 16 multiply(bignum A, bignum B, bignum C) 17 for pos = 0 to sizeB 18 multiply_and_add(A, B(pos), pos, C) 19 signC = (signA + signB) mod 2 大数据被小数据除 和手算没两样。 1 divide_by_scalar (bignum A, int s, bignum C) 2 rem = 0 3 sizeC = 0 4 for pos = sizeA to 0 5 rem = (rem * b) + A(pos) 6 C(pos) = rem / s 7 if C(pos) > 0 and pos > sizeC then 8 sizeC = pos 9 rem = rem mod s # 记得退位 高精度除法 和手算也差不多。。各种细心。。注意如果 b 太大，这个算法会很耗时间 。 。 1 divide_by_bignum (bignum A, bignum B, bignum C) 2 bignum rem = 0 3 for pos = sizeA to 0 4 mult_by_scalar_in_place(rem, b) ·67·

USACO 教程 5 6 7 8 9 10 11 add_scalar_in_place(rem, A(pos)) C(pos) = 0 while (greater(rem, B)) C(pos) = C(pos) + 1 subtract_in_place(rem, B) if C(pos) > 0 and pos > sizeC then sizeC = pos

Section 5.1

Two Dimensional Convex Hull 二维凸包

USACO 教程 可以看出，多边形的顶点必须是给定点集中的点。

·69·

USACO 教程

USACO 教程 1 2 3 4 5 6 7 (midx, midy) = (0, 0) For all points i (midx, midy) = (midx, midy) + (x(i)/npoints, y(i)/npoints) For all points i angle(i) = atan2(y(i) - midy, x(i) - midx) perm(i) = i 把 perm 基于 angle() 排序 # 其中 angle(perm(0)) <= angle(perm(i)) for all i # 开始构造凸包 hull(0) = perm(0) hull(1) = perm(1) hullpos = 2 for 对所有点 p, 根据 perm() 的次序, 除 perm(npoints - 1) 以外 while (hullpos > 1 and zcrossprod(hull(hullpos-2) hull(hullpos-1), hull(hullpos-1) - p) < 0) hullpos = hullpos - 1 hull(hullpos) = p hullpos = hullpos + 1 # 加入最后一个点 p = perm(npoints - 1) while (hullpos > 1 and zcrossprod(hull(hullpos-2) hull(hullpos-1), hull(hullpos-1) - p) < 0) hullpos = hullpos - 1 hullstart = 0 do flag = false if (hullpos - hullstart >= 2 and zcrossprod(p hull(hullpos-1), hull(hullstart) - p) < 0) p = hull(hullpos-1) hullpos = hullpos - 1 flag = true if (hullpos - hullstart >= 2 and zcrossprod(hull(hullstart) - p, hull(hullstart+1) hull(hullstart)) < 0) ·71·

8 9 10 11 12 13 14 15 16

17 18 19 20 21 22 23 24 25 26 27 28 29

USACO 教程 30 31 32 33 34 hullstart = hullstart + 1 flag = true while flag hull(hullpos) = p hullpos = hullpos + 1

·72·

USACO 教程 现在，加入第三个顶点。由于这步操作没有和前两个顶点构成一个大于 180 度的角，我们只需加入这个顶点。

·73·

USACO 教程 加入第六个，第七个，和第八 8 个顶点。这个过程中没有附加的工作。

·74·

USACO 教程 第七个，第八个，和第一个顶点已经完成了，可是第八个，第一个，和第二个顶点构成“右转” ，所以我们必须 删除第一个顶点。

·75·

USACO 教程

Section 5.3 Heuristic Search 启发式搜索

·76·

USACO 教程

USACO 教程 7 3 2---->7 3 2 达到下面的状态所需最小步数是多少?(保证有解) 1 2 3 4 5 6 7 8 _ 估价函数:起始状态到结束状态中所有数的位置的曼哈顿距离之和. 算法:状态空间很小(只有 362,880),A*就很好,不过要保证每个状态只能被访问一次.

·78·