USACO 2014 DEC SILVER

一、题目概览

二、运行内存限制

1.回程{piggyback}

【问题描述】

Bessie 和 Elsie在不同的区域放牧，他们希望花费最小的能量返回谷仓。从一个区域走到一个相连区域，Bessie要花费B单位的能量，Elsie要花费E单位的能量。如果某次他们两走到同一个区域，Bessie 可以背着 Elsie走路，花费P单位的能量走到另外一个相连的区域，满足P<B+E。

【文件输入】

   第一行，四个不超过40,000的正整数B, E, P, N。其中N表示区域的个数（区域分别用1..N编号，N>=3）,M表示各个区域之间连接的边数。一开始Bessie在区域1， Elsie在区域2，谷仓在区域N。

   接下来M行，每行二个整数表示一条双向边连接两个区域，输入保证从区域1和区域2都能走到区域N。

【文件输出】

   一行，一个整数，最小花费的单位能量。

【输入样例】

4 4 5 8 8

1 4

2 3

3 4

4 7

2 5

5 6

6 8

7 8

【输出样例】

22

【样例说明】

Bessie从1到4，Elsie从2到3到4，然后一起从4到7到8。

2. 奶牛IDs{cowids}

【问题描述】

FJ给他的奶牛用二进制进行编号，每个编号恰好包含K 个"1"  (1 <= K <= 10)，且必须是1开头。FJ按升序编号，第一个编号是由K个"1"组成。

请问第N(1 <= N <= 10^7)个编号是什么。

【文件输入】

   一行，两个整数N 和 K。

【文件输出】

   一行，一个二进制串，表示第N个二进制编号。

【输入样例】

7 3

【输出样例】

10110

3. 搬家{ relocate}

【问题描述】

    FJ决定搬家，重新建设农场，以便最小化他每天的行程。

FJ搬往的区域有N(1 <= N <= 10,000)个城镇，共有M (1 <= M <= 50,000)条双向道路连接某些城镇，所有城镇都能找到互通路线。

有K (1 <= K <= 5)个城镇建有市场，FJ每天离开新农场后，都要光顾这K个城镇，并返回农场。FJ希望建设农场的城镇不包含市场。

请帮助FJ选择最佳城镇建设农场，使得他每天的行程最小。

【文件输入】

第一行，三个整数N、M和K。

第2..K+1行，每行一个整数，表示含市场的城镇编号。

第2+K..1+K+M行，每行三个整数，i, j (1 <= i,j <= N),  L (1 <= L <= 1000)，表示城镇i和j之间有长度为L的道路连接。

【文件输出】

一行，一个整数，表示每天的最小行程。

【输入样例】

5 6 3

1

2

3

1 2 1

1 5 2

3 2 3

3 4 5

USACO 2014 DEC SILVER

一、题目概览

二、运行内存限制

1.回程{piggyback}

【问题描述】

Bessie 和 Elsie在不同的区域放牧，他们希望花费最小的能量返回谷仓。从一个区域走到一个相连区域，Bessie要花费B单位的能量，Elsie要花费E单位的能量。如果某次他们两走到同一个区域，Bessie 可以背着 Elsie走路，花费P单位的能量走到另外一个相连的区域，满足P<B+E。

【文件输入】

   第一行，四个不超过40,000的正整数B, E, P, N。其中N表示区域的个数（区域分别用1..N编号，N>=3）,M表示各个区域之间连接的边数。一开始Bessie在区域1， Elsie在区域2，谷仓在区域N。

   接下来M行，每行二个整数表示一条双向边连接两个区域，输入保证从区域1和区域2都能走到区域N。

【文件输出】

   一行，一个整数，最小花费的单位能量。

【输入样例】

4 4 5 8 8

1 4

2 3

3 4

4 7

2 5

5 6

6 8

7 8

【输出样例】

22

【样例说明】

Bessie从1到4，Elsie从2到3到4，然后一起从4到7到8。

2. 奶牛IDs{cowids}

【问题描述】

FJ给他的奶牛用二进制进行编号，每个编号恰好包含K 个"1"  (1 <= K <= 10)，且必须是1开头。FJ按升序编号，第一个编号是由K个"1"组成。

请问第N(1 <= N <= 10^7)个编号是什么。

【文件输入】

   一行，两个整数N 和 K。

【文件输出】

   一行，一个二进制串，表示第N个二进制编号。

【输入样例】

7 3

【输出样例】

10110

3. 搬家{ relocate}

【问题描述】

    FJ决定搬家，重新建设农场，以便最小化他每天的行程。

FJ搬往的区域有N(1 <= N <= 10,000)个城镇，共有M (1 <= M <= 50,000)条双向道路连接某些城镇，所有城镇都能找到互通路线。

有K (1 <= K <= 5)个城镇建有市场，FJ每天离开新农场后，都要光顾这K个城镇，并返回农场。FJ希望建设农场的城镇不包含市场。

请帮助FJ选择最佳城镇建设农场，使得他每天的行程最小。

【文件输入】

第一行，三个整数N、M和K。

第2..K+1行，每行一个整数，表示含市场的城镇编号。

第2+K..1+K+M行，每行三个整数，i, j (1 <= i,j <= N),  L (1 <= L <= 1000)，表示城镇i和j之间有长度为L的道路连接。

【文件输出】

一行，一个整数，表示每天的最小行程。

【输入样例】

5 6 3

1

2

3

1 2 1

1 5 2

3 2 3

3 4 5

4 2 7

4 5 10

【输出样例】

12

【样例说明】

农场建在城镇5。FJ每天的路线 5-1-2-3-2-1-5, 总行程为12。

4 2 7

4 5 10

【输出样例】

12

【样例说明】

农场建在城镇5。FJ每天的路线 5-1-2-3-2-1-5, 总行程为12。

USACO翻译：USACO 2014 DEC Silver三题

原文：http://www.cnblogs.com/jznoi/p/4280805.html