当前位置:首页 >> 学科竞赛 >>

USACO试题精选(第一辑)


USACO 试题精选 第一辑
第1题 第2题 第3题 第4题 第5题 第6题 第7题 第8题 第9题 第 10 题 第 11 题 第 12 题 第 13 题 第 14 题 第 15 题 第 16 题 第 17 题 第 18 题 第 19 题 第 20 题 第 21 题 第 22 题 第 23 题 第 24 题 第 25 题 第 26 题 第 27 题 第 28 题 第

29 题 第 30 题 第 31 题 第 32 题 第 33 题 第 34 题 第 35 题 第 36 题 第 37 题 第 38 题 第 39 题 第 40 题 第 41 题 利润 (Profits, USACO 2011 Jan) ........................................................................... 3 购买饲料二 (Buying Feed II, USACO 2010 Jan) ................................................... 4 奶牛杂技 (Cow Acrobats, USACO 2006 Nov)....................................................... 5 抓苹果 (Apple Catching, USACO 2004 Nov) ........................................................ 6 抢购干草 (Hay For Sale, USACO 2008 Dec) ......................................................... 7 建造栅栏 (Building A Fence, USACO 2008 Oct) ................................................... 8 建造道路 (Building Roads, USACO 2007 Dec) ..................................................... 9 青铜莲花池 (Bronze Lilypad Pond, USACO 2007 Feb) ....................................... 10 滑雪课程 (Ski Lessons, USACO 2009 Open) ...................................................... 11 奶牛飞盘队 (Cow Frisbee Team, USACO 2009 Mar) ......................................... 12 奶牛博览会 (Cow Exhibition, USACO 2003 Fall)................................................ 13 最近回文 (Cheapest Palindrome, USACO 2007 Open) ...................................... 14 安慰奶牛 (Cheering up the Cows, USACO 2008 Nov) ....................................... 15 玉米迷宫 (Corn Maze, USACO 2011 Open) ....................................................... 16 奶牛集会 (MooFest, USACO 2004 Open) .......................................................... 17 奶牛文字 (Cowlphabet, USACO 2011 Feb) ........................................................ 18 奶牛跨栏 (Cow Hurdles, USACO 2007 Nov) ...................................................... 19 工作安排 (Work Scheduling, USACO 2009 Open) ............................................. 20 手机网络 (Cell Phone Network, USACO 2008 Jan) ............................................ 21 提交作业 (Turning in Homework, USACO 2004 Open)...................................... 22 滑雪缆车 (Ski Lift, USACO 2006 Mar) ................................................................ 23 派发巧克力 (Chocolate Giving, USACO 2010 Feb) ............................................ 24 赞助学费 (Financial Aid, USACO 2004 Mar) ...................................................... 25 白银莲花池 (Silver Lilypad Pond, USACO 2007 Feb) ......................................... 26 地震 (Earthquake, USACO 2001 Open) .............................................................. 27 股票市场 (Stock Market, USACO 2009 Feb) ...................................................... 28 奶牛赛车 (Cow Cycling, USACO Feb 2002) ........................................................ 29 奶牛观光 (Sightseeing Cows, USACO 2007 Dec) ............................................... 30 道路重建 (Rebuilding Roads, USACO Feb 2002)................................................ 31 奶牛接力 (Cow Relays, USACO 2007 Nov) ......................................................... 32 猜数游戏 (Haybale Guessing, USACO 2008 Jan) ............................................... 33 混乱奶牛 (Mixed Up Cows, USACO 2008 Nov) .................................................. 34 修剪草坪 (Mowing the Lawn, USACO 2011 Open) ........................................... 35 道路翻新 (Revamping Trails, USACO 2009 Feb) ................................................ 36 安排牧场 (Corn Fields, USACO 2006 Nov) ......................................................... 37 叠积木 (Cube Stacking, USACO 2004 Open) ...................................................... 38 奶牛抗议 (Generic Cow Protests, USACO 2011 Feb) ......................................... 39 洞穴奶牛第一话 (Cave Cow 1, USACO 2004 Open) .......................................... 40 打扫食槽 (Cleaning Up, USACO 2009 Mar) ....................................................... 41 购买饲料 (Buying Feed, USACO 2010 Nov) ....................................................... 42 土地并购 (Land Acquisition, USACO 2008 Mar) ................................................ 43

第 42 题 第 43 题 第 44 题 第 45 题 第 46 题 第 47 题 第 48 题 第 49 题 第 50 题

干草塔 (Tower of Hay, USACO 2009 Open)........................................................ 44 明星奶牛 (Popular Cows, USACO 2003 Fall) ...................................................... 45 电子游戏 (Video Game Troubles, USACO 2009 Dec)......................................... 46 产奶比赛 (Milk Team Select, USACO 2006 Mar) ............................................... 47 黄金莲花池 (Lilypad Pond, USACO 2007 Feb) ................................................... 48 逢低吸纳 (BUY LOW, BUY LOWER, USACO Feb 2002) ....................................... 49 焊接 (Soldering, USACO 2011 Open) ................................................................. 50 旅馆 (Hotel, USACO 2008 Feb)........................................................................... 51 道路和航线 (Roads and Planes, USACO 2011 Jan) ............................................ 52

这一辑从 USACO 月赛中选择了质量很高的 50 题, 是用来训练算法设计和实现的极好素 材,如果初学者希望掌握比较扎实的基本功,我建议将这一辑的题目好好研究一下。主要用 到的知识点有: ? 动态规划:区间上的动态规划、背包问题、树上的动态规划、集合上的动态规划、 单调队列优化、斜率优化 ? 数据结构:堆、并查集、树状数组、线段树 ? 图论: Prim 和 Kruskal 算法, Dijkstra 算法及其堆优化实现, Bellman-Ford 算法, Floyd 算法,深度优先遍历,广度优先遍历 ? 算法思想:贪心、枚举、二分、归纳 这大概只是一个很不完整的列表, 希望选手在训练时候不要太依赖于提示, 自己思考更 有乐趣。在题目顺序的编排上,我是按照题目的难度和代码的长度来循序渐进的。翻译的时 候,基本是忠于原文的,但可能修改了个别段落的语句,使得题面描述更加清晰简短,如果 感觉有问题,请参考原文。每道题目的出处已在标题后标出。数据、官方解答、问题原文很 容易从网上查得,在此不做赘述。 做多少题目才能在信息学竞赛上获得好成绩?我也不太确定。 著名数学教育工作者刘培 杰先生曾撰文指出,正常人从初学到精通一项技能需要一万个小时的训练量。飞行员如此, 运动员如此,竞赛选手仍然如此。我询问了一下上海交通大学 ACM-ICPC 代表队的队员和教 练员,基本上每个人都做了 5000 道以上的题目,如果一道题目算一小时的话,至少在大学 本科期间, 他们都训练了 5000 小时左右了。 我猜想, NOIP 要拿好成绩, 100 行的程序写 100 道,应该是要的,NOI 想要拿好成绩,200 行的程序写 200 道,应该也是要的。 接下来我还打算继续挑选 USACO 月赛里的好题目,凑满 50 道就集结成册,希望以后有 时间,连解答一起,写成一本书吧,可能要很久才能完成了,大家请勿期待。

马 融 marong1204@gmail.com

第1题

利润 (Profits, USACO 2011 Jan)

奶牛们开了家新公司,这家公司已经运作了N天,财务报表显示第i天获得的利润为Pi , 有些天的利润可能是个负数。约翰想给奶牛公司写个新闻报道,以吹嘘她们的业绩。于是他 想知道,这家公司在哪一段连续的日子里,利润总和是最大的。

输入格式
? ? 第一行:单个整数N,1 ≤ N ≤ 105 第二行到N + 1行:每行一个整数Pi ,代表第i天的利润,?1000 ≤ Pi ≤ 1000

输出格式
? 第一行:单个整数,表示在某段连续的日子里最大的利润之和

样例
profits.in 7 -3 4 9 -2 -5 8 -3 profits.out 14

(第三天到第六天,一共是4 + 9 ? 2 ? 5 + 8 = 14)

第2题

购买饲料二 (Buying Feed II, USACO 2010 Jan)

约翰在镇上, 沿着公路开车回家, 他的家离起点有E公里。 他顺便准备买K吨饲料回家。 运送饲料是要花油钱的,如果他的车上有X吨饲料,行驶一公里需要X元,行驶D公里就需要 DX元。约翰可以从N家商店购买饲料,所有商店都在公路边上,第i家店距离起点X i公里,饲 料单价为每吨Ci元,库存为Fi 吨。 约翰可以选择在任意商店里购买任意多的饲料, 只要那家店的还有货就可以了。 保证所 有商店的饲料库存之和不会少于K,为了带K吨饲料回家,约翰最少的花费是多少呢? 举个例子,假设有三家商店,情况如下所示: X=1 X=3 X=4 E=5 坐标 1 1 1 库存 1 2 2 单价 如果约翰要买2吨饲料回家,那么他的最好选择是在离家较近的两家商店购买饲料,则 花在路上的钱是1 + 2 = 3,花在商店的钱是2 + 2 = 4,共需要7元。

输入格式
? ? 第一行:三个用空格分开的整数:K,E和N,1 ≤ K, N ≤ 100,1 ≤ E ≤ 350 第二行到N + 1行: + 1行有三个用空格分开的整数一个整数: i, i 和Ci, < X i < E, 第i X F 0 6 1 ≤ Fi ≤ 100,1 ≤ Ci ≤ 10

输出格式
? 第一行:单个整数,表示购买和运送饲料的最小总费用

样例
feed2.in 253 312 412 111 feed2.out 7

第3题

奶牛杂技 (Cow Acrobats, USACO 2006 Nov)

约翰养了N头奶牛,她们打算逃出牧场,去马戏团演出。可奶牛们很快发现她们那笨拙 的蹄子根本无法在钢丝或晃动的秋千上站稳。 她们还尝试过把自己装在大炮里发射出去, 但 可想而知,结局是悲惨的。最终,她们决定练习一种最简单的杂技:叠罗汉——先选一头奶 牛垫在最底下,剩下的牛挨个爬上去,直到N头牛全部叠上去为止。 每头牛都有自己的重量和力量。设奶牛的编号为1到N,编号为i的奶牛的体重为Wi ,力 量为Si。表演杂技的过程中,每头奶牛都会受到来自上方奶牛的压力,这是非常危险的。一 头奶牛的压力指数定义为压在她上面的所有奶牛的总重量与她的力量的差。 奶牛们希望团队 中出现的压力指数越小越好。请告诉奶牛们,她们该怎么计划次序,才能使得团队中最大的 压力指数最小。

输入格式
? ? 第一行:单个整数:N,1 ≤ N ≤ 50000 第二行到N + 1行:每行有两个整数:Wi 和Si,1 ≤ Wi ≤ 10000,1 ≤ Si ≤ 109

输出格式
? 单独一行:表示最大压力指数的最小值

样例
acrobat.in 3 10 3 25 33 acrobat.out 2 (让重量为 10 的奶牛垫底, 她的压力指数为 2 + 3 ? 3 = 2,其余两头牛的压力指数都比 她小)

第4题

抓苹果 (Apple Catching, USACO 2004 Nov)

奶牛喜欢吃苹果。约翰有两棵苹果树,每棵树上都结满了苹果。每一分钟过去,就会有 一只苹果从一棵树上落下。如果正好站在那棵树下,贝西就能接住苹果。贝西在两棵树之间 的移动是瞬间的,但她的运动能力不足,所以只能移动W次。假设贝西可以玩T分钟,帮助 她计算一下最多可以接几个苹果。一开始贝西在第一棵树下。

输入格式
? ? 第一行:两个用空格分开的整数:T和W,1 ≤ T ≤ 1000,1 ≤ W ≤ 30 第二行到第T + 1行:表示在这一分钟里,苹果将从哪棵树上掉落,1 表示第一棵树,2 表示第二棵树

输出格式
? 第一行:表示能抓到的最大苹果数量

样例
bcatch.in 72 2 1 1 2 2 1 1 bcatch.out 6

(贝西可以抓住 6 个苹果:首先待在第一棵 树下得到 2 个,再移动到第二棵树下抓住两 个,再返回第一棵树,抓住最后两个)

第5题

抢购干草 (Hay For Sale, USACO 2008 Dec)

约翰的牧场遭到了严重的虫灾,他的所有干草全被蝗虫吃光了。为了不让奶牛饿肚子, 他赶紧驾着马车跑到老唐的商店去抢购干草。老唐的商店里有H捆干草,每捆的体积为一个 整数,约翰的马车装载的干草总体积不能超过C。请你帮助约翰计算一下,他最多能带回多 少干草?注意,每捆干草是不能拆开带走的。

输入格式
? ? 第一行:两个用空格分开的整数:C和H,1 ≤ C ≤ 50000,1 ≤ H ≤ 5000 第二行到第H + 1行:第i + 1行表示第i捆干草的体积Vi ,1 ≤ Vi ≤ C

输出格式
? 第一行:单个整数,表示可以带回去的不超过C的最大体积

样例
hay4sale.in 73 2 6 5 hay4sale.out 7

(选择购买2和5,正好装满到7)

第6题

建造栅栏 (Building A Fence, USACO 2008 Oct)

勤劳的约翰打算建造一个四边形的栅栏把奶牛围起来。 他有一条很长的木头, 长度为N。 约翰打算在这块木头上挑选三个切口, 把它锯成四段。 锯开的四根木头要能围成一个四边形, 这个四边形要有面积。每段木头的长度要求是正整数。 那么有多少种锯开木头的方法呢?由于要在这根木上锯三刀, 只要其中有一刀不锯在同 一位置,那么这两种锯法就算是不一样的,哪怕得到的四根长度都是一样的。

输入格式
? 第一行:单个整数: N,1 ≤ N ≤ 2500

输出格式
? 第一行:单个整数,表示方案数目,保证这个数小于231

样例
quad.in 6 quad.out 6 ( 合法的有六个: (1,1,2,2),(1,2,1,2),(1,2,2,1),(2,1,1,2), (2,1,2,1),(2,2,1,1) 下面几种都是不合法的: (1,1,1,3),(1,1,3,1),(1,3,1,1),(3,1,1,1) )

第7题

建造道路 (Building Roads, USACO 2007 Dec)

约翰刚得到了几片新农场!他打算把这些农场连成一片,幸运的是,这些农场之间已经 存在M条道路了。已知共有N片农场,方便起见以数字1到N编号。每片农场在平面上的坐标 是(Xi , Yi )。请帮助约翰计算最少修建多少长的道路,才能把这些农场连成一片?

输入格式
?