usaco合集usaco合集usaco合集资源-CSDN文库

共5个文件

chm：2个

rar：2个

pdf：1个

usaco

合集usaco

5星 · 超过95%的资源需积分: 48 124 浏览量 2010-04-06 23:21:02 上传评论收藏 6.26MB RAR 举报

资源推荐

资源详情

资源评论

收起资源包目录

新建文件夹.rar （5个子文件）

USACO题解%2B程序.rar 1.94MB

USACO讲义合集.pdf 927KB

USACO译题.chm 1.13MB

USACO+1-5.chm 702KB

USACO全部测试数据.rar 2.19MB

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

2009 年暑假集训讲义上海交通大学马融

USACO 题目中常见的单词：

pasture

牧场

barn

牛棚

trail

小路

grazing location

放牧地点

intersection

十字路口

农夫约翰（Farmer John）的缩写

Bessie

贝西，一头非常聪明的母牛

hay

干草

hoof

牛蹄（复数 hooves）

2009 年暑假集训讲义上海交通大学马融

第一讲穷举与贪心

2009 年暑假集训讲义上海交通大学马融

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

逛逛集市，兑兑奖品，看看节目对农夫约翰来说不算什么，可是他的奶牛们非常缺乏锻

炼——如果要逛完一整天的集市，他们一定会筋疲力尽的。所以为了让奶牛们也能愉快地逛

集市，约翰准备让奶牛们在集市上以车代步。

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

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

K (1 K 50000)个小组，第 i 组有M

(1 M

N)头奶牛，他们希望从S

跑到T

(1 S

N)。

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

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

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

输入格式

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

 第二行到K + 1行：在第i + 1行，将会告诉你第i组奶牛的信息：S

，E

和M

，彼此用空

格隔开。

输出格式

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

样例

shuttle.in

shuttle.out

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

（班车可以把2头奶牛从1送到5，3头奶牛从

5送到8，2头奶牛从8送到14，1头奶牛从9送

到12，1头奶牛从13送到14，1头奶牛从14送

到15）

解题思路

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

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

fliptile.out

4 4

1 0 0 1

0 1 1 0

1 0 0 1

0 0 0 0

1 0 0 1

0 0 0 0

（另外还有一个解是

0 1 1 0

0 0 0 0

0 1 1 0

但是这个解在字典序意义下没有样例来得

小）

解题思路

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

评论收藏

内容反馈

yasaka

2018-06-03

不错，就是不太新
wang648979

2014-07-26

全面，资源好
superjx2318

2012-08-19

还是挺全的，不过不是很新
silverelf

2011-10-24

资源很好，很全面，谢谢！
柴西卡夫卡

2011-09-16

总结的挺全的还，不错

前往

页

zj3782

粉丝: 6
资源: 18

usaco 合集usaco 合集usaco 合集

最新资源

usaco 合集usaco 合集usaco 合集

USACO讲义合集

USACO2006数据资料合集

USACO英汉对照题目

usaco合集+测试数据+解题

USACO总结

USACO全部测试数据.zip

usaco教程中文版

uasco_fc解题

USACO训练测试数据

USACO题集及答案

USACO.rar_usaco

04-usaco

usaco_beads

usaco_solutions：usaco解决方案

usaco_creat

USACO题解整理版

USACO经典试题配数据

usaco 2010－2011

usaco心得及总结

Usaco总结&题解

USACO翻译及题解

USACO教程（帮助你实战）

USACO答案及详解

USACO全部测试数据

usaco—Friday

usaco的数据

usaco_bigbrn

usaco 全部题解

milk3 usaco题目

usaco_world_C++_

最新资源