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

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 )。请帮助约翰计算最少修建多少长的道路,才能把这些农场连成一片?

输入格式
? ? ? 第一行:两个用空格分开的整数:N和M,1 ≤ N ≤ 1000,1 ≤ M ≤ 1000 第二行到N + 1行:两个用空格分开的整数:X i和Yi,1 ≤ X i , Yi ≤ 106 第N + 2行到N + M + 2行:两个用空格分开的整数:i和j,代表存在一条从i到j的路

输出格式
? 第一行:需修建的最短总长度,保留两位小数

样例
roads.in 41 11 31 23 43 14 roads.out 4.00

(在 1 和 2 之间,3 和 4 之间修建道路,每 条道路的长度为 2.00,故总长为 4.00)

第8题 Feb)

青铜莲花池 (Bronze Lilypad Pond, USACO 2007

为了让奶牛们娱乐和锻炼,约翰建造了一个美丽的池塘。这个池塘是矩形的,可以分成 M × N个方格。一些格子是坚固得令人惊讶的莲花,还有一些是岩石,其余的只是美丽、纯 净、湛蓝的水。 贝西正在练习芭蕾舞,她站在一朵莲花上,想跳到另一朵莲花上去,她只能从一朵莲花 跳到另一朵莲花上,既不能跳到水里,也不能跳到岩石上。 贝西的舞步很像象棋中的马步:每次跳跃可以横移M1格,纵移M2格,或纵移M1格, 横移M2格,最多有八个方向可供移动选择。 请计算贝西到达终点的最小步数,输入数据保证终点是一定可达的。

输入格式
? ? 第一行:四个用空格分开的整数:M,N,M1和M2,1 ≤ M, N ≤ 30,1 ≤ M1 ≤ 30, 1 ≤ M2 ≤ 30,M1 ≠ M2 第二行到M + 1行:第i + 1行有N个用空格分开的整数,描述了池塘第i行的状态:0 为 水,1 为莲花,2 为岩石,3 为起点,4 为终点。

输出格式
? 第一行:从起点到终点的最少步数

样例
bronlily.in 4512 10101 30204 01200 00010 bronlily.out 2

(先跳到 1 行 3 列的莲花上,再跳到终点, 需要 2 步)

第9题

滑雪课程 (Ski Lessons, USACO 2009 Open)

约翰请贝西去科罗拉多去滑雪。不过贝西不太会玩,她只是个滑雪能力为1的渣渣。所 以她决心参加一些滑雪课程。 滑雪场提供S门课程, 第i门课开始的时间是Mi, 持续时间为Li , 上完课之后,贝西的滑雪能力将变成Ai。注意,能力不是增加Ai,而是变成Ai。 滑雪场有N条斜坡,第i条斜坡滑行一次需要Di 分钟,要求游客的滑雪能力达到Ci或以上 时才能进入。 贝西可以随意安排她的时间:滑雪、上课,或美美地喝上一杯可可汁,但她在滑雪场只 能呆到第T分钟。请问她如何安排时间,滑行次数才能尽量多?

输入格式
? ? ? 第一行:三个用空格分开的整数:T,S和N,1 ≤ T ≤ 104,1 ≤ S ≤ 100,1 ≤ N ≤ 105 第二行到S + 1行:第i + 1行描述了第i门课程,分别为Mi,Li 和Ai,彼此用空格隔开, 1 ≤ Mi , Li ≤ 104,1 ≤ Ai ≤ 100 第S + 2行到S + N + 1行:第S + i + 1行描述了第i条斜坡,分别为Ci和Di ,彼此用空格 隔开,1 ≤ Ci ≤ 100,1 ≤ Di ≤ 104

输出格式
? 第一行:单个整数,表示在时限内贝西可以滑完的最大次数

样例
ski.in 10 1 2 325 41 13 ski.out 6

(先滑 1 次 2 号斜坡,然后去上课,再去 1 号连滑 5 次,一共 6 次)

第10题 奶牛飞盘队 (Cow Frisbee Team, USACO 2009 Mar)
老唐最近迷上了飞盘, 约翰想和他一起玩, 于是打算从他家的N头奶牛中选出一支队伍。 每只奶牛的能力为整数,第i头奶牛的能力为R i 。飞盘队的队员数量不能少于 1、大于N。一 支队伍的总能力就是所有队员能力的总和。 约翰比较迷信,他的幸运数字是F,所以他要求队伍的总能力必须是F的倍数。请帮他 算一下,符合这个要求的队伍组合有多少?由于这个数字很大,只要输出答案除以109的余 数就可以了。

输入格式
? ? 第一行:两个用空格分开的整数:N和F,1 ≤ N ≤ 2000,1 ≤ F ≤ 1000 第二行到N + 1行:第i + 1行有一个整数R i ,表示第i头奶牛的能力,1 ≤ R i ≤ 105

输出格式
? 第一行:单个整数,表示方案数除以109的余数

样例
fristeam.in 45 1 2 8 2 fristeam.out 3

(有两种方案都是8 + 2 = 10, 只是选的奶牛 不一样,第三种方案是2 + 2 + 1 = 5)

第11题 奶牛博览会 (Cow Exhibition, USACO 2003 Fall)
奶牛想证明他们是聪明而风趣的。为此,贝西筹备了一个奶牛博览会,她已经对N头奶 牛进行了面试,确定了每头奶牛的智商和情商。 贝西有权选择让哪些奶牛参加展览。 由于负的智商或情商会造成负面效果, 所以贝西不 希望出展奶牛的智商之和小于零,或情商之和小于零。满足这两个条件下,她希望出展奶牛 的智商与情商之和越大越好,请帮助贝西求出这个最大值。

输入格式
? ? 第一行:一个整数N,表示奶牛的数量,1 ≤ N ≤ 100 第二行到第N + 1行:第i + 1行有两个用空格分开的整数:Si和Fi ,分别表示第i头奶牛 的智商和情商,?1000 ≤ Si ≤ 1000,?1000 ≤ Fi ≤ 1000

输出格式
? 第一行:单个整数,表示情商与智商和的最大值。贝西可以不让任何奶牛参加展览,如 果这样应该输出0

样例
smrtfun.in 5 -5 7 8 -6 6 -3 21 -8 -5 smrtfun.out 8

( 选择 1 ,3 ,4 号 奶牛, 此时 智商 和为 ?5 + 6 + 2 = 3,情商和为7 ? 3 + 1 = 5。加 入 2 号奶牛可使总和提升到10,不过由于情 商和变成负的了,所以是不允许的)

第12题 最近回文 (Cheapest Palindrome, USACO 2007 Open)
追踪奶牛是一件棘手的任务。 约翰安装了一套自动系统, 为每头奶牛设置了电子身份标 签,当奶牛通过扫描器的时候,系统可以读取奶牛的身份信息。标签是由字符串组成的,长 度为M,所用字符由N个小写字母组成。 奶牛是顽皮的动物, 她们有事会倒着通过扫描器。 这样一来,系统会把 abcb 读成 bcba, 识别发生了障碍。但是 abcba 就不会发生这个问题,因为它是一个回文。 于是约翰想把所有的标签都改成回文,比如在 abcb 的最后加个 a 就变成了 abcba;也 可以在前面加上 bcb,变成 bcbabcb;或者去除字母 a,只保留 bcb。约翰可以在任意位置删 除或插入字符。不巧的是,标签是电子产品,增加或删除字母都要付费。给定一头奶牛的身 份标签,以及增加删除相关字母的费用,找出把字符串变成回文的最小费用。注意空字符串 也算是一条回文。

输入格式
? ? ? 第一行:两个用空格分开的整数:N和M,1 ≤ M ≤ 2000,1 ≤ N ≤ 26 第二行:一个长M的字符串,代表原始的身份标签 第三行到第N + 2行: 每行为一个用空格分开的三元组: 其中包括一个字符和两个整数, 分别表示增加或删除这个字符的费用,所有的费用满足0 ≤ 费用 ≤ 10000

输出格式
? 第一行:只有一个整数,表示改造这个身份标签的最小费用

样例
cheappal.in 34 abcb a 1000 1100 b 350 700 c 200 800 cheappal.out 900 (如果在最后插入一个 a,得到 abcba,代价 为1000;如果删除第一个 a,得到 bcb,代价 为1100;如果在字符串的开头插入 bcb,代 价为350 + 200 + 350 = 900,这才是最优的 做法)

第13题 安慰奶牛 (Cheering up the Cows, USACO 2008 Nov)
约翰有N个牧场,编号依次为1到N。每个牧场里住着一头奶牛。连接这些牧场的有P条 道路,每条道路都是双向的。第j条道路连接的是牧场Sj 和Ej,通行需要Lj 的时间。两牧场之 间最多只有一条道路。约翰打算在保持各牧场连通的情况下去掉尽量多的道路。 约翰知道, 在道路被强拆后, 奶牛会非常伤心, 所以他计划拆除道路之后就去忽悠她们。 约翰可以选择从任意一个牧场出发开始他维稳工作。 当他走访完所有的奶牛之后, 还要回到 他的出发地。每次路过牧场i的时候,他必须花Ci 的时间和奶牛交谈,即使之前已经做过工 作了, 也要留下来再谈一次。 注意约翰在出发和回去的时候, 都要和出发地的奶牛谈一次话。 请你计算一下,约翰要拆除哪些道路,才能让忽悠奶牛的时间变得最少?

输入格式
? ? ? 第一行:两个用空格分开的整数: N和P,5 ≤ N ≤ 10,000,N ? 1 ≤ P ≤ 100,000 第二行到N + 1行:第i + 1行包括一个整数Ci,1 ≤ Ci ≤ 1,000 第N + 2行到N + P + 1行:第N + j + 1行包括三个用空格分开的整数Sj ,Ej和Lj , 1 ≤ Sj , Ej ≤ N, Sj ≠ Ej,0 ≤ Lj ≤ 1,000

输出格式
? 第一行:一个整数,表示忽悠所有奶牛需要的最少时间

样例
cheer.in 57 10 10 20 6 30 125 235 2 4 12 3 4 17 2 5 15 356 4 5 12 cheer.out 176

(从 4 号牧场出发,依次访问 4,5,4,2, 3,2,1,2,4 号牧场)

第14题 玉米迷宫 (Corn Maze, USACO 2011 Open)
今年秋天,约翰带着奶牛们去玩玉米迷宫。迷宫可分成N × M个格子,有些格子种了玉 米,种着玉米的格子无法通行。迷宫的四条边界上都是种了玉米的格子,其中只有一个格子 没种,那就是出口。在这个迷宫里,有一些神奇的传送点。每个传送点由一对点组成,一旦 走入传送点的某个结点, 机器就会强制把你送到传送点的另一头去。 所有的传送点都是双向 的,如果你走到了另一头,机器也会把你送回来。 奶牛在一个单位的时间内只能向相邻的四个方向移动一格, 不过传送机传送是瞬间完成 的。现在贝西在迷宫里迷路了,她只知道目前的位置在哪里,请你帮助她用最短的时间走出 迷宫吧。

输入格式
? ? 第一行:两个用空格分开的整数:N和M,2 ≤ N, M ≤ 300 第二行到N + 1行:第i + 1行有M个连续的字符,描述了迷宫第i行的信息。其中“#”代 表不能通行的玉米地, “.”代表可以通行的草地, “@”代表贝西的起始位置, “=”代 表迷宫出口,大写字母“A”到“Z”总是成对出现的,代表一对传送点

输出格式
? 第一行:一个整数,表示贝西走出迷宫的最短时间,保证逃离迷宫的路线一定存在

样例
cornmaze.in 5 6 ###=## #.W.## #.#### #.@W## ###### cornmaze.out 3

(从起点向左走,通过 W 传送,再从另一端 走出迷宫)

第15题 奶牛集会 (MooFest, USACO 2004 Open)
约翰家的N头奶牛每年都会参加“哞哞大会” 。哞哞大会是世界奶牛界的盛事。集会上 的活动很多,比如堆干草,跨栅栏,摸牛仔的屁股等等。当然,哞哞大叫肯定也包括在内。 奶牛们的叫声很大,很多奶牛在参加多年活动之后,实际上已经失去了一部分的听力。 奶牛们已经站在了一条直线上,i号奶牛的坐标为X i,她只能听到大于Vi 的声音。每头奶 牛的位置坐标都是唯一的。 如果i号和j号奶牛想对话, 则他们使用的音量为max{Vi , Vj } × |X i ? X |。 N头奶牛可以组合成N(N ? 1)/2对奶牛,假设每对奶牛都使用最小的音量在对话,请计 算所有奶牛产生的总音量是多少。

输入格式
? ? 第一行:单个整数:N,1 ≤ N ≤ 20000 第 二行 到第N + 1 行 :每 行有两 个用 空格分 开的 整数, Vi 和 X i ,1 ≤ Vi ≤ 20000, 1 ≤ X i ≤ 20000

输出格式
? 第一行:单个整数,表示最小音量之和

样例
moofest.in 4 31 25 26 43 moofest.out 57

第16题 奶牛文字 (Cowlphabet, USACO 2011 Feb)
约翰家的奶牛用别人听不懂的“牛语”联络。牛语采用英文字母,而且区分大小写。牛 语中的语法中,前后字母的衔接非常重要,存在P个基本组合,每个字母之后只能接固定的 几个字母。 约翰担心奶牛正在密谋反对他,于是最近一直在偷听她们的对话。可是牛语太复杂了, 他只模模糊糊地听到了一个单词,并确定了这个单词中有U个大写字母,L个小写字母。约 翰对这个单词很在意,他想知道,有多少牛语词汇拥有U个大写字母,L个小写字母。由于 这个数字太大了,你只要输出答案取 97654321 的余数就可以了。

输入格式
? ? 第一行:三个用空格隔开的整数:U,L和P,1 ≤ U, L ≤ 250,1 ≤ P ≤ 200 第二行到P + 1行:第i + 1有两个字母Ai和Bi,表示字母Ai后面可以接Bi,没有一对Ai和 Bi是完全相同的

输出格式
? 第一行:单个整数,表示符合条件的词汇数量除以 97654321 的余数

样例
cowlpha.in 227 AB ab BA ba Aa Bb bB cowlpha.out 7

(可能的单词为 AabB,ABba,abBA,BAab, BbBb,bBAa,bBbB)

第17题 奶牛跨栏 (Cow Hurdles, USACO 2007 Nov)
约翰家的奶牛正在准备跨栏比赛。对奶牛来说,跳过几个矮栅栏是容易的,但一个高栅 栏却很难跳过。于是,奶牛们关心的是一条路线上所有栅栏中的最高高度。 奶牛的训练场中有N个站台,标号为1到N。站台之间有M条单向道路,第i条道路的起点 是Si,终点是Ei,道路上栅栏的高度为Hi 。 奶牛们有T个训练任务要完成。第i个任务要求奶牛必须从站台A 跑到站台Bi,奶牛可以 自由选择路线,为了寻找最轻松的路线,绕点远路可能也是值得的。你的任务就是写一个程 序,帮助奶牛尽可能地降低每个训练任务会遇到的最高栅栏的高度。

输入格式
? ? ? 第一行:三个用空格分开的整数: N,M和T,1 ≤ N ≤ 300,1 ≤ M ≤ 25000, 1 ≤ T ≤ 40000 第二行到M + 1行:第i + 1行有三个用空格分开的整数: Si ,Ei和Hi ,1 ≤ Si ≤ N, 1 ≤ Ti ≤ N,1 ≤ Hi ≤ 106 第M + 2行到M + T + 1行: + M + 1行有两个用空格分开的整数: i和Bi, ≤ Ai ≤ N, 第i A 1 1 ≤ Bi ≤ N

输出格式
? 第一行到第T行:每行一个整数,表示起点为Ai,终点为Bi的路线中最高的栅栏高度的 最小值,如果从Ai到Bi不存在路线,输出?1

样例
hurdles.in 563 1 2 12 328 135 253 344 248 34 12 51 hurdles.out 4 8 -1

(第一个查询:直接从 3 到 4 即可;第二个 查询:可以直接到 2,但还是先到 3,再到 2 为好)

第18题 工作安排 (Work Scheduling, USACO 2009 Open)
为了让农场有效运转,约翰必须靠自己工作来赚钱。他接到了N项任务,完成每项任务 都要花费一个单位的时间。第i项任务的截止时间为Di ,如果能按时完成,可以得到报酬Pi 。 约翰从0时刻开始工作,由于他在同一个时间内只能从事一项任务,所以他很难按时完成所 有任务。请帮助约翰计算一下,他最多可以赚多少钱?

输入格式
? ? 第一行:单个整数:N,1 ≤ N ≤ 105 第二行到N + 1行:在第i + 1行有两个用空格分开的整数:Di 和Pi ,1 ≤ Di , Pi ≤ 109

输出格式
? 第一行:单个整数,表示约翰可赚得的最多钱

样例
job.in 3 2 10 15 17 job.out 17

(先做第三个任务,再做第一个任务)

第19题 手机网络 (Cell Phone Network, USACO 2008 Jan)
约翰决定为他的奶牛配备手机,以鼓励她们之间互相交流。奶牛居住在N片牧场上,编 号为1到N。约翰需要建立一些通讯基站,一个牧场如果建了基站,那么它和它相邻的牧场 就能收到信号,一共有N ? 1对牧场是相邻的。所有牧场都和其他牧场通过相邻关系连通。 请帮助约翰计算一下,如果要让所有牧场都收能到信号,最少要建几座基站?

输入格式
? ? 第一行:单个整数:N,1 ≤ N ≤ 10,000 第二行到N行:每行有两个用空格分开的整数,表示一对相邻牧场的编号

输出格式
? 第一行:单个整数,表示最少的基站数目

样例
tower.in 5 13 52 43 35 tower.out 2

(建在 2 号、3 号或 3 号、5 号上均可)

第20题 提交作业 (Turning in Homework, USACO 2004 Open)
贝西在哞哞大学选修了C门课,她要把这些课的作业交给老师,然后去车站和同学们一 起回家。 老师们在办公室里, 办公室要等他们下课后才开, 第i门课的办公室在Ti 时刻后开放。 所有的办公室都在一条走廊上,这条走廊长H米,一开始贝西在走廊的最西边,第i门课 的办公室距离贝西的长度为X i,车站距离贝西的长度为B。 贝西可在走廊上自由行走, 每时刻可以向东或者向西移动一单位的距离, 也可以选择在 任何地方暂停。贝西如果走到办公室所处的位置,而且这间办公室已经开门了的话,就可以 把作业交掉,不用花时间在走进办公室上。 请帮助贝西确定交完所有作业,再走到车站的最短时间。

输入格式
? ? 第一行:三个整数C,H和B,1 ≤ C ≤ 1000,1 ≤ H ≤ 1000,0 ≤ B ≤ H 第二行到C + 1行:每行两个整数,表示X i和Ti ,0 ≤ X i ≤ H,0 ≤ Ti ≤ 10000

输出格式
? 第一行:单个整数,表示贝西交完作业后走到车站的最短时间

样例
turnin.in 4 10 3 89 4 21 3 16 8 12 turnin.out 22 ( 时刻 0 8 9 12 12 16 21 21 22 22 )

贝西的行动 走向坐标为 8 的教室 等待 交第一本作业,等待 在原位置交第二本作业 走向坐标为 4 的教室 等待 交一本作业 走向坐标为 3 的教室 交一本作业 贝西正好到车站了,结束

第21题 滑雪缆车 (Ski Lift, USACO 2006 Mar)
科罗拉多州的罗恩打算为奶牛建造一个滑雪场,为此要在山上规划一条缆车线路。 整座山可以用一条折线来描述,该折线有N个拐点,起点是1,终点是N。每个拐点的高 度为Hi ,相邻两个拐点之间的水平距离都是1。 缆车线路必须从起点开始修建,结束于终点。中间可以选择一些拐点安放缆绳的支柱, 安全标准有两点:第一,缆绳的跨度有限制——相邻支柱的水平距离不能超过K;第二,缆 绳的高度有限制——两根支柱之间的钢丝视作笔直的, 在这座山的任何位置, 钢丝都不能低 于山的高度,但允许缆绳紧贴在山坡上或恰好穿过某个山峰。支柱相对于拐点的高度不计。 为了节约,罗恩希望修建的支柱越少越好,请帮他规划一下吧!当然,起点和终点上是 一定要修建支柱的。

输入格式
? ? 第一行:两个用空格分开的整数:N和K,2 ≤ N ≤ 5000,1 ≤ K ≤ N ? 1 第二行到N + 1行:第i + 1行有一个整数Hi ,0 ≤ Hi ≤ 109

输出格式
? 第一行:单个整数,表示最少需要修建的支柱数量

样例
skilift.in 13 4 0 1 0 2 4 6 8 6 8 8 9 11 12 skilift.out 5

(支柱设在 1、5、7、9、13 号点处是最优方 案。如果只设在 1、5、9、13 上,那么 5 到 9 就会有钢丝低于山坡的高度。如果只在 1、 7、13 上修建,虽然高度符合要求,但这两 段支柱的水平距离都超过了K)

第22题 派发巧克力 (Chocolate Giving, USACO 2010 Feb)
情人节到了,约翰准备向奶牛派发巧克力。约翰的牧场有N块草地,这些草地的编号为 1到N,有M条双向道路将它们连接起来,第i条道路连接的草地为R i 和Si,道路的长度为Li 。 两片草地之间,可能会有重复的道路连接它们。 牧场里有B头大牛,每头大牛都有一个表白对象,第i头大牛在草地Pi 上,他暗恋的母牛 在草地Qi 上。约翰在1号草地上派发巧克力,所以为了拿到巧克力,大牛们先要走到1号草 地,然后从1号草地走到表白对象所在的地方。所有的草地都是相互连通的。请帮助这些大 牛算一下,他们行走的最短距离分别是多少。

输入格式
? ? ? 第一行:三个用空格分开的整数:N,M和B,1 ≤ N ≤ 50000,1 ≤ M ≤ 105, 1 ≤ B ≤ 25000 第二行到M + 1行:在第i + 1行有三个用空格分开的整数,代表第i条道路的信息:R i , Si和Li ,1 ≤ R i , Si ≤ N,1 ≤ Li ≤ 2000 第M + 2行到M + B + 1行:在第i + M + 1行有两个用空格分开的整数:Pi 和Q i, 1 ≤ Pi , Q i ≤ N

输出格式
? 第一行到第B行:在第i行有一个整数,表示第i头公牛行走的最短距离

样例
cgiving.in 673 123 543 311 619 342 144 322 24 51 36 cgiving.out 6 6 10

(第一头大牛从 2 走到 1,再经过 3,最终走 到 4;第二头大牛从 5 走到 4,在走到 3,最 后停在 1; 第三头大牛从 3 走到 1, 再走到 6)

第23题 赞助学费 (Financial Aid, USACO 2004 Mar)
人类可以选择很多大学,而奶牛们却没学可上。为解决这个问题,贝西和她的伙伴们创 立了一所奶牛大学,取名为哞哞大学。 为了选拔优秀学生,她们发明了一种奶牛学术能力测试(简称 CSAT) ,这种测试的分数 异常精确,每头奶牛的成绩可以用0到2 × 109之间的一个整数表示,而且可以保证每头奶牛 的分数都不同。 哞哞大学的学费很贵,奶牛们表示负担不起,他们都各自申请了奖学金。政府并没有为 奶牛准备奖学金,所有的预算都必须要从学校有限的助学基金中扣除(设基金总额为F) 。 哞哞大学有N间宿舍,N是一个奇数,所以贝西只能接受N头奶牛的申请,她发誓不会让 入学的奶牛少于N。此外,她希望新生的 CSAT 成绩表现优异,她以中位数来衡量新生的总 体水平。所谓中位数,就是排序后处在最中间的分数,比如3,8,9,7,5的中位数是7。 今年,共有C头奶牛申请入学,给定每头奶牛的 CSAT 成绩和申请的奖学金数目,以及学 校可赞助的总额,确定贝西接受哪些奶牛的申请才可以使成绩的中位数达到最大。

输入格式
? ? 第一行:三个用空格分开的整数:N,C和F。1 ≤ N ≤ 19999,N ≤ C ≤ 105, 0 ≤ F ≤ 2 × 109 第二行到C + 1行:每行有两个用空格分开的整数。第一个数是这头奶牛的 CSAT 成绩, 第二个数是这头奶牛需要的奖学金Qi ,0 ≤ Q i ≤ 105。

输出格式
? 第一行:一个整数,表示贝西可以得到的最大中位数,如果现有基金不够资助任何N头 奶牛,则输出-1。

样例
finance.in 3 5 70 30 25 50 21 20 20 5 18 35 30 finance.out 35

(贝西接受 CSAT 分数为 5,35,50 的奶牛的 申请,中位数为 35,需支付的奖学金总额为 18 + 30 + 21 = 69)

第24题 白银莲花池 (Silver Lilypad Pond, USACO 2007 Feb)
为了让奶牛们娱乐和锻炼,约翰建造了一个美丽的池塘。这个池塘是矩形的,可以分成 M × N个方格。一些格子是坚固得令人惊讶的莲花,还有一些是岩石,其余的只是美丽、纯 净、湛蓝的水。 贝西正在练习芭蕾舞,她站在一朵莲花上,想跳到另一朵莲花上去,她只能从一朵莲花 跳到另一朵莲花上,既不能跳到水里,也不能跳到岩石上。 贝西的舞步很像象棋中的马步:每次跳跃可以横移 2 格,纵移 1 格,或纵移 1 格,横移 2 格,最多有八个方向可供移动选择。 约翰一直在观察贝西的芭蕾练习, 发现她有时不能跳到终点, 因为中间缺了一些必要的 莲花。 约翰可以多种一些莲花来帮助贝西到达终点。 不过要注意有石头的格子是不能种莲花 的。 请帮助约翰求出至少要添加几朵莲花才能让贝西跳到终点,记这个数字为L,再求出添 加L朵莲花后贝西跳到终点的最少步数,记这个数字为J。最后求出添加L朵莲花后跳到终点 的步数为J的路线有多少条,记这个数字为W。

输入格式
? ? 第一行:两个用空格分开的整数:M和N,1 ≤ M, N ≤ 30 第二行到M + 1行:第i + 1行有N个用空格分开的整数,描述了池塘第i行的状态:0 为 水,1 为莲花,2 为岩石,3 为起点,4 为终点。

输出格式
? ? ? 第一行:一个整数:L,即需要添加的最少莲花数目,如果无解输出-1 第二行:一个整数:J,如果第一行是-1,不需要输出这行 第三行:一个整数:W,如果第一行是-1,不需要输出这行

样例
silvlily.in 48 00010000 00000201 00000400 30000010 silvlily.out 2 6 2

第25题 地震 (Earthquake, USACO 2001 Open)
一场地震把约翰家的牧场摧毁了, 坚强的约翰决心重建家园。 约翰已经重建了N个牧场, 现在他希望能修建一些道路把它们连接起来。研究地形之后,约翰发现可供修建的道路有M 条。碰巧的是,奶牛们最近也成立一个工程队,专门从事修复道路。而然,奶牛们很有经济 头脑,如果无利可图,它们是不会干的。 奶牛们关注的是挣钱速度,即总利润和总施工时间的比值。约翰和奶牛达成了协议,奶 牛负责修建道路,将所有牧场连通,而约翰需要支付F元。每条道路都有自己的施工时间和 建造成本。连接两个相同的牧场的道路可能有多条。保证所有的牧场必定是可连通的,不过 也有可能一些道路的建造成本之和会超过F。 请帮助奶牛们选择修复哪些道路,才能使单位时间的利润最大?

输入格式
? ? 第一行:三个整数: N,M和F,1 ≤ N ≤ 400,1 ≤ M ≤ 10000,1 ≤ F ≤ 2 × 109 第二行到M + 1行:第i + 1行表示第i条道路的信息,有四个整数:Ui ,Vi ,Ci和Ti ,Ui 和 Vi 表示这条道路连接的牧场编号,Ci表示这条路的施工时间,Ti 表示建造成本, 1 ≤ Ui ≤ N,1 ≤ Vi ≤ N,1 ≤ Ci ≤ 2 × 109,1 ≤ Ti ≤ 2 × 109

输出格式
? 第一行:一个保留四位小数的浮点数,表示奶牛们能挣到的最大单位时间利润,如果奶 牛们无钱可赚,则输出 0.0000

样例
quake.in 5 5 100 1 2 20 5 1 3 20 5 1 4 20 5 1 5 20 5 2 3 23 1 quake.out 1.0625

(奶牛们可以选择连通最后四条道路,则总 时间为 16,总成本为 83,所以单位利润为 17/16 = 1.0625)

第26题 股票市场 (Stock Market, USACO 2009 Feb)
尽管奶牛们天生谨慎, 她们仍然在住房抵押信贷市场中大受打击, 现在她们准备在股市 上碰碰运气。贝西开挂了,她知道S只股票在今后D天内的价格。 假设她一开始有M元钱,怎么操作才能在D天后赚到最多的钱?股票在市场上的供应量 可以看成是无限的,但买卖股票必须以整数为最小交易单位。 举一个牛市的例子。假设贝西有10元本金,股票价格如下: 股票 今天的单价 明天的单价 后天的单价 A 10 15 15 B 13 11 20 最赚钱的做法是:今天买入 A 股 1 张,到明天把它卖掉并且买入 B 股 1 张,然后在后 天卖掉 B 股,此时贝西手上会有24元。

输入格式
? ? 第一行: 三个用空格分开的整数: D和M, ≤ S ≤ 50, ≤ D ≤ 10, ≤ M ≤ 200000 S, 2 2 1 第二行到第S + 1行:第s + 1行表示第s种股票在第 1 天到第D天的售价,1 ≤ 售价 ≤ 1000

输出格式
? 第一行:D天后能赚的最多钱数,保证这个数字不超过500000

样例
stock.in 2 3 10 10 15 15 13 11 20 stock.out 24

第27题 奶牛赛车 (Cow Cycling, USACO Feb 2002)
奶牛自行车队由N名队员组成,他们正准备参加一个比赛,这场比赛的路程共有D圈。 车队在比赛时会排成一条直线,由于存在空气阻力,当骑车速度达到每分钟x圈时,领头的 奶牛每分钟消耗的体力为x 2 ,其它奶牛每分钟消耗的体力为x。每头奶牛的初始体力值都是 相同的,记作E。如果有些奶牛在比赛过程中的体力不支,就会掉队,掉队的奶牛不能继续 参加比赛。每支队伍最后只要有一头奶牛能到终点就可以了。 比赛规定,最小的计时单位是分钟,在每分钟开始的时候,车队要哪头奶牛负责领头, 领头奶牛不能在这分数中内掉队,每分钟骑过的圈数也必须是整数。 请帮忙计划一下,采用什么样的策略才能让车队以最快的时间到达终点?

输入格式
? 第一行:三个正整数:N,E和D,1 ≤ N ≤ 20,1 ≤ E ≤ 100,1 ≤ D ≤ 100

输出格式
? 第一行:单独一个整数,表示最早达到终点的时间,如果无法到达终点,输出 0

样例
cycling.in 3 30 20 cycling.out 7

说明: 剩余体力 奶牛 1 5 1 奶牛 2 25 23 7 3 掉队 0 掉队 奶牛 3 25 23 19 17 8 4 0

时间 1 2 3 4 5 6 7

领头牛 1 2

速度 5 2 4 2 3 2 2

完成圈数 5 7 11 13 16 18 20

3

第28题 奶牛观光 (Sightseeing Cows, USACO 2007 Dec)
作为对奶牛辛勤工作的回报,约翰决定带她们去附近的大城市玩一天。这个城市有L个 景点,参观第i个景点会给奶牛带来Fi 点欢乐度。第二天一早,奶牛可以自由选择从一个景 点出发,约翰会负责开车把她们送到那里,但她们晚上必须回到这个景点和约翰汇合。 大城市里都是单行道,第i条道路从第L1i 个建筑通向第L2i 个建筑,走完需要Ti 的时间。 奶牛讨厌走路,定义一条游览线路的“欢乐指数”为参观这条线路上所有景点的欢乐度之和 与花在路上的时间之和的比值。欢乐指数越大的线路越受欢迎。当然,参观同一景点两次不 会带来双倍的欢乐。 假设奶牛们至少参观两个景点, 请帮她们找到一条欢乐指数最大的线路。

输入格式
? ? ? 第一行:两个用空格分开的整数:L和P,1 ≤ L ≤ 1000,2 ≤ P ≤ 5000 第二行到L + 1行:第i + 1行有一个整数Fi ,1 ≤ Fi ≤ 1000 第L + 2行到L + P + 1行:第i + L + 1行有三个用空格分开的整数:L1 ,L2j 和Ti , 1 ≤ L1i ≤ L,1 ≤ L2i ≤ L,1 ≤ Ti ≤ 1000

输出格式
? 第一行:输出一个实数,表示最大的欢乐指数,保留两位小数

样例
sightsee.in 57 30 10 10 5 10 123 232 345 352 455 513 522 sightsee.out 6.00

(1 → 2 → 3 → 5 → 1,总乐趣值为60,花费 在路上的时间为10)

第29题 道路重建 (Rebuilding Roads, USACO Feb 2002)
在一场严重的地震之后,奶牛们重建了约翰的牧场。牧场里有N个牛棚,编号为1到N。 这些牛棚之间有道路相连, 由于奶牛们的时间不够重建更多的道路, 所以目前任意两个牛棚 之间有且只有一条路径。 约翰打算把奶牛安置在相邻的P个牛棚里,位置还没选定。他想知道下一场地震将造成 多大的损失。以最坏打算来看,地震至少摧毁几条道路,才会让某处的P个牛棚和其他牛棚 完全隔绝呢?

输入格式
? ? 第一行:两个正整数:N和P,1 ≤ P ≤ N ≤ 150 第二行到第N行:共N ? 1行,每行有两个整数,表示这两个牛棚之间存在一条道路

输出格式
? 第一行:单独一个整数,表示地震需要破坏最少道路条数

样例
roads.in 11 6 12 13 14 15 26 27 28 49 4 10 4 11 roads.out 2

(被隔绝的牛棚是(1,2,3,6,7,8),被破坏的道 路是(1,4)和(1,5))

第30题 奶牛接力 (Cow Relays, USACO 2007 Nov)
为增强体质,约翰决定举办一场奶牛接力跑比赛。比赛现场有一些接力位置,这些位置 间有T条路连接,第i条路的长度为Li 。 有N头奶牛需要参加比赛,领头的奶牛从位置S出发,她会按照你的指示沿着一条路跑 到下个位置,把接力棒交给等在那里的下一头奶牛,就休息去了。每头奶牛重复这个过程, 这条接力路线的终点必须在位置E上。奶牛数量较多,允许一些奶牛等候在同一位置,一条 路也可以供多头奶牛奔跑。 奶牛们对接力跑兴趣不大, 拜托你敷衍地设计一条总长度最短的路线。 所以请设计一条 由N段路组成的,起点在S,终点在E上的最短路线吧。

输入格式
? ? 第一行:四个用空格分开的整数:表示N,T,S和E,2 ≤ N ≤ 106,2 ≤ T ≤ 100, 1 ≤ S, E ≤ 1000 第二行到T + 1行: + 1行首先有一个正整数Li , 第i 表示第i条路的长度, ≤ Li ≤ 1000, 1 其次是Ui 和Vi ,表示第i条路连接的两个位置,1 ≤ Ui , Vi ≤ 1000

输出格式
? 第一行:单个整数,表示起点为S,终点为E,且恰好经过N段路的最短路线长度

样例
relays.in 2664 11 4 6 448 849 668 269 389 relays.out 10

(最短路线为6 → 8 → 4,或者6 → 9 → 4也 可以)

第31题 猜数游戏 (Haybale Guessing, USACO 2008 Jan)
为了提高智商,锻炼思维能力,奶牛设计了一个猜数游戏。游戏开始前,贝西会在牛棚 后面摆上N个数字。所有数字排成一条直线,按次序从1到N编号。每个数字在1到109 之间, 没有两个数字是一样的。 游戏开始后,其他奶牛将会轮流询问贝西Q个问题,每个问题的格式都是一样的: “位置在Q l到Q r的数字中,最小的数字是多少?” 对每个问题,贝西都会回答一个数字A,不过,她的回答可能是不正确的。请你帮助其 他奶牛判断一下,贝西从哪里开始已经出现矛盾了。

输入格式
? ? 第一行:两个用空格分开的整数:N和Q,1 ≤ N ≤ 106,1 ≤ Q ≤ 25000 第二行到第Q + 1行:每行三个用空格分开的整数,Q l ,Q r 和A,表示一个查询, 1 ≤ Ql ≤ Qh ≤ N

输出格式
? 第一行:如果完全没有矛盾,输出 0,否则输出最先造成矛盾的查询编号

样例
bales.in 20 4 1 10 7 5 19 7 3 12 8 11 15 12 bales.out 3

(前两个问题的回答可以推出5到10之间最 小数量是7,这和第三个回答矛盾)

第32题 混乱奶牛 (Mixed Up Cows, USACO 2008 Nov)
约翰家有N头奶牛,第i头奶牛的编号是Si,每头奶牛的编号都是唯一的。这些奶牛最近 在闹脾气,为表达不满的情绪,她们在挤奶的时候一定要排成混乱的队伍。在一只混乱的队 伍中,相邻奶牛的编号之差均超过K。比如当K = 2时,1, 3, 5, 2, 6, 4就是一支混乱的队伍, 而1, 3, 6, 5, 2, 4不是,因为6和5只差1。请数一数,有多少种队形是混乱的呢?

输入格式
? ? 第一行:两个用空格分开的整数: N和K,4 ≤ N ≤ 16,1 ≤ K ≤ 3400 第二行到N + 1行:第i + 1行包括一个整数Si,1 ≤ Si ≤ 25000

输出格式
? 第一行:一个整数,表示混乱队伍的数量,保证答案小于263

样例
mixup2.in 41 3 4 2 1 mixup2.out 2

(两个满足条件的排法是3,1,4,2和2,4,1,3)

第33题 修 剪 草 坪 (Mowing the Lawn, USACO 2011 Open)
在去年赢得了小镇的最佳草坪比赛后, 约翰变得懒惰了, 再也没有修剪过草坪了。 现在, 新一轮的比赛又开始了,约翰希望能够再次夺冠。然而,约翰的草坪非常脏乱,因此,约翰 需要让他的奶牛来完成这项工作。约翰有N头奶牛,平时排成一条直线,编号为1到N。每只 奶牛的能力是不同的,第i头奶牛的能力为Ei。靠在一起的奶牛很熟悉,所以如果安排编号 连续的K + 1头奶牛在一起工作,她们就会密谋罢工。因此,约翰需要你的帮助。如何挑选 奶牛,才能使她们的工作能力之和最高,而且不会罢工呢?

输入格式
? ? 第一行:两个用空格隔开的整数:N和K,1 ≤ N ≤ 105,1 ≤ K ≤ N 第二行到N + 1行:第i + 1行有一个整数,表示第i头牛的能力Ei,1 ≤ Ei ≤ 109

输出格式
? 第一行:单个整数,表示最大的工作能力之和

样例
mowlawn.in 52 1 2 3 4 5 mowlawn.out 12

(除了第三头以外的所有奶牛都选,总能力 为1 + 2 + 4 + 5 = 12)

第34题 道路翻新 (Revamping Trails, USACO 2009 Feb)
农场里有N个牛棚,编号为1到N。它们之间由M条双向道路连接,第i条道路连接的牛棚 为P1i 和P2i ,通行时间为Ti 。约翰每天都要检查牛棚里的奶牛,他会从编号为1牛棚出发, 通过最短的路线走到编号为N的牛棚。为了节约时间,约翰打算翻新K条道路,被翻新后的 道路可以快速通过,通行时间视作0。请帮助约翰选择最好的翻新方法使得从1号牛棚到N号 牛棚的通行时间最短。

输入格式
? ? 第一行: 三个用空格分开的整数: M和K, ≤ N ≤ 10000, ≤ M ≤ 50000, ≤ K ≤ 20 N, 1 K 1 第二行到M + 1行:在第i + 1行有三个用空格分开的整数:P1i,P2i和Ti ,表示第i条道 路的情况,1 ≤ P1i , P2i ≤ N,1 ≤ Ti ≤ 106

输出格式
? 第一行:翻新后的最短通行时间,输入数据保证终点一定可达

样例
revamp.in 441 1 2 10 2 4 10 131 3 4 100 revamp.out 1

(选择翻新3 → 4, 通行时间从100变成0, 最 短路径为1 → 3 → 4,因而总用时为1)

第35题 安排牧场 (Corn Fields, USACO 2006 Nov)
约翰新买了一片牧场,这片牧场可以被分成N × M块土地。他打算在一些土地里种上牧 草, 供奶牛享用。 不过有些土地相当贫瘠, 种不出任何东西, 天生就不适合用来放牧。 此外, 奶牛们要求有一种独霸的感觉。 所以如果两块土地共享一条边界, 那么这两块土地里最多只 能有一块放牧奶牛,不然她们就会引起冲突的。约翰不知道在哪些土地上放牧为好,作为参 考,他想知道一共有多少种方案可供选择。注意不在任何地方放牧奶牛也算是一种方案。

输入格式
? ? 第一行:两个用空格分开的整数:M和N,1 ≤ M ≤ 12,1 ≤ N ≤ 12 第二行到M + 1行:每行有N个用空格分开的整数,每个整数为0或1,0说明这块土地不 能放牧,1说明这块土地可以放牧

输出格式
? 单独一行:表示方案总数除以108 之后的余数

样例
cowfood.in 23 111 010 cowfood.out 9

(放牧 1 头牛有 4 种方案,放牧 2 头牛有 3 种方案,放牧 3 牛有 1 种方案,所以一共有 9 种方案)

第36题 叠积木 (Cube Stacking, USACO 2004 Open)
约翰和贝西在叠积木。共有30000块积木,编号为1到30000。一开始,这些积木放在 地上,分成N堆,每堆只有一块。贝西可以把积木叠起来,一旦积木叠在了一起,就再也不 会分开了,所以最后叠在一起的积木会越来越多,也会越来越高。约翰让贝西依次执行P条 操作,操作分为两种: ? 第一种是“移动X到Y” :X和Y分别代表一块积木,意思是将X所的那堆积木,叠放 到Y所在的那堆积木之; ? 第二种是“统计Z的下方” :意思是贝西需要报告在编号为Z的积木之下有多少块积 木 请编写一个程序,帮助贝西正确操作,并报告统计查询的答案。

输入格式
? ? 第一行:单个整数:P,1 ≤ P ≤ 105 第二行到第P + 1行:每行描述一条命令,如果这行开头的字母是 M,代表一条移动命 令,后面的两个整数代表上文中的X和Y;如果开头字母是 C,代表一条统计命令。后面 的整数代表上文中的Z,保证所有的移动命令都是有意义的,不会出现X和Y已经在同一 堆里的情形。

输出格式
? 对每一个计数命令,输出正确的回答,用换行符分开每个查询操作的结果。

样例
cubes.in 6 M16 C1 M24 M26 C3 C4 cubes.out 1 0 2

(第一次查询时,1 下面只有一个 6;第二次 查询时, 下面没有任何积木; 3 第三次查询时, 4 下面有两块积木:1 和 6)

第37题 奶牛抗议 (Generic Cow Protests, USACO 2011 Feb)
约翰家的N头奶牛聚集在一起,排成一列,正在进行一项抗议活动。第i头奶牛的理智度 为Ai,Ai可能是负数。约翰希望奶牛在抗议时保持理性,为此,他打算将所有的奶牛隔离成 若干个小组,每个小组内的奶牛的理智度总和都要大于零。由于奶牛是按直线排列的,所以 一个小组内的奶牛位置必须是连续的。 请帮助约翰计算一下,存在多少种不同的分组的方案。由于答案可能很大,只要输出答 案除以1,000,000,009的余数即可。

输入格式
? ? 第一行:单个整数:N,1 ≤ N ≤ 106 第二行到N + 1行:在第i + 1行有一个整数:Ai,表示第i头奶牛的理智度,?105 ≤ Ai ≤ 105

输出格式
? 第一行:单个整数,表示分组方案数除以1,000,000,009的余数

样例
protest.in 4 2 3 -3 1 protest.out 4

(分别是[2 3 ? 3 1],[2 3 ? 3] [1], [2] [3 ? 3 1],[2] [3 ? 3] [1])

第38题 洞 穴 奶 牛 第 一 话 (Cave Cow 1, USACO 2004 Open)
奶牛有个不为人知的秘密:她们喜欢去洞穴探险。贝西去的地方由N个洞穴组成,这些 洞穴的编号是1到N。洞穴之间由M条隧道相连,隧道都是可以双向通行的。贝西准备充分, 事先已在K个洞穴里放置了食物。贝西的身材可以用一个数字来描述,一开始是0。当她吃 掉一份食物后,身材就会加 1。每条隧道有一个尺寸,如果贝西的身材比隧道的尺寸还大, 就钻不过去了。贝西准备从1号洞穴出发,在探险的过程中,她想吃掉尽量多的食物,但要 保证能回到起点。 请帮助贝西计划一下, 选择什么样的路线才能吃掉最多的食物?注意路过 有食物的洞穴时,不必匆忙吃掉食物,也可以等到下次路过的时候再吃。

输入格式
? ? ? 第一行:三个用空格分开的整数N,M和K,1 ≤ N ≤ 100,1 ≤ M ≤ 1000,1 ≤ K ≤ 14 第二行到K + 1行:每行一个整数Ci,代表洞穴Ci里有一份食物,1 ≤ Ci ≤ N 第K + 2行到第K + M + 1行: 每行代表一条隧道, 有三个用空格分开的整数X i, i和Wi , Y 其中X i和Yi代表隧道连接的两个洞穴,Wi 代表这条隧道的宽度,1 ≤ X i , Yi ≤ N, 1 ≤ Wi ≤ 100

输出格式
? 第一行:单个整数,表示贝西最多能吃多少份食物

样例
cavecow1.in 675 1 2 3 4 5 123 362 6 2 10 241 511 451 161 cavecow1.out 4

(先吃 5,再吃 3,再吃 2,最后走回 1,吃 掉 1 上的最后一份食物)

第39题 打扫食槽 (Cleaning Up, USACO 2009 Mar)
从前奶牛是不挑食的,但现在世道变了,她们变得非常挑剔。牧场里有N头奶牛,约翰 要向她们提供M种食物,第i头奶牛只会吃Pi 号食物。 约翰每天都要打扫食槽,这件事非常累。奶牛沿着食槽排成一条直线,约翰在打扫时, 可以将食槽分割成若干个区间,如果一段区间中有K种不同的食物,那么这段区间打扫的时 间就是K 2 。请帮助约翰计划一下,怎么样才能使打扫整个食槽的时间最少。

输入格式
? ? 第一行:两个用空格分开的整数:N和M,1 ≤ M ≤ N ≤ 40000 第二行到N + 1行:第i + 1行有一个整数Pi ,1 ≤ Pi ≤ M

输出格式
? 第一行:单个整数,表示约翰完成打扫的最短时间

样例
cleanup.in 13 4 1 2 1 3 2 2 3 4 3 4 3 1 4 cleanup.out 11

(前四头奶牛各成一段,第五段里有两头喜 欢 2 的奶牛, 第六段中的奶牛分别喜欢 3, 4, 3,4,3,最后两段每段只有一头奶牛, 1 × 4 + 1 + 4 + 1 × 2 = 11)

第40题 购买饲料 (Buying Feed, USACO 2010 Nov)
如约翰在镇上,沿着公路开车回家,他的家离起点有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 + 4 = 5,花在商店的钱是2 + 2 = 4,共需要9元。

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

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

样例
feed.in 253 312 412 111 feed.out 9

(数据说明见题面)

第41题 土地并购 (Land Acquisition, USACO 2008 Mar)
约翰准备扩大他的农场,眼前他正在考虑购买N块长方形的土地。如果约翰单买一块土 地,价格就是土地的面积。但他可以选择并购一组土地,并购的价格为这些土地中最大的长 乘以最大的宽。比如约翰并购一块3 × 5和一块5 × 3的土地,他只需要支付5 × 5 = 25元, 比单买合算。 约翰希望买下所有的土地。他发现,将这些土地分成不同的小组来并购可以节省经费。 给定每份土地的尺寸,请你帮助他计算购买所有土地所需的最小费用。

输入格式
? ? 第一行:一个整数:N,1 ≤ N ≤ 50000 第二行到第M + 1行:第i + 1行有两个整数,分别代表第i块土地的长度Hi 和宽度Wi , 1 ≤ Hi , Wi ≤ 106

输出格式
? 第一行:购买所有土地所需的最小费用

样例
acquire.in 4 100 1 15 15 20 5 1 100 acquire.out 500

(分三组:第一组100 × 1,第二组1 × 100, 第三组是20 × 5和15 × 15,每组的价格分别 为100、100和300)

第42题 干草塔 (Tower of Hay, USACO 2009 Open)
为了调整电灯亮度,贝西要用干草包堆出一座塔,然后爬到牛棚顶去把灯泡换掉。干草 包会从传送带上运来,共会出现N包干草,第i包干草的宽度是Wi ,高度和长度统一为1。干 草塔要从底层开始铺建。贝西会选择最先送来的若干包干草,堆在地上作为第一层,然后再 把紧接着送来的几包干草包放在第二层, 再铺建第三层……重复这个过程, 一直到所有的干 草全部用完。每层的干草包必须紧靠在一起,不出现缝隙,而且为了建筑稳定,上层干草的 宽度不能超过下层的宽度。 按顺序运来的干草包一定要都用上, 不能将其中几个干草包弃置 不用。贝西的目标是建一座最高的塔,请你来帮助她完成这个任务吧。

输入格式
? ? 第一行:单个整数:N,1 ≤ N ≤ 100000 第二行到N + 1行:第i + 1行有一个整数Wi ,1 ≤ Wi ≤ 10000

输出格式
? 第一行:单个整数,表示可以建立的最高高度

样例
tower.in 3 1 2 3 tower.out 2

(将 1 和 2 放在第一层,将 3 放在第二层)

第43题 明星奶牛 (Popular Cows, USACO 2003 Fall)
每头奶牛都梦想成为牛棚里的明星。 被所有奶牛喜欢的奶牛就是一头明星奶牛。 所有奶 牛都是自恋狂,每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果A喜 欢B,B喜欢C,那么A也喜欢C。牛栏里共有N 头奶牛,给定一些奶牛之间的爱慕关系,请你 算出有多少头奶牛可以当明星。

输入格式
? ? 第一行:两个用空格分开的整数:N和M,1 ≤ N ≤ 10,000,1 ≤ M ≤ 50,000 第二行到第M + 1行:每行两个用空格分开的整数:A和B,表示A喜欢B

输出格式
? 第一行:单独一个整数,表示明星奶牛的数量

样例
popular.in 33 12 21 23 popular.out 1

(只有 3 号奶牛可以做明星)

第44题 电子游戏 (Video Game Troubles, USACO 2009 Dec)
约翰的奶牛们玩游戏成瘾! 本来约翰是想把她们拖去电击治疗的, 后来他发现奶牛们在 生产了更多的牛奶,也就开始支持她们了。 但是, 奶牛在选择游戏平台上的分歧很大: 有的奶牛想买一台 Xbox 360 来跑 《光晕 3》 ; 有的奶牛想要一台任天堂 Wii 来跑《明星大乱斗 X》 还有的奶牛想要在 PlayStation 3 上玩 ; 《潜龙谍影 4》 。看来约翰要做一些选择才行。 已知市面上有N种平台,如果想玩第i种平台的游戏,必须先买一台该平台上的游戏机, 价格为Pi 。第i种平台上有Gi种游戏,其中第j个游戏的价格为GPi,j ,奶牛玩过该游戏后的牛奶 产出为PVi,j .如果想玩同一平台上的多个游戏,只要买一台游戏机就够了。 假设约翰的总预算不能超过V。请帮他考虑一下,购买哪些游戏机和游戏,才能使奶牛 产奶的效益最大?注意一个游戏玩两次是不会有双倍效益产生的。

输入格式
? ? 第一行:两个用空格分开的整数N和V,1 ≤ N ≤ 50,1 ≤ V ≤ 106 第二行到第N + 1行:第i + 1行描述了第i个游戏平台。首先是Pi 。接着是Gi,其次有Gi对 整数GPi,j 和PVi,j ,1 ≤ Pi ≤ 1000,1 ≤ Gi ≤ 10,1 ≤ GPi,j ≤ 100,1 ≤ PVi,j ≤ 106

输出格式
? 第一行:单个整数,表示约翰可以得到的最高产出

样例
vidgame.in 3 800 300 2 30 50 25 80 600 1 50 130 400 3 40 70 30 40 35 60 vidgame.out 210 (购买第一种游戏机上的第二个游戏和第三 种游戏机上的第一、第三个游戏,预算为 300 + 25 + 400 + 40 + 35 = 800 , 收 益 为 80 + 70 + 60 = 210)

第45题 产奶比赛 (Milk Team Select, USACO 2006 Mar)
约翰的N头奶牛报名去参加世界产奶大奖赛 (Multistate Milking Match-up, 简称 MMM) 。 这是一项组队赛,队伍的人数任意,约翰的第i头奶牛可以为集体贡献Ci 的牛奶。注意有些 奶牛会帮倒——弄翻其他奶牛的牛奶桶,所以Ci可能是负的。所有参加比赛的奶牛毫无疑问 都是女士,记第i头奶牛的母亲为Pi ,如果她的母亲没有报名,Pi 就等于零。 约翰很清楚对手的实力, 确信只要自己队伍产出的牛奶不少于X, 就一定能够赢得比赛。 MMM 举办的目的之一,是通过竞赛中的合作来增进奶牛家庭成员之间的默契。奶牛们觉得 既然自己稳操胜券, 为了表示对大赛精神的支持, 她们希望派出的队伍里多出现一些母女组 合。请挑选出一只能赢得比赛的队伍,使得其中奶牛的母女关系数目最多。如果一头奶牛和 她的母亲、外祖母组成一只队伍,这只队伍算作有两对母女关系。

输入格式
? ? 第一行:两个用空格分开的整数:N和X,1 ≤ N ≤ 500,1 ≤ X ≤ 107 第二行到N + 1行:第i + 1行有两个用空格分开的整数,表示Ci和Pi 。?10000 ≤ Ci ≤ 10000,0 ≤ Pi ≤ N,保证输入数据中的母女关系不会出现循环

输出格式
? 第一行:单个整数,表示母女关系的最大数,如果无法选出一支优胜队伍,输出?1

样例
tselect.in 58 -1 0 31 51 -3 3 20 tselect.out 2

(选1,2,3,5。她们的产出为(?1) + 3 + 5 + 2 = 9 ≥ 8。这支队伍里有两对牛有血缘 关系(1 ? 2和1 ? 3) 。如果选2,3,5,虽然 产奶量更高, 但这个队伍的母女关系数为零)

第46题 黄金莲花池 (Lilypad Pond, USACO 2007 Feb)
为了让奶牛们娱乐和锻炼,约翰建造了一个美丽的池塘。这个池塘是矩形的,可以分成 M × N个方格。一些格子是坚固得令人惊讶的莲花,还有一些是岩石,其余的只是美丽、纯 净、湛蓝的水。 贝西正在练习芭蕾舞,她站在一朵莲花上,想跳到另一朵莲花上去,她只能从一朵莲花 跳到另一朵莲花上,既不能跳到水里,也不能跳到岩石上。 贝西的舞步很像象棋中的马步:每次跳跃可以横移 2 格,纵移 1 格,或纵移 1 格,横移 2 格,最多有八个方向可供移动选择。 约翰一直在观察贝西的芭蕾练习, 发现她有时不能跳到终点, 因为中间缺了一些必要的 莲花。 约翰可以多种一些莲花来帮助贝西到达终点。 不过要注意有石头的格子是不能种莲花 的。 约翰想帮助贝西完成任务, 但一贯吝啬的他只想添加最少数量的莲花, 请帮助约翰确定 至少要添加几朵莲花,其次,确定放置这些莲花有多少种不同的方法。

输入格式
? ? 第一行:两个用空格分开的整数:M和N,1 ≤ M, N ≤ 30 第二行到M + 1行:第i + 1行有N个用空格分开的整数,描述了池塘第i行的状态:0 为 水,1 为莲花,2 为岩石,3 为起点,4 为终点。

输出格式
? ? 第一行:一个整数,表示需要增加的最少莲花数,如果无解则输出-1 第二行:一个整数,表示放置莲花的方案数,输入数据保证这个数字小于263,如果前 一行是-1,不必输出这行

样例
lilypad.in 45 10000 30000 00200 00040 lilypad.out 2 3 ( 最少 2 朵莲花,有 3 种方式,x 为莲花位置: 10000 10X00 10X00 30X00 30000 3000X 00200 0X200 00200 0X040 00040 00040 )

第47题 逢低吸纳 (BUY LOW, BUY LOWER, USACO Feb 2002)
“逢低吸纳” 这条建议是奶牛在股市取得成功的一条基本原则。 想要做个伟大的投资者, 你必须遵循一个伟大的守则: “逢低吸纳!跌得越多就要买得越多! ” 如果遵守这条守则, 你每次买股票的价格必须低于上次的买价。 如果预知一段时间内股 票的价格,在上述守则下,最多可以买多少次股票呢? 举例来说,假设某支股票走势如下: 2 3 4 5 6 7 8 9 10 11 12 日期 1 69 54 64 68 64 70 67 价格 68 “最优秀”的投资者可以买四次,其中的一种方案是: 5 6 10 日期 2 68 64 价格 69 另外还有个方案是 5 8 日期 2 62 10 78 62 98 87

68 67 62 价格 69 这两个方案是不同的,因为他们的成交价格不同。如果两个方案只有成交时间不同,成 交价格完全相同, 会认为这两个方案是一样的。 作为优秀的投资者, 你最多可以买几次股票, 最长方案又有多少种不同的情况呢?

输入格式
? ? 第一行:单个整数:N,表示天数,1 ≤ N ≤ 5000 第二行:N个用空格分开的整数,代表当天股票的价格Pi ,1 ≤ Pi ≤ 216

输出格式
? 第一行:两个用空格分开的整数,第一个数表示最多次数,第二个数表示不同的买价序 列数量,保证答案小于231

样例
buylow.in 12 68 69 54 64 68 64 70 67 78 62 98 87 buylow.out 42 (数据说明见题面)

第48题 焊接 (Soldering, USACO 2011 Open)
奶牛决定用电线焊接出一个特殊图形,这个图形是连通的,由N个点,N ? 1条边组成, 每条边的长度都是1。焊接所用的电线要从当地的商店里买。越长的电线越贵,一条长度为 L的电线售价为L2 。 奶牛们已经学会了基本的焊接方法, 她们会把某条电线的一个端点焊接到另一条电线的 中间某个位置, 但她们没有学会如何把两条电线的端点直接焊接起来, 也没有学会怎么把电 线剪断。 告诉你奶牛准备焊接的图形,请告诉奶牛怎么焊接才能最节约材料费用。

输入格式
? ? 第一行:单个整数N,1 ≤ N ≤ 50000 第二行到N行: 每行有两个用空格分开的整数A和B, 表示图形中的一条边, ≤ A ≤ N, 1 1≤B≤N

输出格式
? 第一行:单个整数,表示最少的花费,保证这个数字小于263

样例
solder.in 6 12 13 14 15 16 solder.out 7

(由于每个点都和 1 相连,因此,只要购买 一条长度为 2 的电线和三条长度为 1 的电线 即可。总花费为22 + 3 ? 12 = 7)

第49题 旅馆 (Hotel, USACO 2008 Feb)
奶牛们最近的旅游计划,是到苏必利尔湖畔,享受那里的湖光山色,以及明媚的阳光。 贝西是导游,她选中了在湖边的一家著名旅馆。这家旅馆一共有N间客房,都在同一楼层, 顺序一字排开,只需要拉开窗帘,就能见到波光粼粼的湖面。 慕名而来的游客会陆续打电话到旅馆前台, 要求订一段连续的房间。 如果能够满足客户 的要求,旅馆总会尽量满足,但如果目前没有连续的空房,前台会向他们道歉,请顾客们另 找一家宾馆。如果有多处连续的空房,前台会挑选编号靠前优先分配。 同时,前台也会收到退房的请求,退房请求也是一段连续的房间。但有时客户会搞错, 报出的区间中有些房间本来就是空的,这不要紧,只需要把它们全部登记成空房就可以了。 你的工作,就是写一个程序,帮助前台为旅客安排房间。程序一共需要处理M条请求, 在第一个请求到来前,所有房间都是空闲的。

输入格式
? ? 第一行:两个用空格分开的整数:N和M,1 ≤ N ≤ 50000,1 ≤ M ≤ 50000 第二行到第M + 1行:每i + 1行描述了一个顾客的请求。每行的第一个整数Ti 代表请求 的类型,如果Ti 为1,表示这是一个订房请求,接下来会有一个整数Di ,表示需要的区 间长度。如果Ti 为2,表示这是一个退房请求,接下来会有两个整数X i 和Di ,表示需要 办理退房手续的第一个房间是X i,区间长度是Di ,1 ≤ Di ≤ N,1 ≤ X i ≤ N ? Di + 1

输出格式
? 对每个订房请求,如果这份订单可以满足,输出满足条件的第一个房间的编号,如果不 可以满足,输出 0,每个请求用换行符分开

样例
hotel.in 10 6 13 13 13 13 255 16 hotel.out 1 4 7 0 5

第50题 道路和航线 (Roads and Planes, USACO 2011 Jan)
约翰在外地销售牛奶。这个地方有T个城市,编号为1到T。这些城市间有R条公路和P条 航线。公路都是可以双向通行的,第i条公路连接城市Ai和Bi,过路费为Ci。而航线都是单程 的,第i条航线从城市X i出发,目的地是城市Yi,机票费为Di ,由于航空公司竞争激烈,Di 竟 可能是个负数!此外,由于反恐需要,政府在规划交通的时候曾保证,如果X i到Yi有一条航 线,就不可能从Yi通过其他公路或航线返回X i。 约翰拥有世界上公认的最给力的奶牛, 所有城市的居民都渴望他的牛奶。 约翰已决定将 配送中心设在S城,他想知道将牛奶从S城送到各个城镇的最少费用分别是多少。

输入格式
? ? ? 第一行:四个用空格分开的整数:T,R,P,S,1 ≤ S ≤ T ≤ 25000,1 ≤ P, R ≤ 50000 第二行到R + 1行:每行有三个用空格分开的整数,表示一条公路:Ai,Bi和Ci, 1 ≤ Ai , Bi ≤ T,0 ≤ Ci ≤ 10000 第R + 2行到R + P + 1行:每行有三个用空格分开的整数,表示一条航线:X i,Yi和Di , 1 ≤ X i , Yi ≤ T,?10000 ≤ Di ≤ 10000

输出格式
? 第一行到第T行:第K行有一个整数,表示从S到K的最小开销,如果根本到不了K,输出 “NO PATH”

样例
roadplane.in 6334 125 345 5 6 10 3 5 -100 4 6 -100 1 3 -10 roadplane.out NO PATH NO PATH 5 0 -95 -100 (从 4 开始,走公路到可以 3,从 3 坐飞机 可以到 5,从 4 坐飞机可以到 6,但不可能到 1 或 2)


相关文章:
备考2014年全国高中物理竞赛---MarkingScheme_ ThQ_I_ Mechanics1983
喜欢此文档的还喜欢 USACO试题精选(第一辑) 52页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。...
USACO 2011年1月精英赛铜组试题 洗盘子
4页 1财富值 usaco试题集-第6章 2页 2财富值 usaco第一章试题 200页 1财富值 USACO试题精选(第一辑) 52页 免费 USACO 三月份试题 暂无评价 10页 免费喜欢...
USACO初学1.1.1(ride)试题源程序和测试数据
USACO初学1.1.1(ride)试题源程序和测试数据_IT/计算机_专业资料。Your Ride ...usaco第一章试题 200页 1下载券 USACO试题精选(第一辑) 52页 免费 USACO 2011...
USACO open10金组中文试题
USACO open10金组中文试题_哲学_高等教育_教育专区。Problem 1: 奶牛的跳格子游戏...USACO试题精选(第一辑) 52页 免费 usaco中文译题 94页 2下载券 USACO 三月...
信息学竞赛题库
地址:http://wzioi.wzms.com/usaco/ USACO 题解(lxd 版&Maigo 版) [ 1 ...(4)酷叶总站 For 一起的学子家园:http://www.kuye.cn/ (5)第 20 届...
USACO 2009年11月月赛金、银试题与解析
USACO 2009年11月月赛金、银试题与解析_财会/金融考试_资格考试/认证_教育专区...USACO试题精选(第一辑) 52页 免费 USACO 三月份试题 10页 免费 usaco第一章...
USACO题目Name That Number (namenum)及代码解析
喜欢此文档的还喜欢 usaco第一试题 200页 1下载券U​S​A​C​O...namenum INPUT FORMAT: (file namenum.in) 单独的一行包含一个编号(长度可能从...
递归基础练习题
以下是 USACO contest 上的题目,全是递归 ---...输出格式: * 第一至?行: 每一个输出行包括一个长度...全球冷笑话精选 68份文档 新市场营销法则 助推企业...
noip2010
②【USACO】冲浪时间限制:1000MS 内存限制:65536K 【试题描述】 试题描述】 受到秘鲁的马丘比丘的新式水上乐园的启发,Farmer John 决定也为奶牛们建一 个水上...
更多相关标签:
全国中考试题精选 | 中药学试题精选及答案 | 中考试题精选30套 | c 面试题精选 | 医师实践技能试题精选 | 小学入学测试题精选 | 机械制图精选试题库 | 全国数控大赛试题精选 |