USACO月赛:DEC08铜组题目翻译及解题报告

最近做了一下USACO的月赛，因为之前很少做所以还是铜组。总体来说铜组的题还是比较简单的，基本上全部暴搜就能OK（本文当然不是介绍怎么暴搜的，如果要看暴搜看USACO的解题报告），不过我有一道题少考虑一种情况丢了3个点。我准备学习一下某牛尝试养成写解题报告的习惯，顺便把题目翻译一下。水平有限、如有不足欢迎留言提出。

铜组有三道题，分别是“Checkers”（西洋跳棋）、“Bad Grass”（劣质的草）、“Hay Expenses”（草料开支），我分别是用了深度优先搜索、并查集、求和数组。

（下述翻译系原创，转载时请注明出处）

**********************************************************************
                                              铜组 问题
**********************************************************************
                                    从11到13的三道题
**********************************************************************

问题 11: 西洋跳棋 [Rob Kolstad, 2008]

奶牛们在疯狂地玩着西洋跳棋，但是非常不幸、不管他们多么享受，
他们还是在最后阶段遇到了可怕的麻烦，他们需要你的帮助。

有一个NxN (4 <= N <= 30) 跳棋格，请确定最佳的结束比赛步骤。
跳棋子仅仅能够在标记有’+’ 的格子里停留，通过“飞跃”俘获对方
的棋子。刚刚跳过的格子将被立即封锁。请看下面的例子：
N=8时:

– + – + – + – +  “K”代表贝茜的王； “O”代表对手的棋子。贝茜总是向下
+ – + – + – + –  走棋。王需要斜着连续的跳过舵手的棋子，跳过的格子
– + – K – + – +  将会被封锁。
+ – + – + – + – 
– o – o – + – +  对于这个情况，获胜的方案需要是最下面、最左边的王
+ – K – + – + –  连续的跳过三个对方的棋子，游戏因此结束。
– o – + – + – + 
+ – K – + – K –  （被移动的K被标记为>K<）：
  
         原始         第一次移动       第二次移动        第三次移动
– + – + – + – +     – + – + – + – +    – + – + – + – +     – + – + – + – +
+ – + – + – + –     + – + – + – + –    + – + – + – + –     + – + – + – + –
– + – K – + – +     – + – K – + – +    – + – K – + – +     – + – K – + – +
+ – + – + – + –     + – + – + – + –    + ->K<- + – + –     + – + – + – + –
– o – o – + – +     – o – o – + – +    – + – o – + – +     – + – + – + – +
+ – K – + – + –    >K<- K – + – + –    + – K – + – + –     + – K ->K<- + –
– o – + – + – +     – + – + – + – +    – + – + – + – +     – + – + – + – +
+ ->K<- + – K –     + – + – + – K –    + – K – + – K –     + – K – + – K –
                   
棋子移动表现在下面的图中：

  1 2 3 4 5 6 7 8           R C
1 – + – + – + – +    开始:  8 3
2 + – + – + – + –    移动:  6 1
3 – + – K – + – +    移动:  4 3
4 + – * – + – + –     移动:  6 5
5 – o – o – + – +
6 * – K – * – + –
7 – o – + – + – +
8 + – K – + – K – 

请写一个程序在存在时给出NxN输入的棋盘的结束游戏步骤（唯一的、
像它生成出来时一样）。 至少有一个王和一个对手棋子在棋盘上。
程序名称: chkr

输入格式:

* 行1: 单个整数: N

* 行 2..N+1: 行i+1 包含 N 个字符 (‘-‘, ‘+’,’K’, or ‘o’) 代表一个正确
        的棋盘上的一行。
样例输入(file chkr.in):

8
-+-+-+-+
+-+-+-+-
-+-K-+-+
+-+-+-+-
-o-o-+-+
+-K-+-+-
-o-+-+-+
+-K-+-K-

输出格式:

* 行 1..?: 如果步骤序列不存在，请输出“impossible”；如果存在序列，
        每一行包含两个用空格开的整数代表被移动、胜利的王每步的位置。

样例输出 (file chkr.out):

8 3
6 1
4 3
6 5

**********************************************************************

问题12: 劣质的草 [Fatih , 2008]

贝茜像其它奶牛一样正在吃草，她正在思考她所在的地方。她注意
到她只得到了一个平于海平面的广泛大片牧场。只有海拔1米或者更
高更硬的草不那么美味。草随着海拔的增加越发难吃。

继续咀嚼，她意识到，这没有食欲的食物长成两侧的丘陵，形成了青
翠美味丰富草地海洋中的一系列劣质草小岛 。

贝茜穿上她的实验服，决心测定她的牧场有多少劣草小岛。她画出一
张画有被分成R (1 < R <= 1,000) 行、C (1 < C<= 1,000)列的1米x1米
小格子的地图。她为每个小格子测量了海拔高度，并四舍五入到
非负整数。她饥饿地把所有美味草标的海拔标记成0。

她着手统计小岛。任何水平、垂直、斜向相邻的两个有劣草的格子将
被认为在同一个岛中。

在每一张她提供的地图中有多少劣草岛屿呢？

程序名称: badgras

输入格式:

* 行 1: 两个用空格隔开的整数: R 和 C

* 行 2..R+1: 行 i+1 用C个看空格隔开的整数表示地图中的i行

样例输入 (file badgras.in):

8 7
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0

输出格式:

* 行 1: 一个代表岛屿数的整数。

样例输出 (file badgras.out):

2

输出说明:

有两个岛。最大的一个在左侧通过一个对角线延伸到最底层，
最小的一个在右上角。

**********************************************************************

问题 13: 草料开支 [Neal Wu, 2008]

每天农场主约翰都会用一顿奢侈美味的草料大餐喂养奶牛们。然后，
他会在他记录开支的笔记本上记录下草料的包数。

缴税时间到来时
，约翰意识到自己忘记记录草料喂养的日期。他必须
计算出许多不同的连续草料喂养的总数，以解决这个涉及一个月饲料
开支难题。

约翰设立了一个包含被简单编号为1 .. N的N (4 <= N <= 500)天
的干草包数H_i (1 <= H_i <= 1,000)。他有Q (1 <= Q <= 500)次额外
查询，每次查询包含整数S_j和E_j(1 <= S_j <= E_j <= N) 代表了起
始日期。你的任务是，统计S_j .. E_j （含）期间总共的草料包数并
对每一次查询返回一个总数。

程序名称: hayexp

输入格式:

* 行 1: 两个空格隔开的整数: N 和 Q

* 行 2..N+1: 行 i+1 包含一个代表第i天草料包数的整数:H_i

* 行 N+2..N+Q+1: 行 j+N+1 包含第j次查询的两个整数:S_j 和 E_j

样例输入 (file hayexp.in):

4 2
5
8
12
6
1 3
2 4

输入说明:

四天; 两次查询。  草料包数: 5, 8, 12, 和 6. 统计日期1..3和2..4.

输出格式:

* 行 1..Q: 行 j 包含一个整数代表天数从 S_j 到 E_j 的草料包数和。

样例输出 (file hayexp.out):

25
26

输出说明:

日次:    1 2  3  4 
包数:    5 8 12  6

查询 1..3:  5 + 8 + 12 = 25
查询 2..4:  8 + 12 + 6 = 26

**********************************************************************
 （上述翻译系原创，转载时请注明出处）

问题一：西洋跳棋

从题目的叙述来看，一组解、又有那么多限制，再看看数据规模只有30，显然我们可以用搜索，因为数据量最多只有900个格子，我们最多最多搜900×900次，显然这个我们是可以忍受的。

再看看题目中，只要一组解、而且还划定的位置优先顺序，显然应该使用深度优先搜索，大家可以参考一下我的程序，实际上当我们读入数据发现’o’的时候就可以将对角线连接起来，因为只有两端为’+’跨越’o’的对角线才可以做边，于是原图便成了右图所示的无向图，我们只需要在这里以每一个K为起点深度优先搜索一下就可以了。

问题二：劣质的草

最开始看到这个题我就想到了并查集，因为并查集能够实现合并、查找的功能，当然、此题查找功能用的不多，不过我们可以利用一下它的查找。其实这道题数据规模也不大，USACO的报告是在用广度优先搜索，也就是每一个点为起点开始搜索，这样就可以把整个块遍历出来，这种搜索经常运用到图像算法中（叫什么我给忘了/UPDATE:某牛说是Floodfill）。再回来接着说我的并查集，我不幸并查集没写对，我是边读入边建立并查集的，结果忘了考虑斜右上的边了。顺便在这里偷偷谴责一下USACO的评测机，这个题后来我用修改过的同样的程序提交了4次，2次OK、2次TLE，我都无奈了……后来写信给Rob（比赛策划者），他说那是Linux的一个老问题了，他想了很多办法都没有解决，每次比赛他都要测试很多次以确定成绩稳定。

问题三：草料开支

这题不说什么了，这个数据规模朴素绰绰有余，用O(n²)每次查询现算都可以。这道题USACO给的解题报告就是朴素。当然，我们可以定义一个数组g[n]代表从第一天到第n天的和，每次调用g[e]-g[s-1]就可以了。