猴子的小窝

昨天(25日)，我们班一位同学突发水痘(一种由水痘－带状疱疹病毒引起的急性传染病)，在放学后我们接到学校通知开始更换教室接受隔离。去年有一个班是因为手足口病被隔离的。

这次罹患水痘的是我们班的一位住宿的女同学，她可能已经有了两日的症状了，但是由于她并没有意识到便一直没有发现。据信，她当时和另一位同学打算逃避课间操“冬煅”跑步，那位同学看见了她身上的红点出主意说到医务室看看是不是水痘，结果才得到了确诊。我们班当天下午就被通知搬离教室、撤离教学楼，年级负责人员、医务室负责人员、后勤负责人员、食堂负责人员以及班主任都到场了。据口头通知，我们将被隔离至明年元旦4日，但又有消息称我们将在之后被继续隔离直至放假，而书面的家长信上告知的是21日隔离。

隔离的日子里

在隔离期间，我们不能进入食堂、不能进入教学楼、不能进入操场、不能进入图书馆、不能进入除公共厕所外的一切校内公共场所，同时这也意味着新年舞会我们将不能参加、元旦联欢将不能在我们原来宽敞明亮的教室里举办，如果我们的隔离期还将延长，我们将有可能不能在原来的教室里度过这个学期左后的时光。我们每日的早、中、晚餐都将由食堂工作人员做好后送到我们的教室里。我们体育课（由于天气不适宜易感人群）、课间操也一并取消。

最惨的是数学、外语A/B分层教学也将中止，多个班级将受到影响，很多其他班级的A班同学要返回B班上课，很多我们班的B班同学会跟着A班上课。这也成全了我们中的很多人，一些同学对B班的教学有些看法或希望能够学得更多的愿望得以实现。本人也和所在教学班的老师告了别，呵呵。

由于以后不能去食堂了，我们昨晚的最后一顿在食堂的晚餐吃得格外的丰盛，我们有同学开玩笑说“咱们赶紧分散坐，等人家快吃完了，然后说，咱这水痘怎么这么痒啊……”

晚上回宿舍，我们宿舍那位外班的以前得过所以不怕。他们上完第三节晚自习的人回来的时候开玩笑地喊着“水痘大军来啦！”早上我们也不能在宿舍食堂就餐。

隔离中的乐趣

这几天班主任一直和我们在一起，不上课间操我们可以干很多好玩的事情——比如打羽毛球、踢毽子，我才发现我们班主任的羽毛球水平非常的高。

昨天是圣诞节，我们把另一位同学的衣服用书和一个毛绒玩具架起来，帽子用球填充好，制造出了一个手里夹着写有“圣诞快乐”字样纸条的假人，本来想把我们宿舍老师逗一逗呢……结果人家没有来。

不过遥望着晚自习前的教学楼，看见除了我们的教室以外其它的教室都灯火通明，还是有一丝的伤感……

据说，水痘也会引起带状疱疹。弟兄们，挺住！

 为了纪念生活中的重大事情，本博客将启用纪念顶部通栏，每次大事顶部的通栏都会发生变化以表示纪念。

本次使用的是秋游通栏，2008年11月我们前往了南宫地热公园进行秋游，通栏照片取自本人的摄影作品，图中是同学们正在喂鸭子。

最近做了一下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]就可以了。

“老师们同学们，你们好！”昨天上操的时候，我们学校学生处主任孟老师给我们了一个公告，说什么为了感谢同学们对学校工作的支持，值此过年之际，包了个场子让我们去看电影……

真不知道学校的葫芦里卖的什么药，两场，一个是《梅兰芳》，另外一个是《回到未来》《预见未来》。

最近做了一下SGU106这道题，本来以为是一道很简单的数学题，结果就死活Accept不了……经过几个星期的奋战、参考了别人的程序终于解决了问题。

首先我们可以通过扩展欧几里德算法计算出符合该方程的一组解，之后根据数论推出的公式就可以的解数：

这个公式有一点参数方程的味道，在算出两侧最大的k以后相减即可。顺便说一句，我感觉上面我被链接解题报告的那位仁兄的程序似乎有些问题，尽管程序都能Accept，但我觉得他的理解有问题：在最开始的特殊情况判断的时候，如果a和b有且仅有一个为零，则应该输出的是其在范围内的长度，而不是1，Saratov State University没有在这里设点，因此没有出现问题。

我当初是ceil()/floor()这两个取整函数写错了，囧死了……其实PASCAL在竞赛的时候可以使用math库，里面都有。

program<br/>        sgu106;<br/>var<br/>        i,j,k:int64;<br/>        a,b,oa,ob,c,x1,x2,y1,y2:int64;<br/>        x,y:int64;<br/>        tx,ty:int64;<br/>procedure swap(var a,b:int64);<br/>        var<br/>          t:int64;<br/>        begin<br/>          t:=a;<br/>          a:=b;<br/>          b:=t;<br/>        end;<br/>function min(a,b:int64):int64;<br/>        begin<br/>          if a>b<br/>            then<br/>              min:=b<br/>            else<br/>              min:=a;<br/>        end;<br/>function max(a,b:int64):int64;<br/>        begin<br/>          if a>b<br/>            then<br/>              max:=a<br/>            else<br/>              max:=b;<br/>        end;<br/>function ex_euclid(a,b:int64;var x,y:int64):int64;<br/>        begin<br/>          if b<>0<br/>            then<br/>              begin<br/>                ex_euclid:=ex_euclid(b,a mod b,x,y);<br/>                x:=x-(a div b)*y;<br/>                swap(x,y);<br/>              end<br/>            else<br/>              begin<br/>                x:=1;<br/>                y:=0;<br/>                ex_euclid:=a;<br/>              end;<br/>        end;<br/>function ceil(a,b:int64):int64;<br/>        var<br/>          c:int64;<br/>        begin<br/>          c:=a div b;<br/>          if (a mod b)*b>0<br/>            then<br/>              ceil:=c+1<br/>            else<br/>              ceil:=c;<br/>        end;<br/>function floor(a,b:int64):int64;<br/>        var<br/>          c:int64;<br/>        begin<br/>          c:=a div b;<br/>          if (a mod b)*b<0<br/>            then<br/>              floor:=c-1<br/>            else<br/>              floor:=c;<br/>        end;<br/>begin<br/>        readln(a,b,c);<br/>        readln(x1,x2);<br/>        readln(y1,y2);<br/>        oa:=a;<br/>        ob:=b;<br/>        c:=-c;<br/>        if (x1>x2)or(y1>y2)<br/>          then<br/>            begin<br/>              writeln(0);<br/>              halt;<br/>            end;<br/>        if (b=0)and(a=0)<br/>          then<br/>           begin<br/>            if (c=0)<br/>              then<br/>                writeln(abs(x2-x1+1)*abs(y2-y1+1))<br/>              else<br/>                writeln(0);<br/>            halt;<br/>           end;<br/>        if b=0<br/>          then<br/>           begin<br/>            if (c mod a=0)and(c div a>=x1)and(c div a<=x2)<br/>             then<br/>              writeln(abs(y2-y1+1))<br/>             else<br/>              writeln(0);<br/>            halt;<br/>           end;<br/>        if a=0<br/>          then<br/>           begin<br/>            if (c mod b=0)and(c div b>=y1)and(c div b<=y2)<br/>             then<br/>              writeln(abs(x2-x1+1))<br/>             else<br/>              writeln(0);<br/>            halt;<br/>           end;<br/>        tx:=1;<br/>        ty:=1;<br/>        if a<0<br/>          then<br/>            tx:=-tx;<br/>        if b<0<br/>          then<br/>            ty:=-ty;<br/>        if c<0<br/>          then<br/>            begin<br/>              tx:=-tx;<br/>              ty:=-ty;<br/>            end;<br/>        a:=abs(a);<br/>        b:=abs(b);<br/>        c:=abs(c);<br/>        k:=ex_euclid(a,b,x,y);<br/>        if c mod k<>0<br/>          then<br/>            begin<br/>              writeln(0);<br/>              halt;<br/>            end;<br/>        x:=x*c div k;<br/>        y:=y*c div k;<br/>        x:=x*tx;<br/>        y:=y*ty;<br/>        a:=oa div k;<br/>        b:=ob div k;<br/>        if (a<0)<br/>          then<br/>            swap(y1,y2);<br/>        if (b<0)<br/>          then<br/>            swap(x1,x2);<br/>        j:=max(ceil(x1-x,b),ceil(y-y2,a));<br/>        k:=min(floor(x2-x,b),floor(y-y1,a));<br/>        if k>=j<br/>          then<br/>            writeln(k-j+1)<br/>          else<br/>            writeln(0);<br/>end.<br/> 

*上述代码引用时请注明本文链接。