tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

USACO月赛2011MAR


USACO 2011
MAR Gold
布朗尼切片(brownie)
Bessie 烘焙了一块巧克力蛋糕。这块蛋糕是由 R*C(1 <= R,C <= 500)个小 的巧克力蛋糕组成的。第 i 行,第 j 列的蛋糕有 N_ij(1 <= N_ij <= 4,000)块 巧克力碎屑。 Bessie 想把蛋糕分成 A*B 块,(1

<= A <= R,1 <= B <= C): 给 A*B 只奶牛。 蛋糕先水平地切 A-1 刀(只能切沿整数坐标切)来把蛋糕划分成 A 块。然后再把 剩下来的每一块独立地切 B-1 刀,也只能切沿整数坐标切。其他 A*B-1 只奶牛就 每人选一块,留下一块给 Bessie。由于贪心,他们只会留给 Bessie 巧克力碎屑 最少的那块。 求出 Bessie 最优情况下会获得多少巧克力碎屑。 例如,考虑一个 5*4 的蛋糕,上面的碎屑分布如下图所示: 1 2 2 1 3 1 1 1 2 0 1 3 1 1 1 1 1 1 1 1 Bessie 必须把蛋糕切成 4 条,每条分成 2 块。Bessie 能像这样切蛋糕: 1 2 | 2 1 --------3 | 1 1 1 --------2 0 1 | 3 --------1 1 | 1 1 1 1 | 1 1 因此,其他贪得无厌的牛拿完后,Bessie 仍能够拿走 3 个巧克力碎屑。 【输入格式】: * 第 1 行: 四个空格隔开的数: R, C, A ,B * 第 2-R+1 行: 第 i+1 行有 C 个整数, N_i1 , N_i2 .. N_iC 【样例输入】 (brownie.in):

5 4 4 2 1 2 2 1 3 1 1 1 2 0 1 3 1 1 1 1 1 1 1 1 【输出格式】: * 第 1 行: 一个整数: Bessie 保证能拿到的最多碎屑数 【样例输出】 (brownie.out): 3

图形发现(gdisc)
贝西给农民约翰出了一个谜。他面前是一个湖,湖上有 N(1 <= N<=40)个 小岛屿,岛屿之间驾着一些桥梁。贝西同意告诉 FJ,是否有可能安全地从任何 岛屿到其他任何一个岛屿不使用一组指定的桥梁。 也就是说,如果我们把岛屿看做图,桥梁看做边,然后贝西告诉 FJ 是否 N 个顶点全部链接(取出指定的边集后) (保证初始图形连接) 。 FJ 想确定哪些桥梁是确实存在的。帮助 FJ 解决这个问题使用尽可能少的问 题(见下文评分程序的详细说明) 。 贝茜和 FJ 之间对话的一个例子如下, 假设图里 4 个顶点构成的边是{{1,2},{1,3},{1,4},{2,3}} (下图所示) : 1--2 |\ | | \| 4 3 FJ 的问题 | Bessie 的回应 | 解释

--------------------------------------------------------{{1,2}} | Yes | {{3,4}} | Yes | {{1,4}, {4,3}} {{1,2}, {2,3}} {{1,2}, {3,1}} {{1,3}} | | | | No No No Yes | {1,4} 一定是 | {2,3} 一定是 | {1,3} 一定是 | {1,2} 一定是

{{1,4}}

|

No

| {2,4} 和{3,4} 不是

FJ 可以得出结论:该图的边是{{1,2},{1,3},{1,4},{2,3}},并没有其 他的。 此问题是反应性的问题,这意味着,而不是读取和写入到一个文件中,您将使用 stdin 和 stdout(换句话说,用控制台输入和输出)与平地机程序。 也就是说,这是一个交互式问题 所以此题没有样例

树装饰(tdec)
农夫约翰正装饰他的春分树(像圣诞节树,但大约三个月后流行) 。它可以建模 为一个有根的数学树,有 N(1 <= N <=100,000)个节点,标记为 1...N,1 是 树的根。每个节点 e> 1 有一个父亲 P_E(1<= P_E<= N) 没有父亲(在输入里 。1 表示为“-1”。 ) 每个节点 i 有一个相应的子树的(可能大小为 1)以它为根。 FJ 想确保相应的 子树 i 至少有饰品 C_i(0 <= C_i<= 10,000,000)挂在它的节点上。他还想尽 量减少挂饰品的时间(在 i 上放 K 个饰品需要时间 K* T_i(1 <= T_i<= 100)。 ) 帮助 FJ 确定花费时间的最小量。请注意,这个答案可能需要 64 位整数来存储。 例如下面这棵树 1 | 2 | 5 / \ 4 3 假设,FJ 具有以下的子树的约束: 子树上最少要挂多少饰品 | | 子树的根 | C_i | 时间消耗 | T_i

--------+--------+------1 | 9 | 3 2 | 2 | 2 3 | 3 | 2 4 | 1 | 4 5 | 3 | 3 FJ 可以将所有的装饰品挂上,如下图所示,总共花费 20: 1 [0/9(0)] | subtree(node install time)] 2 [3/9(6)] | 5 [0/6(0)] / \ [1/1(4)] 4 3 [5/5(10)] 【输入格式】: *第 1 行:一个整数:N *第 2.. N +1 行:第 i+1 包含三个空格分隔的整数:P_I,c_i,T_i

【样例输入】(tdec.in): 5 -1 93 1 2 2 5 3 2 5 1 4 2 3 3 【输出格式】: *第 1 行:一个整数:所需最短的时间

【样例输出】(tdec.out): 20

Sliver

会场(meetplace)
Bessie 和 JoNell 是好基友。由于 FJ 每天打乱奶牛吃草的地方,有时他们离 对方很远,因此无法聊天。 FJ 农场里的牧场和路径,形成“树”结构。每个牧场恰好有一个不同的路径 连接一个其他的牧场,每个牧场(除了 1 号牧场,也就是根节点) ,有且仅有一 个父节点。 Bessie 和 JoNell 决定他们将总是在他们的最近公共祖先的牧场见面。 FJ 创建了一张地图包括他的 N(1<= N<=1,000)个牧场(编号为 1 至 N) ,并 告诉你他们的父亲节点 P_I(1<= P_I<= N) ,除了 1 号牧场因为它没有父节点。 FJ 发布了他未来 M(1<=M<=1,000)天的每日放牧时间表,所以 Bessie 和 JoNell 正在决定他们每天应该在哪里聊天。 第 K 天,Bessie 在牧场 B_k(1 <=b_k<= N) ,JoNell 在牧场 J_k(1 <= J_k<= N) 。 给你地图和时间表,帮助 Bessie 和 JoNell 找到他们的碰头地点。 例如,考虑下面的农场布局:

牧场 [1] --------/ | \ 1 / | \ 2 [2] [3] [6] 3 / | \ 4 / | \ 5 [4] [8] [9] 6 / \ 7 / \ 8 [5] [7] 9

父节点 -----------------1 1 2 8 1 8 6 6

以下是 Bessie 和 JoNell 6 天的放牧地点以及他们会选择的碰头地点 Bessie -------2 4 1 4 7 9 Jonell -------7 2 1 1 5 5 碰头地点 --------------1 2 1 1 8 6

【输入格式】: * 第一行: 用空格隔开的两个数字: N 和 M * 第 2..N 行: 第 i 行 P_i * 第 N+1..N+M 行: 第 k+N 行:B_k 和 J_k 【样例输入】 (meetplace.in): 9 1 1 2 8 1 8 6 6 2 4 3 4 7 9 6

7 2 3 1 5 5

【输出格式】: * 第 1..M 行:第 j 行输出第 j 天的碰头地点 【样例输出】 (meetplace.out): 1 2 3 1 8 6

传递包裹(packdel)

农夫约翰必须送一个包裹给农民丹,正准备开始他的旅程。为了维持和平, 他给路上遇到的每头牛一个好吃的东西,当然,FJ 为了节俭想尽可能少遇到牛。 FJ 绘制了一张有 N <= N <= 50,000) (1 个谷仓的地图, M 由 (1<= M<=50000) 条双向路径连接,每条路上有 C_i(0 <=C_i<=1,000)头奶牛。一条路连接两个 不同的谷仓:A_i 和 B_i(1 <= A_I<= N<= B_i<= N; A_i!= B_i,。两个谷仓间可 ) 能有一条以上的路径直接连接。FJ 目前在谷仓 1,农民丹在谷仓 N. 考虑下面的地图: [2]--/ | \ /1 | \ 6 / | \ [1] 0| --[3] \ | / \2 4\ | /4 [6] \ | / /1 [4]-----[5] 3 农民约翰的最佳路径是从 1 - > 2 - >4 - >5 - >6, 因为这会花费他 1+0+3+1= 5 个食 物。 告诉你 FJ 的地图,他最少应该带多少食物?他并不关心他的旅程的长度。 【输入格式】 : *第 1 行:两个用空格隔开的整数:N 和 M *第 2.. M +1:三个用空格隔开的整数:A_I,B_i,C_i 【样例输入】 (packdel.in) : 6 8 4 5 3 2 4 0 4 1 4 2 1 1 5 6 1 3 6 2 3 2 6 3 4 4 【输出格式】 : *第 1 行:最低数量的对待,FJ 必须携带 【样例输出】 (packdel.out) : 5

牛桥战役(rotsym)
农民约翰的 N(4<= N<=1,000)头奶牛都在主牧场上耐心等待。奶牛 i 的位 置 是 整 数 坐 标 ( X_i , Y_i )( -1,000,000,000<= X_i<=1,000,000,000 ; -1,000,000,000<=Y_i<= 1,000,000,000) 。 奶牛希望形成分成四人一组来玩 Bridge,他们的新喜欢上的纸牌游戏。每个 组都必须满足一个重要的约束: 四头母牛允许组队,当且仅当在平面上的某些地 方存在一些 X 点(不能跟任何一个潜在的四人组中四点重合) ,使得绕 X 点旋转 这组中的任意一只牛 180 度能和这组的另外一只牛重合。 请帮助奶牛确定最多能够找出几个 Bridge 组。 举例来说,假设 8 头奶牛正站在 8 点:

| f* | a = (-3, 1) b* | b = (-2, 2) a e | c = (-3, 0) * * | d = (-2, 0) c d | g h ---------*--*-----+-----*--*--------|

e f g h

= = = =

(-1, ( 0, ( 2, ( 3,

1) 3) 0) 0)

解释一下,其实就是让你在图里找有几个平行四边形。 有 3 组合法解{A,B,E,D}(绕点(-2,1)旋转){B,C,E,F}(绕点(-1.5, 1.5),{C,D,G,H}(绕(0,0)。 ) ) 【输入格式】 : *第 1 行:一个整数:N *第 2.. N +1:第 i +1 行包含两个用空格隔开的整数:X_i 和 Y_i 【样例输入】 (rotsym.in) : 8 -3 0 -2 0 -1 1 03 20 -3 1 30 -2 2 【输出格式】 :

*第 1 行:一个整数,可以找到多少组。 【样例输出】 (rotsym.out) : 3

BRONZE
幸运护身符(charms)

贝西有一个可爱的小饰物手链长度为 L(4<= L <=32,768)毫米。手链上挂 着 C(1<= C <=512)个护符, 每一个距离手链的左侧都有一个唯一的整数距离。 护符 i 是一个长度为 S_I 毫米 (1<= S_I<=25) 的串, 距离手链左侧 P_I 0 <= ( P_I<= L)mm。 玛格丽特从贝茜那抢走了手链,并用一个 0 宽度的钉子钉在了栅栏上。钉子 在手链 Nmm(1 <= N<= L-1)处,手链的左右两边就因重力挂了下来。 贝茜好奇:每个护符距离钉子多远? 【输入格式】 : *第 1 行:三个用空格隔开的整数:L,C 和 N *第 2.. C+1:第 i +1 行 两个描述护符的整数:S_I 【样例输入】 (charms.in) : 16 3 5 44 79 3 16 【输出格式】 : *第 1..C 行:第 i 行包含护符 i 到钉子的距离

P_I

【样例输出】 (charms.out) : 5 11

14

寻路(pathfind)
贝西被困在一个荒凉的北极岛屿, 她可以用小船乘着海流用 1 单位时间从一 个岛移动到另一个岛 她得到了一个海洋地图, N 有 (1 <= N <= 100) 条单向海流航线, 编号为 1 .. N。 告诉你她的起始位置,M(1 <= M <= N)和地图,帮助贝西确定到达每个 岛的最短时间是多少。 输入为一个矩阵 C,第 r 行,第 c 列的值若为 1,则 r 到 c 存在海流,值为 0 则不存在海流。 【输入格式】 : *第 1 行:两个用空格隔开的整数:N 和 M *第 2 .. N +1:第 i +1 行包含 N 个用空格隔开的整数:C_R 【样例输入】 (pathfind.in) : 41 0101 0010 0001 0000 【输出格式】 : *第 1 ..??行:第一行输出 M,第 i +1 行包含时刻 i 能到达的岛屿(升序排列) 【样例输出】 (pathfind.out) : 1 24 3

螺旋步行(spiral.out)

贝西在 N*N 的广场上漫步, 她想要从左上角经过最长的路到达中心(当 N 为 偶数时,到达中心附近),穿过广场的每一格。

她已决定走顺时针螺旋路线(例如下图) 。写一个程序来画出走的路线 例如,大小为 N=3 和 N= 4 的广场,贝西路线应该使用: 1 2 3 1 2 3 4 8 9 4 12 13 14 5 7 6 5 11 16 15 6 10 9 8 7

【输入格式】 : *第 1 行:一个整数:N 【样例输入】 (spiral.in) : 3 【输出格式】 : *第 1.. N 行:N 个用空格隔开的整数 【样例输出】 (spiral.out) : 123 894 765

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

之和最高,而且不会罢工呢? 【输入格式】 : *第 1 行:两个用空格隔开的整数:N 和 K *第 2.. N +1 行:第 i +1 行包含单个整数:E_i 【样例输入】 (mowlawn.in) : 52 1 2 3 4 5 【输入详细信息】 : FJ 有 5 头牛的效率是 1,2,3,4,5。他想选择一些奶牛,这样他们的总效率最 大化,但他不能选择连续 2 个以上奶牛。 【输出格式】 : *第 1 行:一个整数,最高的总效率 【样例输出】 (mowlawn.out) : 12 【输出详细信息】 : FJ 选择除了 3 之外所有的奶牛。因此,奶牛总效率 1 + 2+ 4 + 5= 12。

奇度(oddd)

奶牛国家被入侵!他们的共和国包括 N(1 <= N <=50,000)个城镇,M(1<= M <=100,000)条无向路连接两镇 A_i 和 B_i(1 <= A_I<= N,1<= B_i<= N;A_I!= B_i;不会出现重复路径) 。然而,共和国不一定是联通的 - 有可能一对城镇无 法通过任何路径连接。 奶牛知道他们的侵略者计划清点她们的路径,所以他们想关闭一些路径,来阻止 侵略者这样做。 请帮助奶牛找到一种方式来关闭一个路径集合,使得每个镇连接奇数条路径,或 者确定是否不存在这样的方式。 例如,考虑以下牛共和国:

1---2 \ / 3 --- 4 如果我们保留路径 1-3,2-3,3-4,并删除路径 1-2,然后城镇 1,2,4 将是一个 路径的端点,而城镇 3 将是三个路径的一个端点: 12 \/ 3 --- 4 【输入格式】 : *第 1 行:两个用空格隔开的整数:N 和 M *第 2.. M+1 行:第 i +1 行包含两个用空格隔开的整数:A_I 和 B_i 【样例输入】 (oddd.in) : 44 12 23 31 34 【输出格式】 : *第 1 行:一个整数,保留下路径的数目。如果无解,输出-1 *第 2.. K+1:每行包含一个保留下来的路径,输出编号。 【样例输出】 (oddd.out) : 3 2 3 4

焊接(solder)
奶牛决定用电线焊接处一个特殊图形,这个图形是联通的,由 N 个点,N-1 条边 组成,每条边的长度都是 1。焊接所用的电线要从商店里买。越长的电线越贵, 一条长度为 L 的电线售价为 L*L。 奶牛们已经学会基本的焊接方法, 他们会把某条电线的一个端点焊接到另一条电

线的中间某个位置, 但他们没有学会如何把两条电线的端点直接焊接起来,也没 有学会剪断电线。 告诉你奶牛准备焊接的图形,告诉奶牛怎么焊接最节约材料费用。 【时间限制】 秒 :2 【空间限制】 :64MB

【输入格式】 : *第 1 行:一个整数:N (1 <= N <= 50,000) 对于 50%的数据 N<=2000

*第 2.. N 行:两个用空格隔开的整数,描述一条边连接 A 和 B (1 <= A <= N; 1 <= B <= N; A != B). 【样例输入】 (solder.in) : 6 12 13 14 15 16 【输出格式】 : *第 1 行:一个整数,焊接成本。 请注意,这个数字可能并不总是适合一个 32 位的整数。 【样例输出】 (solder.out) : 7 【输出细节】 : 由于该结构中的所有节点连接到节点 1,我们只需要买一根导线长度为 2 和 3 条 长度为 1,总成本为 2 * 2+1 * 1+1* 1+1* 1= 7。

Sliver
玉米迷宫(cornmaze)

刚刚过去的这个秋天,农民约翰参观了奶牛的玉米迷宫。但 这不只是普通的玉米迷宫,它有一些传送点,传送点由一对点组成,可以让奶牛 瞬间从一个瞬移点传送到另一头。传送点可以双向传送。 玉米迷宫的外侧除了出口之外全是玉米。 迷宫可以表示为一个 N×M(2 <= N <= 300; 2 <= M<= 300)的网格。每个 网格元素包含这些项目之一: *玉米(玉米网格元素不可穿过) *草(容易通过! ) *传送点(将运送一头牛到其他端点) *出口 奶牛在一个单位的时间内只能向相邻的四个方向移动一格, 但是通过传送点 传送不消耗时间,即消耗时间 0。 “#”表示玉米, “.”表示草地, “@”表示贝西的起始位置, “=”表示出口, “A”至“Z”中的一对大写字母成对出现,代表一对传送点 贝西迷路了。她知道她现在在哪里,请你帮助她用最短的时间走出去。 请考虑以下的网格,其中有 N = 5 和 M = 6: ###=## #.W.## #.#### #.@W## ###### 这最少需要 3 单位时间才能出去 【输入格式】 : *第 1 行:两个空格隔开的整数:N 和 M *第 2.. N +1 行:第 i +1 行描述第 i 行的迷宫:M 个字符(无空格) 【样例输入】 (cornmaze.in) : 5 6 ###=## #.W.## #.#### #.@W## ###### 【输出格式】 : *第 1 行:一个整数,贝西退出迷宫的最短时间。

【样例输出】 (cornmaze.out) : 3

奶牛跳棋(cow checkers)

一天,Besssie 准备和 FJ 挑战奶牛跳棋游戏。这个游戏上在一个 M*N ( 1<=M<=1,000,000;1<=N<=1,000,000 ) 的 棋 盘 上 , 这 个 棋 盘 上 在 ( x,y ) (0<=x<M,0<=y<N)这个坐标上放有一颗棋子。棋盘的左下角是(0,0)坐标,棋 盘的右上角是坐标(M-1,N-1) 。Bessie 每次都是第一个移动棋子,然后 Bessie 与 Fj 轮流移动。每一轮可以做以下三种中的一种操作: 1)在同一行,将棋子从当前位置向左移动任意格; 2)在同一列,将棋子从当前位置向下移动任意格; 3)将棋子从当前位置向下移动 k 格再向左移动 k 格(k 为正整数,且要满足移 动后的棋子仍然在棋盘上) 第一个不能在棋盘上移动的人则输出(因为棋子处在(0,0)点) 。共有 T 个 回合(1<=T<=1,000),每次给出一个新起始点的坐标(x,y),确定是谁赢。 【输入格式】 : 第一行:两个用空格隔开的整数 M 和 N; 第二行:一个整数 T; 第 3 到第 T+2 行:两个用空格隔开的整数 x 和 y. 【输入样例】 : 33 1 11 【输出格式】 : 第 1 到 T 行:包含“Farmer John”或者是“Bessie” ,表示谁赢了这轮游戏。 【 输出样例】 Bessie :

忘记密码(forgot)
发生了这么多,贝茜已经忘记了她 cowtube 密码。然而,她记得一些有用的 信息。 首先,她记得她的密码(记为变量 P)长度为 L(1 <= L<=1,000)罗马字符,

并 可 以 被 分 成 一 个 或 多 个 词 ( 不 一 定 是 唯 一 的 ) 词 来 自 于 字 典 中 NW , (1<=NW<=1,000)个独特的词。一个词 W_i,被定义为一个长度 1..20 的小写 字母序列('a'..'z')。 她还记得她密码中某些字母的位置。 请看下面的例子。贝西知道她的密码看起来像"a??l?ban???????"('?'代表一 个字母,她不记得) , 她的字典里有下面的词: apple cow farmer banana bananas pies 贝西有两个可能的密码是的“applebananapies”和“applebananascow” 。 给你字典, 贝西记得的字母, 请找到她的密码。 如果有一个以上的密码是可能的, 找到字典序最后的。 【输入格式】 : *第 1 行:两个空格分隔的整数:L 和 NW *第 2 行:一个字符串,长度为 L:P *第 3..N+2W 行:第 I+2 行包含在字典中的第 i 个字:W_i 【样例输入】 (forgot.in) : 15 6 a??l?ban??????? apple cow farmer banana bananas pies 【输出格式】 : *第 1 行:密码 【样例输出】 (forgot.out) : Applebananapies

学习语言(llang)

农夫约翰的 N(2 <= N<=10,000)头奶牛,号为 1.. N,一共会流利地使用 M (1<= M <=30,000)种语言,编号从 1 .. M.牛,Cow_i 会说 K_i(1 <= K_i<= M) 种语言,即 L_i1, L_i2,..., L_{iK_i} (1 <= L_ij <= M)。 FJ 的奶牛不太聪明,所以 K_i 的总和至多为 100,000。 两头牛,不能直接通话,除非讲共同的语言。然而,奶牛们可以传递消息以 及充当翻译。换言之,牛 A 和 B 可以谈话,当且仅当存在一个序列奶牛 T_1, T_2,...,T_k,A 和 T_1 说一种语言,T_1 和 T_2 共用一种语言??,并且 T_k 和 B 说同一种语言。 农夫约翰希望他的奶牛更加社会性, 所以他希望他的奶牛能够与任何其他牛 交谈。他可以买书教他的奶牛任何语言。作为一个相当节俭的农民,FJ 想要购 买最少的书籍,让所有他的奶牛互相可以说话。 帮助他确定: *他必须购买的书籍的最低数量 *某个将书分配给奶牛的方案,一个程序将给你的输出评分。 【输入格式】 : *第 1 行:两个用空格隔开的整数:N 和 M *第 2.. N +1 行: i +1 行描述的牛 i 的语言, 第 K_i+1 个空格隔开的整数: L_i1 K_i L_i2,...,L_I{K_i}。 【样例输入】 (llang.in) : 33 232 12 11 【输出格式】 : *第 1 行:一个整数,FJ 最少需要购买的书籍数量。 *第 2.. B +1 行:第 i +1 行包含两个空格隔开的整数:语言的编号和学习这种语 言的牛编号。如果存在多种解决方案,打印任何一个。 【样例输出】 (llang.out) : 1 23

BRONZE
牛的消防演习(bfire)

N(3<= N <=250)头的奶牛(标记为 cow_1.. cow_N)坐在在一圈绕着篝火 的椅子上 chair_1.. chair_N(cow_i 坐在 chair_i 上) ,农夫约翰告诉他们昔日的故 事。一个故事结束后,FJ 建议他们进行牛的消防演习。 在牛的消防演习中,当轮到 cow_i 移动,她沿顺时针方向移动到途中遇到的 第 i 个椅子。比如轮到 cow_3 移动,她会从 chair_3 开始移动,并移动到 chair_6 (如果 N> = 6) 。 当 cow_i 到达她的新椅子上,到达的那张椅子上的原来那头牛会开始移动, 给 cow_i 腾出空间,然后 cow_i 坐下。这个过程一直持续,直到一头牛坐到空椅 子上或者直到某头牛被要求第二次移动。在上述任何一种情况下,游戏结束。牛 1 总是第一个开始,所以她的椅子总是空的。 最后结束比赛的牛(坐在 cow_1 的椅子上,或者到达一只已经移动过的牛 那里) ,将收到一种特殊的嫩草奖励。 帮助 FJ 提前了解哪只牛会得到嫩草。 【输入格式】 : *第 1 行:一个整数:N 【样例输入】 (bfire.in) : 5 【输出格式】 : *第 1 行:结束比赛的那只牛编号 【样例输出】 (bfire.out) : 3

歪斜排序 农夫约翰有 2 ^ N(1<= N<= 10)头奶牛,每头奶牛在身体侧面用油漆写上了一 个数字标记,取值范围为 1..2^ N。它们按随机的顺序站在在一条线上。第一头 牛是 cow_1,第二头牛是 cow_2;(1<= cow_i<=2 ^ N) 。当然,cow_1 不太可能 油漆标签也是 1。

FJ 执行下面的算法来把它们按顺序排列。 1。如果有一个以上的牛,然后把奶牛分成两个大小相等的子组。两个子组继 续执行该算法。 2。递归返回时,比较两个子组的字典序,如果后面的子组字典序小,将两个 子组整体交换 奶牛想知道执行这个'排序'程序一共需要走动多少距离。 根据奶牛的初始位置,请求出: *所有奶牛的总行驶距离的总和 *奶牛的执行这个'排序'程序后最终的序列。 【输入格式】 : *第 1 行:一个整数:N *第 2..2 ^ N+1:第 i +1 行包含一个整数:cow_i 【样例输入】 (ssort.in) : 3 8 5 2 3 4 7 1 6 【输出格式】 : *第 1 行:一个整数,总行驶距离所有的奶牛 *第 2..2 ^ N+1 行:第 i +1 行包含一个整数:位置 i 站着的牛 【样例输出】 (ssort.out) : 50 1 6 4 7 2 3 5

8

3D 太空探索(space3d)

农夫约翰的奶牛终于从地球发射升空,奶牛要达到他们亲属的家,木星的一 个卫星木卫一上,但这样做,他们首先要穿过危险的小行星带。 贝西要通过 N*N*N(1<= N<= 100)的空间。所有小行星包括一些 1×1×1 的岩石(必须共享一个面,如果仅仅共享一个顶点或一条边,那就算 2 颗小行星) 请帮助贝西统计小行星数量。 在输入文件中,”*”代表小行星块,”.”代表一个空隙。 【输入格式】 : *第 1 行:一个整数:N *第 2.. N ^ 2+1 行:每 N 行代表一个空间平面 【样例输入】 (space3d.in) : 3 ... .*. ... ..* .*. *.. ... .*. ... 【输出格式】 : *第 1 行:一个整数,表明在小行星的数量 【样例输出】 (space3d.out) : 3

字符串函数编码(stringe)

贝西发现了一个新的功能,整个牛群可以申请一些字符串。 一个数字 N(1<= N <= 15)和一个串 S,长度严格大于 N,定义 F(N,S) 为一个新的字符串,即串 S 的第 N+1 个字母到最后作为前缀,再加上串 S 本身。 例如,对于 N = 2,和 S=“COW” ,F(N,S)=“W”+“COW”=“WCOW” 。 另外,F(3, “USACO” )=“CO”+“USACO”=“COUSACO” 。 贝西迷上了此功能,并希望迭代好几次。举例来说,如果她迭代函数一次, “COW”和 N = 2,那么她将得到“WCOW” 。如果她再次应用 N = 2 到该字符 串 , 她 将 得 到 “ OWWCOW ”, 如 果 她 用 更 多 次 N=2 , 她 会 得 到 “WCOWOWWCOW” 。 贝西有 Z(1<= Z <= 100)个字符串,STR_1,STR_2 等等。每个 STR_I 长 度范围为 2..100,只包含大写字母。其每个字符串有自己的 N_i(0 <= N_i<length (STR_I) ,需要迭代:C_i 次(1 <= C_i<=12) 。 输出迭代的最终结果串。 【输入格式】 : *第 1 行:一个整数:Z *第 2.. Z+1: i +1 行包含两个空格隔开的整数, 第 以及要被编码的字符串: C_i, N_i STR_I 【样例输入】(stringe.in): 2 2 3 COW 3 2 USACO 【输出格式】: * 第 1..Q 行: 第 J 行输出 STR_J

【样例输出】 (stringe.out): WCOWOWWCOW SACOCOUSACO 【输出解释】: COW -> WCOW -> OWWCOW -> WCOWOWWCOW USACO -> COUSACO -> SACOCOUSACO


推荐相关:

USACO讲义合集

马融 哞哞大学之匹萨预定 (Moo University - Emergency Pizza Order, USACO 2004 Mar) 哞哞大学咖啡厅的干草用完了,必须马上为C (1 ≤ C ≤ 1000)头奶牛预定...


b2 变换序列

? Usaco2010[9] hnoi[4] ? ? ? Usaco2010Hol[3] Hol[3] Usaco2010Mar[...2002-2011 BlogBus.com, All Rights Reserved. 博客大巴 版权 所有 博客大巴...


bzoj刷题总结列表

枚举每个点 i,if(now+sum[a,i]<=s) then<倍增> 2761: [JLOI2011]不...1233: [Usaco2009Open]干草堆 tower 1638: [Usaco2007 Mar]Cow Traffic 求...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com