usaco金组试题【河南省实验中学吧】

共有九题
**********************************************************************
第一题: 双数? 单数? [25分] [Rob Kolstad, 2009]
Bessie那惨无人道的二年级老师搞了一个有 N (1 <= N <= 100) 个正整数 I (1 <= I
<= 10^60) 的表叫Bessie去判断“奇偶性”（这个词语意思向二年级的学生解释，就是“这个
数是单数，还是双数啊？”）。Bessie被那个表的长度深深地震精到了，竟然跟栋栋的泛做表
格一样多道题！！！毕竟她才刚刚学会数数啊。
写一个程序读入N个整数，如果是双数，那麼在独立的一行内输出"even"，如果是单数则类似
地输出"odd".
分值: 25
题目名称: evenodd
输入格式:
* 第一行: 一个单独的整数: N
* 第2到第N+1行: 第j+1行有第j个需要判断奇偶性的整数。
样例输入 (文件：evenodd.in):
2
1024
5931
输入细节:
两个整数: 1024和5931
输出格式:
* 第1..N行: 第j行根据第j个整数的奇偶性输出一个单词"even"或者"odd"
样例输出 (文件 evenodd.out):
even
odd
输出格式:
1024可以被2整除; 而5931不可以。
**********************************************************************
第2题: 犁田机器人 [25分] [Rob Kolstad (传统题目), 2009]
Farmer John为了让自己从无穷无尽的犁田工作中解放出来，於是买了个新机器人帮助他犁田。
这个机器人可以完成犁田的任务，可惜有一个小小的缺点：这个犁田机器人一次只能犁一个边的
长度是整数的长方形的田地。
因为FJ的田地有树和其他障碍物，所以FJ设定机器人去犁很多不同的长方形。这些长方形允许重
叠。他给机器人下了P个指令，每个指令包含一个要犁长方形的地。这片田地由长方形的左下角
和右上角坐标决定。他很好奇最后到底有多少个方格的地被犁过了。
一般来说，田地被分割为很多小方格。这些方格的边和x轴或y轴平行。田地的宽度为X个方格，
高度为Y个方格 (1 <= X <= 240; 1 <= Y <= 240). FJ执行了I (1 <= I <= 200)个指
令，每个指令包含4个整数：Xll, Yll, Xur, Yur (1 <= Xll <= Xur; Xll <= Xur <=
X; 1 <= Yll <= Yur; Yll <= Yur <= Y), 分别是要犁的长方形的左下角坐标和右上角坐
标。机器人会犁所有的横坐标在Xll..Xur并且纵坐标在Yll..Yur范围内的所有方格的地。可能
这个长方形会比你想像的多一行一列（就是说从第Xll列到第Xur列一共有Xur - Xll + 1列而
不是Xur - Xll列）。
考虑一个6方格宽4方格高的田地。FJ进行了2个操作（如下），田地就被犁成"*"和"#"了。虽然
一般被犁过的地看起来都是一样的。但是标成"#"可以更清晰地看出最近一次被犁的长方形。
    ......             **....             #####.
    ...... (1,1)(2,4) **.... (1,3)(5,4) #####.
    ......             **....             **....
    ......             **....             **....
一共14个方格的地被犁过了。
分数: 25
题目名称: rplow

        3-----%                       3-----%
         \                             \
          4----%                        4----%
           \                             \
            %                             %
从分岔节点9到达的草地是两个可以让Bessie走过最多小径的草地之一。在去吃早草的路上
Bessie将走过7条不同的小径。这些草地是离牛棚也就是节点1最“远”的。
由3个整数来表示每一个节点：Cn, D1和D2，Cn是节点的编号(1 <= Cn <= P-1); D1和
D2是由该节点引出的两条小径的终点(0 <= D1 <= P-1; 0 <= D2 <= P-1)。如果D1为
0，表示这条小径引向的是一片牧草地；D2也一样。
分值: 100
题目名称: stroll
输入格式:
* 第1行: 一个单独的整数: P
* 第2到第P行: 第i+1行有3个由空格隔开的整数，表示一个分岔节点Cn, D1和D2。
样例输入 (文件 stroll.in):
10
7 8 0
5 0 6
9 0 0
6 0 7
3 4 0
2 5 0
8 0 9
4 0 0
1 2 3
输入细节:
这个输入表示题目描述中的例子。
输出格式:
* 第一行: 一个单独的整数，表示Bessie去最远的草地的路上最多可以走过的小径的数目。
样例输出 (文件 stroll.out):
7
输出细节:
1-2-5-6-7-8-9-P是最长的一条路径之一。
**********************************************************************
第六题: 乳草的入侵 [125分] [Rob Kolstad, 2009]
Farmer John一直努力让他的草地充满鲜美多汁的而又健康的牧草。可惜天不从人愿，他在植
物大战人类中败下阵来。邪恶的乳草已经在他的农场的西北部份占领了一片立足之地。
草地像往常一样，被分割成一个高度为Y(1 <= y <= 100), 宽度为X(1 <= x <= 100)的
直角网格。(1,1)是左下角的格（也就是说坐标排布跟一般的X,Y坐标相同）。乳草一开始占
领了格(Mx,My)。每个星期，乳草传播到已被乳草占领的格子四面八方的每一个没有很多石头
的格（包括垂直与水平相邻的和对角线上相邻的格）。1周之后，这些新占领的格又可以把乳草
传播到更多的格里面了。
Bessie想要在草地被乳草完全占领之前尽可能的享用所有的牧草。她很好奇到底乳草要多久才
能占领整个草地。如果乳草在0时刻处於格(Mx,My)，那麼还在那个时刻它们可以完全占领入侵
整片草地呢（对给定的数据总是会发生）？
草地由一个图片表示。"."表示草，而"*"表示大石。比如这个X=4, Y=3的例子。
     ....