USACO翻译：USACO 2012 JAN三题（2）

曾经终败给现在 2022-01-10 03:53 275阅读 0赞

## USACO 2012 JAN（题目二） ##

一、题目概览

<table> 
 <tbody> 
 <tr> 
 <td> 中文题目名称 </td> 
 <td> 叠干草 </td> 
 <td> 分干草 </td> 
 <td> &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;奶牛联盟 </td> 
 </tr> 
 <tr> 
 <td> 英文题目名称 </td> 
 <td> stacking </td> 
 <td> baleshare </td> 
 <td> cowrun </td> 
 </tr> 
 <tr> 
 <td> 可执行文件名 </td> 
 <td> stacking </td> 
 <td> baleshare </td> 
 <td> cowrun </td> 
 </tr> 
 <tr> 
 <td> 输入文件名 </td> 
 <td> stacking.in </td> 
 <td> baleshare.in </td> 
 <td> cowrun.in </td> 
 </tr> 
 <tr> 
 <td> 输出文件名 </td> 
 <td> stacking.out </td> 
 <td> baleshare.out </td> 
 <td> cowrun.out </td> 
 </tr> 
 <tr> 
 <td> 每个测试点时限 </td> 
 <td> 1秒 </td> 
 <td> 1秒 </td> 
 <td> 1秒 </td> 
 </tr> 
 <tr> 
 <td> 测试点数目 </td> 
 <td> 10 </td> 
 <td> 10 </td> 
 <td> 10 </td> 
 </tr> 
 <tr> 
 <td> 每个测试点分值 </td> 
 <td> 10 </td> 
 <td> 10 </td> 
 <td> 10 </td> 
 </tr> 
 <tr> 
 <td> 比较方式 </td> 
 <td> 全文比较 </td> 
 <td> 全文比较 </td> 
 <td> 全文比较 </td> 
 </tr> 
 </tbody> 
</table>

二、运行内存限制

<table> 
 <tbody> 
 <tr> 
 <td> 运行内存上限 </td> 
 <td> 128 M </td> 
 <td> 128 M </td> 
 <td> 128 M </td> 
 </tr> 
 </tbody> 
</table>

#  注：感谢老胡鼎力翻译。【错误会有的，语句也不是那么流畅……】 #

**1.****叠干草****\{Bronze****题****2\}**

【问题描述】

有(1 <= N <= 1,000,000, N为奇数)堆干草，按1..N编号，开始时每堆高度都是0，FJ给出K (1 <= K <= 25,000)条指令，每条指令包含两个用空格隔开的整数，例如”10 13”，表示给10,11,12,13这四堆干草分别叠加一捆干草，即高度均增加1。

FJ想知道，干草对完后，这N堆干草高度的中位数是多少。

【文件输入】

第一行，两个正整数N和K。

第2..K+1行，每行两个整数A B (1 <= A <= B <= N)，表示一条指令。

【文件输出】

一个整数，表示中位数。

【输入样例】

7 4

5 5

2 4

4 6

3 5

【输出样例】

【样例说明】

堆完后，高度分别是0,1,2,3,3,1,0。排序后为0,0,1,1,2,3,3，故中位数是1。

**2.****分干草****\{silver****题****2\}**

【问题描述】

FJ有N (1 <= N <= 20)包干草，干草i的重量是 S\_i (1 <= S\_i <= 100)，他想尽可能平均地将干草分给3个农场。

他希望分配后的干草重量最大值尽可能地小，比如， B\_1,B\_2和 B\_3是分配后的三个值，假设B\_1 >= B\_2 >= B\_3，则他希望B\_1的值尽可能地小。

例如：8包感触的重量分别是：2 4 5 8 9 14 15 20，一种满足要求的分配方案是

农场 1: 2 9 15 B\_1 = 26

农场 2: 4 8 14 B\_2 = 26

农场 3: 5 20 B\_3 = 25

请帮助FJ计算B\_1的值。

【文件输入】

第一行，一个整数N。

第2..N+1行，每行一个整数，表示重量。

【文件输出】

一行，一个整数，表示B\_1的值。

【输入样例】

【输出样例】

**3.** **奶牛跑步****\{ Gold****题****2\}**

【问题描述】

FJ和贝茜为奶牛们设计了一个新的跑步游戏。跑道是环行的，长度为(2 <= M <= 1,000,000,000)的环行，奶牛们在相同的起跑位置。这个游戏一共要进行N (1 <= N <= 14)轮，通过一副8N张的纸牌来控制每一轮的跑步距离，每张纸牌都有一个数字X\_i (0 <= X\_i < M)。

每一轮，FJ取出最上面的8张纸牌，然后再取出这8张的上面或者底下的4张。接着，贝茜从这4张牌中取出上面或者底下的2张，上面一张的数字为X\_top，下面一张的数字是X\_bottom，则牛先跑R\*X\_top的距离（R表示奶牛们已经跑过的距离），再跑X\_bottom的距离。

FJ担心奶牛们太累而回不到起点，游戏结束时，若奶牛们离开起点距离超过K (0 <= K <=floor(M/2))，则他们就回不了起点了。

问题保证，当FJ选择正确的取牌策略，不论贝西如何取牌，奶牛们都能够回到起点。对于每一轮，你的任务是决定取哪4张纸牌。在输入数据中，贝西的每次选择都是已知的，但FJ的每次取牌时，贝西接着的选择应该被假定为是未知的，即不论贝西怎么选，FJ的选择都是能保证奶牛们能够回到起点。

【文件输入】

第一行，3个用空格隔开的整数N，M，K。

第二行，N个字符，若第i个字符是T，表示第i轮贝西选择上面的2张纸牌，若是B，则表示选择下面的2张纸牌。

第3..N+2行，每行包含8个数字，表示每一轮开始时，最上面的8张纸牌（自上而下）上的数字。

【文件输出】

一行，一个包含N个字符的字符串，若第i个字符是T，表示第i轮FJ选择上面的4张纸牌，若是B，则表示选择下面的4张纸牌。若有多解，则输出字典序最小的方案。

【输入样例】

2 2 0

1 0 0 0 0 0 0 1