内容发布更新时间 : 2024/6/7 18:47:19星期一 下面是文章的全部内容请认真阅读。

2009 年暑假集训讲义

上海交通大学 马融

2009 年暑假集训讲义

上海交通大学 马融

第一讲

穷举与贪心 ................................................................................................................... 3

集市班车 (Fair Shuttle, USACO 2009 Feb) ............................................................................... 4 翻转棋 (Fliptile, USACO 2007 Nov) .......................................................................................... 5 翻转奶牛 (Face The Right Way, USACO 2007 Mar) ................................................................. 6 第二讲

背包问题 ....................................................................................................................... 7

分数膨胀 (Score Inflation, USACO 3.1) .................................................................................... 8 货币系统 (Money Systems, USACO 2.3) .................................................................................. 9 奶牛博览会 (Cow Exhibition, USACO 2003 Nov) ................................................................... 10 太空电梯 (Space Elevator, USACO 2005 Mar) ....................................................................... 11 牛奶量取 (Milk Measuring, USACO 5.3) ................................................................................ 12 第三讲

动态规划选讲 ............................................................................................................. 13

抓苹果 (Apple Catching, USACO 2004 Nov) .......................................................................... 15 最廉回文 (Cheapest Palindrome, USACO 2007 Open) .......................................................... 17 麦香牛块 (Beef McNuggets, USACO 4.1) .............................................................................. 19 道路重建 (Rebuilding Roads, USACO Feb 2002).................................................................... 20 第四讲

最小生成树问题 ......................................................................................................... 22

建造道路 (Building Roads, USACO 2007 Dec) ....................................................................... 23 安慰奶牛 (Cheering up the Cows, USACO 2008 Nov) ........................................................... 24 地震 (Earthquake, USACO 2001 Open) .................................................................................. 26 第五讲

最短路径问题 ............................................................................................................. 28

道路翻新 (Revamping Trails, USACO 2009 Feb) .................................................................... 29 道路障碍 (Roadblocks, USACO 2006 Nov) ............................................................................ 31 奶牛慢跑 (Cow Jogging, USACO 2008 Mar) .......................................................................... 33 第六讲

广度优先遍历 ............................................................................................................. 35

青铜莲花池 (Bronze Lilypad Pond, USACO 2007 Feb) ........................................................... 36 白银莲花池 (Silver Lilypad Pond, USACO 2007 Feb) ............................................................. 37 黄金莲花池 (Lilypad Pond, USACO 2007 Feb) ....................................................................... 39 第七讲

USACO 竞赛试题选讲 ................................................................................................ 41

哞哞大学之奖学金 (Moo University - Financial Aid, USACO 2004 Mar) .............................. 42 哞哞大学之校队选拔 (Moo University - Team Tryouts, USACO 2004 Mar) ......................... 44 哞哞大学之匹萨预定 (Moo University - Emergency Pizza Order, USACO 2004 Mar) .......... 46 第八讲

USACO 竞赛试题选讲（续） .................................................................................... 48

黄金平衡 (USACO 2007 Mar) ................................................................................................ 49 奶牛排名 (Ranking the Cows, USACO 2007 Mar) .................................................................. 50 奶牛交通 (Cow Traffic, USACO 2007 Mar)............................................................................. 51 校庆聚会 (Ural 1039)............................................................................................................. 52 第九讲

线段树 ......................................................................................................................... 54

1 / 55

2009 年暑假集训讲义

上海交通大

USACO 题目中常见的单词：

pasture barn trail grazing location intersection FJ Bessie hay hoof 牧场 牛棚 小路 放牧地点 十字路口 农夫约翰（Farmer John）的缩写 贝西，一头非常聪明的母牛 干草 牛蹄（复数 hooves）

2 / 55

上海交通大学 马融

第一讲 穷举与贪心

3 / 55

2009 年暑假集训讲义

上海交通大学 马融

集市班车 (Fair Shuttle, USACO 2009 Feb)

逛逛集市，兑兑奖品，看看节目对农夫约翰来说不算什么，可是他的奶牛们非常缺乏锻 炼——如果要逛完一整天的集市，他们一定会筋疲力尽的。所以为了让奶牛们也能愉快地逛 集市，约翰准备让奶牛们在集市上以车代步。

但 是， 约翰 木有 钱， 他租来 的班 车只 能在 集市上 沿 直线 跑一 次， 而且 只能停 靠

N (1 ≤ N ≤ 20000)个地点（所有地点都以1到N之间的一个数字来表示）。现在奶牛们分成

K (1 ≤ K ≤ 50000)个小组，第 i 组有Mi (1 ≤ Mi≤ N)头奶牛，他们希望从Si跑到Ti (1 ≤ Si<

Ti≤ N)。

由于班车容量有限，可能载不下所有想乘车的奶牛们，此时也允许小组里的一部分奶牛

分开乘坐班车。约翰经过调查得知班车的容量是C (1 ≤ C ≤ 100)，请你帮助约翰计划一个尽

可能满足更多奶牛愿望的方案。

输入格式

??第一行：包括三个整数：K，N和C，彼此用空格隔开。

??第二行到K + 1行：在第i + 1行，将会告诉你第i组奶牛的信息：Si，Ei和Mi，彼此用空

格隔开。

输出格式

??第一行：可以坐班车的奶牛的最大头数

样例

shuttle.in 8 15 3 1 5 2 13 14 1 5 8 3 8 14 2 14 15 1 9 12 1 12 15 2 4 6 1

shuttle.out 10 （班车可以把2头奶牛从1送到5，3头奶牛从 5送到8，2头奶牛从8送到14，1头奶牛从9送 到12，1头奶牛从13送到14，1头奶牛从14送 到15） 解题思路

贪心，在任何时刻总是带最早下车的奶牛，证明略。

4 / 55

2009 年暑假集训讲义

上海交通大学 马融

翻转棋 (Fliptile, USACO 2007 Nov)

农夫约翰知道，聪明的奶牛可以产更多的牛奶。他为奶牛设计了一种智力游戏，名叫翻 转棋。翻转棋可以分成M × N (1 ≤ M, N ≤ 15)个格子，每个格子有两种颜色，一面是黑的， 一面是白的。

一旦翻转某个格子，这个格子的颜色就会颠倒。如果把所有的格子都翻成白的，就算奶 牛赢了。然而，奶牛的蹄子很大，一旦它们打算翻转某个格子，这个格子附近（即和这个格 子有公共边）的格子也会被翻转。一直翻来翻去也很无聊，奶牛们想最小化必须翻动的次数。

请帮助奶牛确定翻动的最少次数和具体的翻法。如果最小解有多个，则输出在字典序意 义下最小的那个，如果不可能完成任务，则只要输出一行单词：IMPOSSOBLE。

输入格式

??第一行：两个用空格分开的整数：M和N

??第二行到M + 1行：第i + 1行从左至右依次描述了棋盘第i行的的颜色，共记N个用空格

分开的整数，1 代表黑色，0 代表白色。

输出格式

??第一行到第M行：每行输出N个用空格分开的整数，表示在这个格子上翻转的次数。

样例

fliptile.in 4 4 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1

fliptile.out 0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 （另外还有一个解是 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 但是这个解在字典序意义下没有样例来得 小） 解题思路

如果第一行的翻法固定了，其余行的翻法是固定的，所以只要穷举第一行的翻法就可以了。

5 / 55