USACO open10金组铜组中文试题

USACO open10试题

金组试题

Problem 1: 奶牛的跳格子游戏[John Pardon, 2010]

奶牛们正在回味童年，玩一个类似跳格子的游戏，在这个游戏里，奶牛们在

草地上画了一行N个格子，(3 <=N <= 250,000)，编号为

1..N。

就像任何一个好游戏一样，这样的跳格子游戏也有奖

励！第i个格子标有一个数字V_i(-2,000,000,000 <=V_i

<= 2,000,000,000)表示这个格子的钱。奶牛们想看看最

后谁能得到最多的钱。

规则很简单：

* 每个奶牛从0号格子出发。(0号格子在1号之前，

那里没钱)

* 她向N号格子进行一系列的跳跃(也可以不跳)，每

次她跳到的格子最多可以和前一个落脚的格子差K格(1

<= K <= N)(比方说，当前在1号格，K=2, 可以跳到2号和3号格子)

*在任何时候，她都可以选择回头往0号格子跳，直到跳到0号格子。另外，除了以上规则之外，

回头跳的时候还有两条规则：

*不可以跳到之前停留的格子。

*除了0号格子之外，她在回来的时候，停留的格子必须是恰巧过去的时候停留的某个格子的前一格(当然，也可以跳过某些过去时候停留的格子)。简单点说，如果i号格子是回来停留的格子，i+1号就必须是过去停留的格子，如果i+1号格子是过去停留的格子，i号格子不一定要是回来停留的格子。(如果这里不太清楚的可以去看英文原文)

她得到的钱就是所有停留过的格子中的数字的和，请你求出最多奶牛可以得到的钱数。

在样例中，K=2，一行5个格子。

格子 编号: 0 1 2 3 4 5

+---+ +---+ +---+ +---+ +---+ +---+

|///|--| |--| |--| |--| |--| |

+---+ +---+ +---+ +---+ +---+ +---+

钱数 : - 0 1 2 -3 4

一个合法的序列Bessie可以选择的是0[0], 1[0], 3[2], 2[1], 0[0]。(括号里的数表示钱数)这样，可以得到的钱数为0+0+2+1+0 = 3。

如果Bessie选择一个序列开头为0, 1, 2, 3, ...，那么她就没办法跳回去了，因为她没办法再跳到一个之前没跳过的格子。

序列0[0], 2[1], 4[-3], 5[4], 3[2], 1[0], 0[0]是最大化钱数的序列之一，最后的钱数为(0+1-3+4+2+0 = 4)。

PROBLEM NAME: hop

INPUT FORMAT:

* 第1行 1: 两个用空格隔开的整数: N 和 K

* 第2到N+1行: 第i+1行有一个整数

: V_i

USACO open10金组铜组中文试题

SAMPLE INPUT (file hop.in):

5 2

1

2

-3

4

OUTPUT FORMAT:

* 第一行: 一个单个的整数表示最大的钱数是多少。

SAMPLE OUTPUT (file hop.out):

4

OUTPUT DETAILS:

还有一种可能的最大化钱数的序列是: 0 2 4 5 3 1 0

********************************************************************* Problem 2: 冲浪 [John Pardon, 2010]

受到秘鲁的马丘比丘的新式水上乐园的启发，Farmer John决定也为奶牛们建一个水上乐园。当然，它最大的亮点就是新奇巨大的水上冲浪。

超级轨道包含 E (1 <= E <=150,000)条小轨道连接

着V (V <= 50,000)个水池，编号为1..V。每个小轨道必

须按照特定的方向运行，不能够反向运行。奶牛们从1

号水池出发，经过若干条小轨道，最终到达V号水池。每

个水池(除了V号和1号之外，都有至少一条小轨道进来

和一条小轨道出去，并且，一头奶牛从任何一个水池到达

V号水池。最后，由于这是一个冲浪，从任何一个水池出

发都不可能回到这个水池)

每条小轨道从水池P_i到水池Q_i (1 <= P_i <= V;

1<= Q_i <= V; P_i != Q_i)，轨道有一个开心值F_i (0

<= F_i <= 2,000,000,000)，Bessie总的开心值就是经

过的所有轨道的开心值之和。

Bessie自然希望越开心越好，并且，她有足够长的时间在轨道上玩。因此，她精心地挑选路线。但是，由于她是头奶牛，所以，会有至多K (1 <= K <= 10)次的情况，她无法控制，并且随机从某个水池选择了一条轨道(这种情况甚至会在1号水池发生)

如果Bessie选择了在最坏情况下，最大化她的开心值，那么，她在这种情况下一次冲浪可以得到的最大开心值是多少？

在样例中，考虑一个超级轨道，包含了3个水池(在图中用括号表示)和4条小轨道，K的值为1

(开心值在括号外表示出来，用箭头标识)

[1]

/ \

5 -> / \ <- 9

/ \ [2]---3---[3]

USACO open10金组铜组中文试题

\__5__/

她总是从1号水池出发，抵达3号水池。如果她总是可以自己选择，就是不会发生不能控制的情况她可以选择从1到2(这条轨道开心值为5)，再从2到3(开心值为5)，总的开心值为5+5=10。但是，如过她在1号水池失去控制，直接到了3，那么开心值为9，如果她在2号水池失去控制，她总的开心值为8。 Bessie想要找到最大化开心值的方案，可以直接从1到3，这样，如果在1号水池失去控制，这样，她就不会在2号水池失去控制了，就能够得到10的开心值。因此，她的开心值至少为9

PROBLEM NAME: slide

INPUT FORMAT:

* 第一行: 三个用空格隔开的整数: V, E, 和 K

* 第2到第E+1行: 第i+1行包含三个用空格隔开的整数:

P_i, Q_i, and F_i

SAMPLE INPUT (file slide.in):

3 4 1

2 3 5

1 2 5

1 3 9

2 3 3

OUTPUT FORMAT:

* 第一样: 一行一个整数表示在最坏情况下最大化的开心值

SAMPLE OUTPUT (file slide.out):

9

********************************************************************

Problem 3：数三角形

在一只大灰狼偷偷潜入Farmer Don的牛群被群牛发现后，贝西现在不得不履行着她站岗的职责。从她的守卫塔向下瞭望简直就是一件烦透了的事情。她决定做一些开发智力的小练习，防止她睡着了。

想象牧场是一个X，Y平面的网格。

她将N只奶牛标记为1 N (1 <= N <=

100,000)，每只奶牛的坐标为X_i,Y_i

(-100,000 <= X_i <= 100,000;-100,000

<= Y_i <= 100,000; 1 <= i <=N)。然

后她脑海里想象着所有可能由奶牛构成

的三角形。如果一个三角形完全包含了

原点(0,0)，那么她称这个三角形为“黄

金三角形”。原点不会落在任何一对奶

牛的连线上。另外，不会有奶牛在原点。

给出奶牛的坐标，计算出有多少个

“黄金三角形”。

USACO open10金组铜组中文试题

顺便解释一下样例，考虑五只牛，坐标分别为(-5,0), (0,2), (11,2), (-11,-6), (11,-5)。

下图是由贝西视角所绘出的图示。

............|............

............*..........*.

............|............

-------*----+------------

............|............

............|............

............|............

............|............

............|..........*.

.*..........|............

............|............

所有十个三角形如图下所示：

通过观察，其中有5个构成了“黄金三角形”

PROBLEM NAME: tricount

INPUT FORMAT:

* 第一行:一个整数: N

* 第2到第N+1行: 每行两个整数X_i，Y_i，表示每只牛的坐标

Sample Input (file tricount.in):

5

-5 0

0 2

11 2

-11 -6

11 -5

OUTPUT FORMAT:

* 第一行: 一行包括一个整数，表示“黄金三角形的数量”

USACO open10金组铜组中文试题

SAMPLE OUTPUT (file tricount.out):

5

*********************************************************************

Translation by zhongtian jiang

铜组题目

********************************************************************* 从11到14一共4道题

*********************************************************************

第11题: 牛友 [传统题目, 2010]

Bessie和其他的所有奶牛的耳朵上都戴有一个射频识别（RFID，不能使用英文缩略词）序列号码牌。因此FJ可以机械化地计算他们的数量。很多奶牛有一个“牛友”：一只奶牛的牛友的序列号刚好等于奶牛自己的序列号的所有约数之和。在这里，一个数的“约数”不包括这个数本身。因为一些奶牛的号码约数和大于其他任何奶牛的号码，所以这些奶牛没有牛友。

一些奶牛有一个“非常好友”。当两个奶牛互为“牛友”时，他们就是一对“非常好友”。注意在这道题中，忽略那些自己是自己的“非常好友”的情况。

给定一个序列号S (6 <= S <= 18,000)，找到序列号不小于S的第一只有“非常好友”的奶牛。

比如说，考虑序列号220，它的约数是1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 和110。和是284。类似的，284的约数是1, 2, 4, 71, 和142。他们的和是220 题目名称: cowpals

输入格式:

* 第1行: 一个单独的整数: S

样例输入 (文件cowpals.in):

206

输出格式:

* 第1行: 单独一行，包含2个由空格隔开的整数。第一个整数表示第一个序列号不小于S的有非常好友的奶牛，第二个整数是他的好友的序列号。 样例输出 (文件cowpals.out):

220 284

*********************************************************************

第12题: 山峰暸望 [Jeffrey Wang, 2009]

一天，Bessie在眺望美丽的威斯康星的群山的时候，她突然产生了疑问：那座山是最宽的捏？

她决定在地平线上，利用她的新大量程山峰高度测量仪依次做N (1 <= N <= 10,000)次高度测量H_i (1 <= H_i <= 1,000,000,000)。

一座山定义为一段连续的高度序列，序列中的高度一开始单调上升（或者不变），然后单调下降（或者不变）。举例来说，2, 3, 3, 5, 4, 4, 1这一段高

USACO open10金组铜组中文试题

度序列就是一座山。如果在她的视线范围内有一段只单调上升或者只单调下降的序列，也算是一座山。

山的宽度定义为在这个山上进行的测量的次数（也就是序列的长度）。请帮Bessie找到最宽的山。

这是一个比较典型的地平线的例子：

******* *

********* ***

********** *****

*********** ********* *

* ***************** *********** *** *

** ******************* ************* * * ******* * ********************************************************************* ?ddsssuussuussssssddddssddssssuuuuuuuuddddddssududssssuuudduddsssssuds3211112333677777776543332111112344456765432111212111112343232111111211aaaaa cccccccccccccccccccc eeeeeee ggggggggg bbbbbbbbbbbbbbbbbbbbbbbbbbbb ddddd ffffffffff hhhhhhhhh 山标记为'a', 'b'等等。显然，山b有着最大的宽度，宽度为28。

悄悄告诉你：如果你知道一座山的最高的部分（也就是山峰），你会发现，找到这座山的宽度是很容易的哦。

题目名称: mount

输入格式:

* 第1行: 一个单独的整数: N

* 第2到第N+1行: 第i+1包含一个单独的整数: H_i

样例输入 (文件 mount.in):

7

3

2

3

5

4

1

6

输入细节:

测量到的高度分别为3, 2, 3, 5, 4, 1, 6.

输出格式:

* 第1行: 一个单独的整数，表示最宽的山的宽度。

样例输出 (文件mount.out):

5

输出细节:

在最宽的山处测量到的高度为2, 3, 5, 4, 1. 其他的山包括3, 2和1, 6。

*********************************************************************

USACO open10金组铜组中文试题

第13题: 接力赛跑 [Jelle van den Hooff, 2010]

N (1 <= N <= 1,000)只奶牛（编号为1..N）在进行一个特别的接力赛跑。这个赛跑中，奶牛能同时跑。

在t=0时刻，每只奶牛在起点线处等待自己起跑的时间。奶牛们会在一个圆形跑道上跑，重点线跟起点线重合。

在t=0时刻，牛1开始沿着跑道跑，L_1秒后跑完一圈重新到达起点线。一般来说，牛i跑完一圈需要的时间为L_i (1 <= L_i <= 1,000)秒。当她重新越过起点线的瞬间，她示意M_1只其它的奶牛立刻旗袍。一般来说，牛i会示意M_i (0 <= M_i <= N)只其它的奶牛A_ij (1 <= j <= M_i)起跑。不管是什么时候被叫到，每只奶牛先慢一定会被其他奶牛示意起跑。注意可能出现M_i为0并且A_i不存在的情况。

每一只被叫到的奶牛起跑。等到它回到起点时，会继续示意其它奶牛起跑。可能出现多支奶牛示意同一只奶牛起跑的情况，但是每一支奶牛只愿意跑一圈。所以它被叫到第二次的时候就不愿意跑了。

农夫John希望你帮他确定总的赛跑时间（也就是从比赛开始到最后一支奶牛越过终点的时间）。

考虑一个只有五只奶牛的小型比赛。下标表示奶牛的编号(i)，跑一圈的时间(L_i)，它跑完一圈会示意起跑的其他奶牛的数目(M_i)，和示意起跑的奶牛（可能为空）的列表(A_ij)。

i L_i M_i A_i*

1 4 2 2 4

2 3 3 1 3 4

3 7 1 5

4 4 2 3 5

5 1 0

由于牛1起跑导致了以下的时间表。

时间 时间

0 牛1起跑

4 牛1跑完一圈; 示意 2和 4

4 牛2起跑(完成赛跑的时间: +3秒 -> 7)

4 牛4起跑(完成赛跑的时间: +4秒 -> 8)

7 牛2跑完一圈; 示意 1, 3,和 4

7 牛1和 4忽略重复信号

7 牛3 starts (完成赛跑的时间: +7秒 -> 14)

8 牛4跑完一圈; 示意 3和 5

8 牛3忽略重复信号

8 牛5 starts (完成赛跑的时间: +1秒 -> 9)

9 牛5跑完一圈 但是不示意其他牛起跑

14 牛3跑完一圈; 示意 5

14 牛5忽略重复信号

14 所有牛完成赛跑

因此，赛跑会持续14秒。

USACO open10金组铜组中文试题

题目名称: relayrace

输入格式:

* 第1行: 一个单独的整数: N

* 第2到第N+1行: 第i+1行包含多个由空格隔开的整数：L_i, M_i和M_i个整数A_ij

样例输入 (文件relayrace.in):

5

4 2 2 4

3 3 1 3 4

7 1 5

4 2 3 5

1 0

输出格式:

* 第1行: 一个单独的整数, 最后一支奶牛结束的时间

样例输出 (文件relayrace.out):

14

*********************************************************************

第14题: 奶牛打字 [Jelle van den Hooff, 2010]

奶牛最近发现了一个神奇的东西，叫做电子邮件。他们很享受跟农夫John接受邮件的过程。但困难是，奶牛们用它们的蹄子要在一般的电脑键盘上打字比较困难。福气的是农夫John开发了一个先进的奶牛输入系统。

系统包含4个大按键和一个屏幕。按键上面标着“上一个”“下一个”“放上去”“打进去”。奶牛选择字母输入以组成单词而不是直接打进字母。其实呢，奶牛打字的时候啊，是只用大写字母的。也许很多人不相信，但是他们确实这样做。

FJ是一个聪明的家伙。他知道奶牛只会用他们懂的词语（一个已经发现的词语列表，一个一行，在文件'dict.txt'中）。没有一个单词超过20个字母，不超过25000个单词。真正测试用的词典在

http:///usaco/dict.txt中。

屏幕上由两行:

* 目前单词已经输入的的部分

* 一个可能的下一个字母的列表，其中一个字母高亮。

奶牛们用“下一个”“上一个”按键来把高亮移动到列表的下一个或者上一个字母上面。列表是循环的，第一个字母的上一个字母是最后一个字母。

列表只包含可能的下一个字母，以减轻奶牛的劳动。因为B开头的单词的第二个字母不可能是D，因此可以把这个可能性排除在列表外。

当一个单词已经输入的部分是空的，列表就包含所有可能的单词的首字母。比如说，如果一个小型的词典只有4个单词('ACE', 'APPLE', 'BANANA', 和'PEAR'), 因此按键就可以在'A', 'B', 和'P'中循环(从'A'开始)。

当奶牛按“放上去”的时候，高亮的字母会被加到当前已经输入的部分的后面，然后可能的下一个字母的列表会立刻更新。比如上个自然段中的例子，如果

USACO open10金组铜组中文试题

输入'A'，然后单词首字母确定，那么可能的下一个字母就将会是'C'和'P'，热切因为'C'字典序考前，所以'C'高亮。

当按下“打进去”的时候，屏幕上的单词就会被打到电子邮件之中，然后就会重复输入单词的过程。

用那个包含四个单词的词典，下表表示输入打"apple"的过程（*A*表示A高亮）：

操作 WORD 可能的单词

[初始] _________ *A* B P

ADD A________ *C* P

NEXT A________ C *P*

ADD AP_______ *P*

ADD APP______ *L*

ADD APPL_____ *E*

ADD APPLE____

PRINT _________ *A* B P

注意！这个只用按7次按键，只比用普通键盘多2次（如果要空格那就再多一次）！

农夫John不想要奶牛太累，所以想要知道奶牛们发送一个简单的只包含N（1 <= N <= 20）个单词电子邮件需要按多少次按键。

题目名称: typing

输入格式:

* 第1行: 一个单独的整数: N

* 第2到第N+1行: 每一行包括一个需要打进去的单词。

样例输入 (文件 typing.in):

5

HELLO

FARMER

HOW

ARE

YOU

输入细节:

一个包含五个单词的信息"HELLO FARMER HOW ARE YOU"

输出格式:

* 第1行: 输出一个单独的行，包含一个单独的数字，奶牛需要按键的次数。 样例输出 (文件 typing.out):

92

输出细节:

一共按92下: 拍HELLO 27下, FARMER 22下, HOW 16下, ARE 17下，YOU 10下。

********************************************************************* Translation by Sinya Lee