USACO 2012 FEB SILVER
一、题目概览
|
中文题目名称 |
矩形草地 |
奶牛IDs |
搬家 |
|
英文题目名称 |
planting |
cowids |
relocate |
|
可执行文件名 |
planting |
cowids |
relocate |
|
输入文件名 |
planting.in |
cowids.in |
relocate.in |
|
输出文件名 |
planting.out |
cowids.out |
relocate.out |
|
每个测试点时限 |
1秒 |
1秒 |
1秒 |
|
测试点数目 |
10 |
10 |
10 |
|
每个测试点分值 |
10 |
10 |
10 |
|
比较方式 |
全文比较 |
全文比较 |
全文比较 |
二、运行内存限制
|
运行内存上限 |
128 M |
128 M |
128 M |
1.矩形草地{planting}
【问题描述】
有N (1 <= N <= 1000)个矩形区域（各边分别平行于x轴y轴），有些矩形可能全部或者部分重叠，FJ要在这些矩形区域能种草，请计算种植面积。
【文件输入】
第一行，一个整数N。
第2..N+1行，每行四个个整数x1 y1 x2 y2，其中（x1，y1）表示左上角，（x2，y2）表示右下角，坐标值范围是-10^8...10^8。
【文件输出】
一行，一个整数，表示种植面积。
【输入样例】
2
0 5 4 1
2 4 6 2
【输出样例】
20
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。