12/14

最近做了一下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(n2)每次查询现算都可以。这道题USACO给的解题报告就是朴素。当然,我们可以定义一个数组g[n]代表从第一天到第n天的和,每次调用g[e]-g[s-1]就可以了。