05年7月21日我在我的Blog上发了我的第一篇日志（那时我还是用的MSN Space），到现在已经坚持写了三年，一共写了537篇日志。我选出了50篇精彩的原创和半原创文章，以此来纪念我Blog的三岁生日，另外也方便新来的朋友快速查阅以前的精华文章。

1. 原创科普说明文：递归
假期的一篇作文，叫我们写任一说明文。我把这篇作文发到了我的Blog上。这可能是我Blog最早的技术文章，它确定了我以后类似文章的写作风格。

2. 非常奇妙的证明：图形必在格点之外
翻译的cut-the-knot上的一篇文章。这是我所见到的最elegant的证明之一，在饭桌上提到证明问题时我经常会举这个例子。几个好友很早就开始阅读我的Blog，他们一致认为这是最令人难忘的一篇日志。

3. 几个把平面几何问题的辅助线做到空间去的数学趣题
也是翻译的cut-the-knot上的系列文章，当时觉得确实非常神奇。后来的学习发现，其实射影几何中有更多有趣的例子。

4. 追溯羊与车：Monty Hall Dilemma问题的故事
我们数学老师提到了Monty Hall问题，他的说法是错误的，因此才写下这篇文章。当时写这篇文章主要是给我的同学看，因为那时这个Blog几乎只有我们同学才上。

5. 几个很强的数列
这是我在The On-Line Encyclopedia of Integer Sequences找到的，非常强。不是经常有考什么数列找规律的么？从这里面随便挑一个来，不查数列百科全书的话别人几乎不可能找出规律来。

查看更多 »

傻B聪送了我一个Mr.P出品的猥琐便笺纸。纸上整整齐齐地打了一个洞，可以插一支铅笔。
古汉MM送了我一个鼠标垫。
N多天没理我的Stetson MM今天在校内上给我发了个消息。
小猫告诉我说她又要恢复单身了。
手机、校内和Blog上收到无数多的生日祝福。
FOX给我带来了House有史以来第二精彩的episode。（第一精彩的？here）

昨天晚上（严格的来说是前天晚上）六个人去巴贝拉，吃得很疯狂。然后玩电动，抓了一大把的娃娃。晚上在17英里通宵K歌，有MM。

查看更多 »

第一次呼吸这个世界的空气。
体验一次溺水濒死的感觉。
目睹一次大自然未解之谜。
第一次看到雪景。
第一次与父亲争辩并取胜。
参加一次集体舞比赛。
用两位数的加法鄙视一个同班的孩子。
用三位数的乘法鄙视一个同班的孩子。
用速算诀窍鄙视一个老师。
赢得一个实习老师的喜爱（她送了我一个纸折的鸽子）。
在语文考试中获得唯一一个满分。
第一次发现软盘的写保护位置。
学习使用一个操作系统。
学习使用另一个操作系统。
写一个VB程序。
做一个网页放在网上。
查看更多 »

    写Blog是一件很有意义的事。我可以在Blog里总结学习经验，写下自己的心情故事，和大家分享一些好玩的东西，更重要的是通过这个平台我结识了很多好友，其中甚至有一些可爱的MM。在这里感谢所有人对这个Blog的支持，祝大家RP加加，MM多多。

之所以没公布标程，是因为个人觉得标程写得比较丑。
既然有人需要就发布一下吧，标程丑总比没有标程好。

Problem 1
program whyleast;

procedure solve(t,a,b:integer);
begin
   if t=0 then exit else
   begin
      solve(t-1,a,b);
      writeln(a,' ',2);
      solve(t-1,b,a);
      writeln(2,' ',b);
      solve(t-1,a,b);
   end;
end;

{====main====}
var
   n,i:integer;
   ans:longint=1;
begin
  assign(input,'whyleast.in');
  reset(input);
  assign(output,'whyleast.out');
  rewrite(output);
  
  readln(n);
  for i:=1 to n do ans:=ans*3;
  writeln(ans-1);
  solve(n,1,3);
  
  close(input);
  close(output);
end.



Problem 2
program height;

const
   OutputString:array[boolean]of string=('YES','NO');

type
   rec1=record
          h,p:longint;
        end;

   pointer=^rec2;
   rec2=record
          x,y:longint;
          dir:boolean;
          next:pointer;
        end;
var
   orderHeight : array[1..100000]of longint;
   SortHeight  : array[1..100000]of rec1;
   Deg,DegHash : array[0..100000]of longint;
   EdgeHash    : array[1..100000]of pointer;
   n,m,DegCount:longint;

procedure SwapRec(var t1,t2:rec1);
var
   t3:rec1;
begin
   t3:=t1;
   t1:=t2;
   t2:=t3;
end;

procedure SwapInt(var t1,t2:longint);
var
   t3:longint;
begin
   t3:=t1;
   t1:=t2;
   t2:=t3;
end;

function InsertEdgeHash(x,y:longint):integer;
var
   newp:pointer;
begin
   new(newp);
   newp^.x:=x;
   newp^.y:=y;

   if orderHeight[x] > orderHeight[y] then
      newp^.dir:=( 1.25*OrderHeight[y] <= orderHeight[x] )
   else newp^.dir:=( 1.25*OrderHeight[x] > orderHeight[y] );
   newp^.dir:=not newp^.dir;

   newp^.next:=EdgeHash[x];
   EdgeHash[x]:=newp;
   exit( ord( newp^.dir ) );
end;

function FindEdgeHash(x,y:longint):integer;
         { -1: Not Found;  0: x-->y  1: x<--y
            x Always Smaller than y }
var
   now:pointer;
begin
   now:=EdgeHash[x];
   while now<>nil do
   begin
      if now^.y=y then
      begin
         now^.dir:=not now^.dir;
         exit( ord( now^.dir ) );
      end;
      now:=now^.next;
   end;
   exit(-1);
end;

procedure UpdateDeg(t,c:longint);
begin
   if deg[t]<>c then
   begin
     dec(DegHash[Deg[t]]);
     if DegHash[Deg[t]]=0 then dec(DegCount);
     inc(DegHash[c]);
     if DegHash[c]=1 then inc(DegCount);
     Deg[t]:=c;
   end;
end;

procedure ReadHeight;
var
   i:longint;
begin
   readln(n,m);
   for i:=1 to n do
   begin
      readln(OrderHeight[i]);
      SortHeight[i].h:=OrderHeight[i];
      SortHeight[i].p:=i;
   end;
end;

procedure Sort(l,r:longint);
var
   i,j,mid:longint;
begin
   i:=l;
   j:=r;
   mid:=SortHeight[(i+j)div 2].h;
   repeat
      while SortHeight[i].h<mid do inc(i);
      while SortHeight[j].h>mid do dec(j);
      if i<=j then
      begin
         SwapRec(SortHeight[i],SortHeight[j]);
         inc(i);
         dec(j);
      end;
   until i>j;
   if l<j then Sort(l,j);
   if i<r then Sort(i,r);
end;

procedure Init;
var
   low:longint=1;
   high:longint=1;
   i:longint;
begin
   DegHash[0]:=n;
   DegCount:=1;
   for i:=1 to n do
   begin
      while SortHeight[low].h*1.25 < SortHeight[i].h do inc(low);
      while ( high<n ) and ( SortHeight[i].h*1.25 >= SortHeight[high+1].h ) do inc(high);
      UpdateDeg( SortHeight[i].p, high+low-i );
   end;
end;

procedure Solve;
var
   i,x,y:longint;
   dir:integer;
   newp:pointer;
begin
   for i:=1 to m do
   begin
      readln(x,y);
      if x>y then SwapInt(x,y);
      dir:=FindEdgeHash(x,y);
      if dir=-1 then dir:=InsertEdgeHash(x,y);
      if dir=0 then SwapInt(x,y);
      UpdateDeg(x,Deg[x]+1);
      UpdateDeg(y,Deg[y]-1);
      writeln( OutputString[DegCount=n] );
   end;
end;

{====main====}
begin
   assign(input,'height.in');
   reset(input);
   assign(output,'height.out');
   rewrite(output);

   ReadHeight;
   Sort(1,n);
   Init;
   Solve;

   close(input);
   close(output);
end.




Problem 3
program wolf;

type
   rec=record
          left,right:integer;
       end;

const
   infinite=maxlongint div 3-100000;
   //Make sure no overflows occur

var
   k,n,m  : integer;
   map    : array[1..1000,1..1000]of longint;
   dist   : array[1..1000]of longint;
   hash   : array[1..1000]of boolean;
   father : array[1..1000]of longint;

   tree : array[1..1000]of rec;
   attk : array[1..1000]of longint;
   cost : array[1..1000]of integer;
   minf : array[1..1000,0..100]of longint;

procedure readp;
var
   i,x,y,d:longint;
begin
   readln(k,n,m);
   for i:=2 to n do
      readln(attk[i],cost[i]);
   for i:=1 to m do
   begin
      readln(x,y,d);
      map[x,y]:=d;
      map[y,x]:=d;
   end;
end;

procedure init;
var
   i,j:longint;
begin
   for i:=2 to n do dist[i]:=infinite;
   for i:=2 to n do hash[i]:=false;
   dist[1]:=0;
   hash[1]:=true;

   for i:=1 to n do
   for j:=1 to n do
      if map[i,j]=0 then map[i,j]:=infinite;

   for i:=1 to n do
   for j:=1 to k do
      minf[i,j]:=-infinite;
end;

procedure sssp;
var
   i,j:longint;
   min:longint=0;
   minj:longint=1;
begin
   for i:=1 to n-1 do
   begin
      for j:=1 to n do if not hash[j] then
      begin
         if ( min+map[minj,j] = dist[j] ) and ( father[j] > minj ) then
           father[j]:=minj
         else if min+map[minj,j] < dist[j] then
         begin
           dist[j]:=min + map[minj,j];
           father[j]:=minj;
         end;
      end;

      min:=infinite;
      for j:=1 to n do if not hash[j] and (dist[j]<min) then
      begin
         minj:=j;
         min:=dist[j];
      end;

      tree[ minj ].right:=tree[ father[minj] ].left;
      tree[ father[minj] ].left:=minj;
      hash[ minj ]:=true;
   end;
end;

function solve(x,y:longint):longint;  //(node,cost)

   procedure update(var t1:longint;t2:longint);
   begin
      if t1<t2 then t1:=t2;
   end;

var
   ans:longint=-infinite;
   i,t:longint;
begin
   if minf[x,y]<>-infinite then exit(minf[x,y]);
   if y>=cost[x] then ans:=attk[x];

   if tree[x].left>0 then update(ans,solve(tree[x].left,y)+attk[x]);
  
   if tree[x].right>0 then
   begin
      update(ans,solve(tree[x].right,y));
      if y-cost[x]>0 then
         update(ans,solve(tree[x].right,y-cost[x])+attk[x]);
   end;
  
   if (tree[x].left>0) and (tree[x].right>0) then
      for i:=1 to y-1 do
         update(ans,solve(tree[x].left,i)+solve(tree[x].right,y-i)+attk[x]);

   minf[x,y]:=ans;
   exit(minf[x,y]);
end;

procedure writep;
var
   ans:longint=-infinite;
   i,j:integer;
begin
   for i:=0 to k do
     if solve(1,i)>ans then ans:=solve(1,i);
   writeln(ans);
  
   {===For Debug===
   for i:=1 to n do
   begin
      for j:=1 to k do write(minf[i,j]:3);
      writeln;
   end;
   for i:=1 to n do writeln(tree[i].left,' ',tree[i].right);
   }
end;

{====main====}
begin
   assign(input,'wolf.in');
   reset(input);
   assign(output,'wolf.out');
   rewrite(output);

   readp;
   init;
   sssp;
   writep;

   close(input);
   close(output);
end.




Problem 4
program garden;

const
   dir:array[1..4,1..2]of integer=
     ((1,0),(0,1),(-1,0),(0,-1));

type
   arr=array[1..10]of integer;
   rec=record x,y:integer;end;

var
   map:array[0..11,0..11]of boolean;
   ans:array[1..100]of rec;
   n,m,max:integer;
   step:integer=1;
   state:arr;

procedure readp;
var
   i,j:integer;
   ch:char;
begin
   readln(m,n);
   for i:=1 to n do
   begin
      for j:=1 to m do
      begin
         read(ch);
         map[i,j]:=(ch='1');
         inc(max,ord( map[i,j] ))
      end;
   readln;
   end;
end;

procedure writep;
var
   i:integer;
begin
   for i:=1 to step do
      writeln( '(' , ans[i].x , ',' , ans[i].y , ')' );
end;

procedure solve(x,y:integer);
var
   tx,ty,d:integer;
   step_cache:integer;
   state_cache:arr;
begin
   step_cache:=step;
   state_cache:=state;
   if step=max then
   begin
      writep;
      exit;
   end;

   for d:=1 to 4 do
   begin
      tx:=x+dir[d,1];
      ty:=y+dir[d,2];
      while map[tx,ty] and ( not state[tx] and(1 shl (ty-1) )>0) do
      begin
         inc(step);
         ans[step].x:=tx;
         ans[step].y:=ty;
         state[tx]:=state[tx] or ( 1 shl (ty-1) );
         tx:=tx+dir[d,1];
         ty:=ty+dir[d,2];
      end;

      tx:=tx-dir[d,1];
      ty:=ty-dir[d,2];
      if (tx<>x) or (ty<>y) then solve(tx,ty);
      state:=state_cache;
      step:=step_cache;
   end;
end;

{====main====}
var
   i,j:integer;
begin
   assign(input,'garden.in');
   reset(input);
   assign(output,'garden.out');
   rewrite(output);

   readp;
   for i:=1 to n do
   for j:=1 to m do
     if map[i,j] then
     begin
        ans[1].x:=i;
        ans[1].y:=j;
        state[i]:=1 shl (j-1);
        solve(i,j);
        state[i]:=0;
     end;

   close(input);
   close(output);
end.

依然欢迎大家来挑错

注：本日志请勿转载！

    我的第一篇日记是这一年的7月10日写的，因此这一年的5月16日具体发生了什么我已经忘记了。直到看到了这一年的年度总结，我才想起这一天是如何度过的。在04年的年度总结中，我写到：

    年初，我的第一次恋爱（与ZJ）因我的过分要求和渴望、学习压力、突发事件等各方面原因而渐渐走向危险的一端，酝酿半年的感情灾难在5月份突然爆发，一年历程的感情抛物线在2003年12月31日走到最高点，在2004年5月16日落在了x轴下方。2004年5月16日，我的16岁生日的晚上22:20，我到了ZJ的楼下疯狂地呼唤她，幻想能听见她的回答。此后，我俩有意回避，直到她和我进入不同的高中。

    很遗憾，至于那天以及那天的前后到底发生了些什么，上述文字是我唯一能记起的东西。我记得我下了晚自习后快速跑到她回家的必经之路，但却没有等到她。等她的过程中我遇见了另一个同学（忘记是谁了）。后来我沿路返回，又选了另外一条路跑到了她家楼下。很久以后某天我因别的事走过与这完全相同的路线，才发现当时我跑过的路有多么长。很多人说失恋那天会下雨，这是不正确的。我记得那天没有下雨。
    根据一项不完全统计，痴情的我似乎以后注定要踏上OI之路。

    05年10月11日前日记都是在我的PDA上写的，使用的DayNotez软件。10月11日那天在学校大礼堂观看英语歌比赛时PDA撞在了椅子的金属支架上，完全坏了，此后自己用Delphi写了一个程序继续在电脑上写日记。再后来我成功抢救回了PDA上的旧日记，但有一段日记少了几个字节，这段日记包括这年5月16日的日记。
    在这篇不完整的日记里，我看到我当天起床后的第一件事是上网更改了QQ资料的年龄。这是我最后一次更改QQ资料，一个多月后我就放弃QQ开始使用MSN了。当天上午的数学任课老师发生了变动。中午妈妈送了贺卡和一块小蛋糕。下午某个可能是来上门推销的工作人员在我们班的教室安装了一套非常破的英语教学软件，作为教室电脑的管理员我整理了很久。当时我是地理科代表，正负责收书费。到了晚自习时钱仍没有收齐，自己垫钱交给了地理老师。
    晚自习看了科幻世界的一篇文章，王晋康《一生的故事》。它比起《Stories of Your Life》差远了，但我觉得WS可能会喜欢这样的软科幻。于是跑到11班教室去，把这期的科幻世界给她，推荐她看这篇文章，并在里面夹了一张纸条说想请她周末看电影。下了晚自习后我出去在校门口的小书店买了《月亮孩子》。印象中这本书我没有看完，因为我后来渐渐不喜欢看科幻小说了。日记中我写道，WS和DQ没有送我生日礼物。WS和DQ是我认识的好朋友，属于非常少有的那种很感性的女生。她们没有送我生日礼物的唯一可能的原因就是忘记或记错了我的生日。后来我告诉她们我的生日已经过了，20日她们合送了一件短袖T恤。月底我开始喜欢上DQ，年底分手，分手那天的感情记录在了这里。DQ喜欢用23这个名字，因为她的名字中有个字写出来很像数字“23”。
    日记的最后我简单地写道：“晚雨，思ZJ”。那天下了晚自习后我淋着雨站在ZJ经常出现的地方，有一种她似乎随时会出现的感觉。耳边隐隐约约听到她的声音在说，你怎么又没带伞。日记中类似的语言是最后一次出现了。曾经有人向我倾诉说他逃脱不了失恋的阴影，怎么也忘不了那个她。我告诉他，失恋的阴影消失得比你想象中的快，一年以后你将很难再想起她来。
    这可能是我心理最复杂的一个生日。

    这一天离我后来完全停课的时间恰好一个月。谁也没有想到我在这个班级只剩30天的时间了。
    日记的第一句话是“生日，无感”。和前一年恰好相反，人生最重要的一天里我竟然没有任何感慨。若不是我早上来到教室发现桌子上有一颗糖，那天我将永远不会意识到我是在度过我18岁的生日。直到现在我也不知道，那颗糖是谁放在我桌子上的。这个细节我可能永远也忘不了，或许在38岁，48岁时我还会在想当初究竟是谁送了我这个小礼物。除此之外我当天没有收到任何礼物。
    那天我和数学老师讨论了一下第二天公开课的事情，因为我要帮忙制作教学课件。下午年级需要选送一个十佳学生报上去，年级主任把我和班上的一个女生叫到了办公室。我当场把机会让给了那个女生。我只在竞赛方面得过几个破奖，然而她的文艺、主持、英语等各方面能力让她小有名气。下午三四节课年级组织看电影《雷雨》，以配合几天后的语文教学。那一个多小时我一直在睡觉，甚至还梦到了一道OI题。后来语文课上老师叫大家谈《雷雨》观后感时我什么都说不出来。
    这一天是星期二，星期二的晚上有历史听写和新的一集24。晚自习的听写我挂得很惨，这天的24倒是不错。这一年是我第一次追美剧看，原来都是下载的已经结束的剧集。这天的24已经是第五季快结束了，回想一下这个学期竟是每周一集的24陪伴我度过的。

    大家或许会注意到，在这个Blog的标签里，所有以某个人作为标签的算“小猫”最大，这个名字也在友链中排第一。不知道为什么，我对这个矮矮的小女生有一种特别的感觉，直到今天。在手机里，短信数和通话时间最多的应该就是和她了。在这一天，她和我开了一系列让我恼火的玩笑——把我的手表藏在教室里的某个角落让我找。我至今仍不知道她在这一天玩这样的游戏代表什么意思。或许是我自作多情吧，有时女生的一个随意的动作也可能会让我猜想她有没有什么意图。我竭力想装作自己对某些东西看得很轻，然而实际上陷得最深的往往就是我。

    05年的9月份我开始每天记录一个词语作为当天的“单词化日记”。这个想法可能（我也忘记了）是来自安妮宝贝的一本书的彩页，上面是一张张日历，每一天的格子里都写有一个词。虽然我喜欢这种日记形式，但我仍然巨讨厌安妮宝贝这种小女生看的东西，也很不喜欢被她这些东西搞得神经兮兮的女孩子。我很高兴看到很多网友也在进行这种“单词化日记”形式的记录。任何一件事持久做下去都是有意义的，最终会获得好评，比如那个每天照大头像照了几年的人。
    这一天的单词是“暴光”，因为我的MSN Space（那时我在用MSN Space）被一中的同学发现了。OIBH上的很多重庆的OIer，还有我的很多老同学（包括ZJ）都在一中，Blog的读者将很快不再限于我们学校的OI组和班上的同学。从这次“暴光”开始，我的Blog里个人的东西慢慢地少了，日志内容也开始面向更多的OIer。年底我申请了付费空间和国际域名，搭建了私人Blog。很多人写Blog是越写越觉得没劲，但我坚持了下来，这个Blog已经快要两岁了。
    这篇日志就是生日那天我在MSN Space上写的日志。日期是17号可能是因为我是凌晨写的。从这篇日志来看，我的18岁生日是非常普通的一天。

    凌晨2:00。
    我把所有的灯都关了，一个人躺在沙发上，望着漆黑的天花板，iPod里放着S.H.E的新专辑。眼角流出两滴眼泪，并不是因为我伤心，而是因为我困了。但我不想睡觉。这一年我做的最多的事情就是睡觉了。
    前天我回了一趟学校，高三年级要照集体照留念。遇见了理科班的那一帮兄弟，大家仍然是开玩笑地疯打了一会儿。但我悲哀地发现，我几乎无法和我们班的同学交流了。除了四五个要好的朋友外我没有和我们班其他人打招呼。我甚至发现我已经认不出一些同班同学了。
    脱离集体近一年让我真正体会到了什么叫孤独。和其它高三学生一样，我的“高三”心里也是阴暗的。我不能浪费了这些时间，于是我开始学语言，做网页，写文章。只要自己能忙起来就不会觉得孤独了。19岁生日之际，我组织了一次生日邀请赛充实了一下自己的生活，收到了有史以来最多的生日祝福。

    听完了，S.H.E的新专辑非常有个性。我从沙发上起来，打开电脑开始看新的一集Lost。其实这也不算新的一集，只是上个星期留下来的。上个星期比较忙，因此有一集Lost还没看。
    这一集Lost的主角是Ben，故事中穿插了几段Ben的回忆。这一集的故事时间正好是Ben的生日，而每一个回忆的片段都发生在Ben以前某个生日。他这一生的故事由这一串回忆拼凑了起来。很巧，今天也是我的生日。我突然想知道，我的前几个生日又发生了什么。具体我是什么时候记的日记我已经记不清了，可能16岁的时候已经在写日记了吧。16岁到18岁是成人的标志，是人生最重要的阶段，在这期间我到底做过什么？
    我翻看起我的日记来。眼前是许多一闪而过的片段。我曾经失恋，曾经淋雨，我也曾经快乐，曾经辉煌。我想起了一颗糖之谜，想起了糟糕的历史听写，想起了《雷雨》，想起了《一生的故事》……我决定写下我能记起的每一个生日里发生的事。现在我的日记有14.7万字。我希望当我的日记有100万字时我还能像今天这样书写我的故事。
    每个人都有自己的故事。


Matrix67原创
本日志请勿转载！

题目在这里：http://www.matrix67.com/blog/article.asp?id=241

如果机房马上要关门了，或者你急着要和MM约会，请看简要题解：

1. 用类似于传统hanoi的递归方法可以做到3^n-1次。这显然是最多的了，因为总的状态数也只有3^n个。
2. 可以证明，竞赛图中不存在环当且仅当所有顶点的出度从小到大排列依次为0, 1, 2, ... , n-1 。
3. 在最短路树上做树状DP，需要多叉转二叉。注意几种需要输出0的情况。
4. 搜索，算是练基本功了。用位运算优化，不加任何剪枝就能过。

否则，请慢慢阅读——

Problem 1: 为什么最少
    如果你还不熟悉Hanoi塔的解法，去题目中提到的那篇日志看看吧。如果你已经熟悉Hanoi塔的解法，你会立刻想到这道题的解法：依然是递归地解决。至于怎么递归，样例已经告诉我们了：把前n-1个金片从1号柱搬到3号柱，把第n片移到2号柱，又把那n-1片从3号柱搬回1号柱，再把第n片搬到3号柱，最后把那n-1个金片又搬过来，完成整个操作。
    我们下面解决三个问题：为什么这样不会重复出现状态，这样的移动步数是多少，为什么这样的操作步数是最多的。
    为什么这样不会出现重复的状态呢？因为我们假设前n-1个金片的移动过程中没有重复状态，而三次对n-1的调用时整个状态由于第n个金片的位置不同而不同。
    这样的方法获得的操作步数是多少呢？答案是3^n-1。我们可以用数学归纳法证明，n=1时步数为2显然正确，而f(n+1)=3f(n)+2=3*(3^n-1)+2=3^(n+1)-1。
    为什么这样的操作步数是最多的呢？废话，这样的操作步数当然是最多的，因为总的状态数也只有3^n个（每个金片的三种可能的位置确定了一种状态），你的移动步骤能比这个数目还多就见鬼了。

    这道题有人用了math库，没有提供math库导致无法编译是我的失误，向大家道歉。

    Hanoi问题的变种太多了，比如多根柱子、单向移动、双色金片等等。dd上次不是也出了一题么。

    这题代码很短，我公布在下面。
program whyleast;

procedure solve(t,a,b:integer);
begin
   if t=0 then exit else
   begin
      solve(t-1,a,b);
      writeln(a,' ',2);
      solve(t-1,b,a);
      writeln(2,' ',b);
      solve(t-1,a,b);
   end;
end;

{====main====}
var
   n,i:integer;
   ans:longint=1;
begin
   assign(input,'whyleast.in');
   reset(input);
   assign(output,'whyleast.out');
   rewrite(output);
  
   readln(n);
   for i:=1 to n do ans:=ans*3;
   writeln(ans-1);
   solve(n,1,3);
  
   close(input);
   close(output);
end.


Problem 2: 身高控制计划
    一个竞赛图是指任两个点之间都有一条有向边的图。竞赛图有很多奇妙的性质，比如一个竞赛图必然存在一条经过所有节点的路等等。
    下面我们证明，竞赛图中不存在环当且仅当所有顶点的出度从小到大排列依次为0, 1, 2, ... , n-1 ：
    如果一个有向图的所有点出度都至少为1，那么这个图一定有环，因为在找到环之前DFS总可以找到新的节点。如果有向图无环，必然存在一个点没有出度。由于任两点之间都有有向边，那么其它所有点都要连一条边指向它，这样其它所有点的出度都至少为1了。删掉这个出度为0的点后剩下的图仍然无环，不断对剩下的图继续上面的过程就得到了我们的结论。
    现在我们的算法就很明确了，首先统计初始状态下的出度，然后设计某种数据结构完成两种操作：改变一个数（加一减一），询问所有数是否恰好为0, 1, 2, ... , n-1 。
    统计初始状态下的出度方法有很多，这里介绍两个。首先对身高排序，然后对于每个人进行二分，寻找有序数列中该数的4/5和5/4各在什么地方。还有一种方法也是先排序，然后从左到右扫描整个序列，并保持两个指针始终指向4/5和5/4处。每次开始处理一个新的数时都把两个指针适当地右移直到超出了这个数的4/5或5/4为止。两种方法都是O(nlogn)。别以为第二种方法是线性的哦，线性算法之前还有一个排序呢。
    操作的处理也有不少方法。最简单的方法就是统计当前图中出度的数目有多少种。就是说，用a[i]表示出度为i的点有多少个，然后不断更新a[i]>0的有多少个。当这个数目等于n时我们就认为图中没有环（因为出度可能的取值只有从0到n-1共n种）。
    注意，由于同一条边可能被操作多次，因此需要一个Hash表（开散列）来判重。具体地说，你需要判断这条边以前被操作过奇数次还是偶数次，以决定哪边的出度要增加，哪边的出度要减小。


Problem 3: 狼的复仇

    把这个问题中所有的最短路都画出来是什么样子？它一定是一棵树！为什么？首先，图肯定是连通的，因为源点到任一个点都有一条最短路；其次，图肯定无环，因为源点到任一个点只有一条最短路（环的出现将意味着某些点有更短的路存在）。仔细想一下Dijkstra的算法过程，不难想到Dijkstra算法的实质就是在建这棵树——每一次由x节点加上边x-y扩展到y节点就记作x是y的父亲。注意观察上图中左图是如何变成右图的。这样，题目变成了这种形式：在有根树上，除根节点之外的其它节点中选择一些节点，使得这些节点和它们所有祖先的权值和最大。这是一个经典的树型动态规划模型。我们用f[i,j]表示以节点i为根节点的子树花费j个单位的材料最多可以得到多大的攻击力。令节点1的材料和攻击力都为0，那么最后输出f[1,0..k]中的最大值即可。决策分为两类，要么该位置建一个塔，要么把所有材料适当地分给儿子（自己就不需要再建了）。但这样的复杂度太高，我们需要用DP嵌套或者更巧妙的多叉转二叉来解决。
    DP嵌套理解起来更简单，它主要是解决这样一个子问题：若某个节点有m个儿子，我们需要寻找当j1+j2+...+jm等于某个定值时f[儿子1,j1]+f[儿子2,j2]+...+f[儿子m,jm]的最大值。这个子问题与我的某次模拟赛中论文课题选择那道DP题几乎是一模一样，看一看那道题就明白了。下面简单描述多叉转二叉的方法。

    如果你还不知道多叉转二叉的话，这道题是一个绝好的学习材料。一棵多叉树可以用“左儿子右兄弟”的方法转为二叉树，具体的说就是把多叉树转化为这种形式：节点的左儿子才是真正的儿子，节点的右儿子只是和它同辈的兄弟。注意看上图的左图是如何变成右图的。现在，我们的f[i,j]表示在这棵二叉树上的子树花费j个材料的最大值。它有这样五种决策：
    1. 自己把材料用了；
    2. 自己把材料用了后剩下的给右边；
    3. j个材料全部用到左边去，加上自己的权值；
    4. j个材料全部用到右边去，不加自己的权值；
    5. j个材料左边用一点，右边用一点，加上自己的权值。
    注意思考决策3-5中为什么有的决策要算自己的权值，有的不算自己的权值。转化后的二叉树并不是原来的树，左边和右边的意义是不同的。在原图中对比一下你就能看到这些决策的实质了。
    状态O(nk)个，决策为O(k)，因此这道题可以在O(nk^2)的时间内解决。

    这题有很多细节需要注意。比如，建树时如何处理多条最短路优先选择编号较小节点，解决方法是在Dijkstra的更新过程中，当新的最短路与原来相同但新的父亲比原父亲编号小时仍然要更新。还有几种特殊情况需要输出0，比如所有的花费都大于k时，再比如所有的攻击力都小于0时。


Problem 4: 和MM逛花园
    这题搜索，DFS枚举方向，没什么好说的。在这里说一下位运算优化。
    用State[x]表示第x行的状态（0表示还没走过，1表示已经走过），用Map[x,y]表示地图第x行第y列的位置是否有景点。假如当前位置是(x,y)，枚举方向d后进行下面的while循环可以飞快地确定最终状态。细心的人会发现State的储存是“反”的（和实际状态左右颠倒）。这没关系，只要State的储存一直是反的就没事了。
const
   dir:array[1..4,1..2]of integer=
     ((1,0),(0,1),(-1,0),(0,-1));
while Map[x,y] and ( not State[x] and (1 shl (y-1) )>0) do
begin
   x:=x+dir[d,1];
   y:=y+dir[d,2];
   State[x]:=State[x] or ( 1 shl (y-1) );
   ...
end;
    我的数据都是唯一解，因此你不用麻烦着写check了。


Matrix67原创
转贴请注明出处

大家帮忙校对，我先睡觉了

注：
1. 名称后带有(1)、(2)的是多次提交相同文件名，系统自动重命名的结果
2. 里面的那个“matrix67”不是我，是另外的人在捣乱（我就不说是谁了: ) ）。

更多消息：http://www.oibh.org/bbs/thread-14911-1-1.html
详细的题解近期发布