谁有USACO金牌月赛历届题目答案？

谁有USACO金牌月赛历届题目答案？

标程你可以到USACO CONTEST查找，这是近年2月月赛的金组题。 题1: 覆盖牛棚 [Richard Peng, 2009] 奶牛们非常羞涩，他们要求Farmer John在他们的圆形牛棚周围建造围栏。牛棚的周长为c(1 <= C <= 1,000,000,000)，现在，FJ希望从一些有固定起点和终点的栏杆的集合里选出一些栏杆。 栏杆i 的起点可以被建造在一个整数位置 x_i(相距围栏起点i个长度) (0 <= x_i < C),并且，这个栏杆有一个整数长度l_i(1 <= l_i <= C)。 FJ 希望最小化栏杆的数量，从而达到覆盖整个牛棚的外圈。 考虑一个周长为5的牛棚，下图所示的是一些连接的线段，同样的两个点 '0'表示牛棚上的同样的位置。 下列有3个可以建造的栏杆： 起点 终点 i x_i l_i 1 0 1 2 1 2 3 3 3 0 1 2 3 4 0 1 2 3 ... 牛棚外圈: +---+---+---+---+--:+---+---+---+- ... 11111 1111 22222222 22222222 3333333333333333 |..................| 如上所示，建造2号和3号栏杆可以覆盖整个牛棚外圈共5个单位长度。FJ 认为不同栏杆之间可以相互重叠。 【程序名】: corral 【输入格式】 * 第一行 : 用空格隔开的两个整数C和M * 第二行到M+1行: 第i+1行为两个用空格分开的整数 x_i和l_i 【输出格式】 * 第一行:单独一个整数表示最少的围栏数，从而能够覆盖整个牛棚的外圈 【样例输入】 (文件名 corral.in): 5 3 0 1 1 2 3 3 【样例输出】 (文件名 corral.out): 2 题2: 冰上 [Jelle van den Hooff, 2010] Bessie 在一个冰封的湖面上游泳，湖面可以表示为二维的平面，坐标范围是-1,000,000,000..1,000,000,000。湖面上的N(1 <= N <= 20,000)个位置有石块(编号分别为1到N)，其它位置是冰面。由于Bessie滑冰技术不够好，她通过推动自己旁边的石块，依靠反作用力向某一个方向前进，在碰到一个新的石块之前，Bessie是不会停下来的。(当然，最后会停留在某块石块的前一个格子里)由于Bessie无法计算复杂的角度，她只能够向东南西北四个方向前进。很显然，Bessie不能够穿越石块，因此，Bessie仅仅可以向三个方向滑。 滑冰不是没有风险，Bessie滑向某个方向后必须能碰到某个石块，因此她必须很小心。考虑下面的一个情况，Bessie希望到达在她东面的目标位置(x=5,y=1)，(. = 冰块,* = 石头, B = Bessie, G = 目的位置)如果她直接向东滑，那么她会滑过目标位置，因为她通过撞上某块石头来停下来，一个能够到达目标位置的方案是这样的： (a) (b) (c) (d) 4 .....*. .....*. .....*. .....*. 3 ..*.... slide ..*.... slide ..*.... slide ..*.... 2 ......* north ..B...* east .....B* south ......* 1 .*B..G. ------> .*...G. ------> .*...G. ------> .*...B. 0 *....*. *....*. *....*. *....*. 0123456在(a)中，Bessie 只能朝向北，东，或者南三个方向，但是只有在北面能撞上石头从而停下来，在(b)中，类似地，她只能向东走。对于输入，石头 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)，没有任何两块石头位于同一个位置，Bessie从Bx,By的位置出发(出发点一定与某个石头相邻)，Bessie的目标位置是Gx,Gy(-1,000,000,000 <= Gx <= 1,000,000,000; -1,000,000,000 <= Gy <=1,000,000,000). Bessie 并不介意长时间滑冰，但是，不停地推石头依靠反作用力前进很累。FJ 非常关心Bessie的健康，因此他希望知道Bessie最少要推多少次石头才能到达终点。 【程序名】: ice 【输入格式】: *第一行: 五个用空格隔开的整数: N, Bx, By, Gx, and Gy *第二行到第N+1行: 第i+1行用两个空格隔开的整数来描述第i个石头 【样例输出】： * 第一行: 一个整数表示Bessie至少要推多少次石头才能够到达终点 【样例输入】(文件名 ice.in): 6 2 1 5 1 5 4 2 3 1 1 6 2 5 0 0 0 【样例输出】(文件名 ice.out): 3 题3: 慢慢走 [Jelle van den Hooff, 2010] 每天Farmer John的N头奶牛(1 <= N <= 100000，编号1…N)从粮仓走向他的自己的牧场。牧场构成了一棵树，粮仓在1号牧场。恰好有N-1条道路直接连接着牧场，使得牧场之间都恰好有一条路径相连。第i条路连接着A_i，B_i，(1 <= A_i <= N; 1 <= B_i <= N)。 奶牛们每人有一个私人牧场P_i (1 <= P_i <= N)。粮仓的门每次只能让一只奶牛离开。耐心的奶牛们会等到他们的前面的朋友们到达了自己的私人牧场后才离开。首先奶牛1离开，前往P_1；然后是奶牛2，以此类推。 当奶牛i走向牧场P_i时候，他可能会经过正在吃草的同伴旁。当路过已经有奶牛的牧场时，奶牛i会放慢自己的速度，防止打扰他的朋友。 考虑如下的牧场结构（括号内的数字代表了牧场的所有者）。 1 (3) / \ (1) 4 3 (5) / \ (2) 2 5 (4) 首先，奶牛1走向自己的牧场。 1 (3) / \ [1] 4* 3 (5) / \ (2) 2 5 (4) 当奶牛2走向自己的牧场时，她会先经过粮仓（牧场1）。然后她会在到达牧场2（她自己的牧场）前路过奶牛1所在的牧场4。 1 (3) / \ [1] 4* 3 (5) / \ [2] 2* 5 (4) 奶牛3不用走很远，他自己的牧场就是粮仓（牧场1）。 1* [3] / \ [1] 4* 3 (5) / \ [2] 2* 5 (4) 奶牛4必须放慢速度经过牧场4，2到达牧场5. 1* [3] / \ [1] 4* 3 (5) / \ [2] 2* 5* [4] 奶牛5则要小心经过牧场1进入牧场3. 1* [3] / \ [1] 4* 3*[5] / \ [2] 2* 5* [4] FJ想要知道奶牛们总共要放慢多少次速度。 【文件名】: slowdown 【输入格式】: *第1行 : 一个正整数N *第2…N行: 第i+1行包括一对正整数A_i,B_i *第N+1..N+N行: 第 N+i行 包括一个正整数: P_i 【样例输入】 (文件名 slowdown.in): 5 1 4 5 4 1 3 2 4 4 2 1 5 3 【输出格式】: * 第一行到第N行：第i行表示第i只奶牛需要被放慢的次数 【样例输出】 (文件名 slowdown.out): 0 1 0 2 1

希望采纳