老师的询问
题目描述：

东汉末年，颖川书院，有一日老夫子给他的学生出了一道问题，书院中有一口清澈见底的池塘（什么都看得见），老夫子要吃鱼，池塘里有很多很多鱼，而池塘是一个n*m的矩形，他希望放置最少的挡板，将池塘分成很多个矩形（包括正方形），使得每个矩形里有且只有一条鱼，而作为老夫子学生的郭嘉很想完成这个任务，所以他把这个任务交给了你，他相信作为长郡中学未来希望的你肯定不差，希望你能很快地解决问题。

例如：
　　n=4，m=3时的一种情况（0表示小方格内无鱼，1表示有鱼）。
0 1 0
0 0 0
1 0 1
0 0 0
　　可以这么分：

0 1 0

0 0 0

——
1|0 1
0|0 0
　　由于池塘边框不需要放置挡板，所以这个分割方案所需的挡板总长度为5。
输入数据：
第一行有两个整数n和m（1≤n,m≤32），描述池塘规模。接下来的n行，每行有m个数字（非“0”即“1”）。每两个数字之间用空格隔开。

输出数据：
对于每组输入数据，输出一行：一个数字，所需挡板的最短总长度。

输入样例：
4 3

0 1 0
0 0 0

1 0 1
0 0 0

输出样例：
5

Solve:

    这一道题mt大牛说用类A*算法，先广搜（枚举每条鱼的矩形），检验状态重复，然后用貌似很不必要的方法剪枝。

袁绍的刁难

题目描述：

黄巾之乱后，郭嘉到了袁绍的统辖地区，结果袁绍想给我们的郭嘉大大一个下马威，且正值他招募将领的时候，于是乎，袁绍就让郭嘉大大去替他招募将领。
　　这时候有很多很多的将领到袁绍处报到（别人家底厚，四世三公哪~~），每个将领的编号依次为1、2、3……N，第i个将领的武力值为3^(i-1)。
　　袁绍需要我们的郭嘉大大招纳任意个将领，而郭嘉选中的将领有一个“总武力值”为各个将领的武力值之和。例如：郭嘉这一次招募了第一个将领和第三个将领，那么“总武力值”为1+9=10。
　　袁绍想知道，他可以获得的第k小的“总武力值”是多少，请你帮助我们的郭嘉大大告诉袁绍这个第k大的“总武力值”。
　　从文件中读入k，输出郭嘉能够获得的，第k大的“总武力值”。

输入：
　　数据包含n+1行，第一行读入n(n≤100)。以下n行每行包含一个k。

输出：
　　输出包含n行，每行输出一个对应的结果。 

输入样例：
1
7

输出样例：
13

样例说明：
　　郭嘉能够拿到的总武力值从小到大为1、3、4、9、10、12、13……所以第7小的总武力值是13。
　　对于50%的输入文件，有k≤5000。
　　对于100%的输入文件，有k≤2^31-1。
Solve:

这道题是很典型的数学归纳题，类似NOIp2006普及组的第三题，把每一个k请求转成2进制，再把这个二进制数乘以三进制的位权（101=>1*3^2+0*3^1+1*3^0），这样就是结果。这是应用排列组合的方法。自己多模拟模拟就可以发现规律。

游历的路线

题目描述：

    我们的郭嘉大大经过一段时间发现了袁绍这个人干大事而惜身，见小利而忘义，又逢曹操在招兵买马，决定逃离袁绍去投曹操，而我们的曹操在第M天招募良材，我们的郭嘉大大既不能早去，也不能晚去，于是乎，他就趁着这一段时间到其他的城市游历一番，而每两个城市之间只能坐马车来往，由于我们的郭嘉大大很贪钱，他想用最少的费用，所以需要我们帮他求出这一个最小的费用。

输入：

第一行包含两个数n，m， 表示有n个城市，和m天后曹操招纳良材。城市一就是郭嘉所在的城市，城市n就是曹操处。接下来n * (n – 1)行描述马车乘坐表。第2到第n行就是描述的城市1到2… n的马车乘坐表，第n + 1到第2n-1行描述的城市2到城市1，3..n的马车乘坐表… … 对每一行，首先有一个数T，表示城市I到城市J的马车以T为周期，接下来有T个数，表示每天的马车的价格，如果价格为0则表示没有马车可坐。

（n <= 100,  m <= 200,  T <= 20， Price <= 50000）
输出:

如果存在这样的路线使郭嘉第m天到达曹操处，则输出最少的费用，否则输出0！

输入样例：                             

3 5                                       

2 130 150

3 75 0 80

2 110 100

4 60 70 60 50

3 0 135 140

2 70 80

输出样例：

355

Solve:

    设F[i,j]表示第i天到第j个城市的最小花费，

    则有：F[i,j]=Min{F[i-1,k]+Effort(i-1,k,j)}  1<=k<=n

    F[n,m]即为所求。

消息的传递

题目描述：

我们的郭嘉大大在曹操这过得逍遥自在，但是有一天曹操给了他一个任务，在建邺城内有N（<=1000）个袁绍的奸细，将他们从1到N进行编号，同时他们之间存在一种传递关系，即若C[i，j]=1，则奸细i能将消息直接传递给奸细j。

现在曹操要发布一个假消息，需要传达给所有奸细，而我们的郭嘉大大则需要传递给尽量少的奸细使所有的奸细都知道这一个消息，问我们至少要传给几个奸细

输入：

    文件的第一行为N，第二行至第N+1行为N*N的矩阵（若第I行第J列为1，则奸细I能将消息直接传递给奸细J，若第I行第J列为0，则奸细I不能将消息直接传递给奸细J）。

输出:

    输出文件只有一行：即我们的郭嘉大大首先至少要传递的奸细个数。

 

输入样例：                             

8

0 0 1 0 0 0 0 0 

1 0 0 1 0 0 0 0 

0 1 0 1 1 0 0 0 

0 0 0 0 0 1 0 0 

0 0 0 1 0 0 0 0 

0 0 0 1 0 0 0 0 

0 0 0 1 0 0 0 1

0 0 0 0 0 0 1 0

输出样例：

2

Solve:

    很经典的图论题目哦。

    首先，求出图中所有强连通分量(Strongly Connected Component, SCC)，然后把每个强连通分量缩为一个“点”，此时原图就变成了一个标准的拓扑图。入度为0的“点”即为所求。

    强连通分量的求法：（这里给出刘铮同学的求出一个点所在的强连通分量的过程）

procedure zuo(r:longint);

var

  i,j,q:longint;

begin

  inc(p);  //建栈

  b[p]:=r;//r点入栈

  a[r]:=p;//r点在栈中的位置

  c[r]:=p;//r点能连出的最前的点，初值为自己。（link）

  i:=v3[r];//选边集数组中r出的一条边。

  while i<>0 do begin

    j:=v1[i];//得到当前边的目标结点

    if(d[j]=0)then begin//如果j点当前不属于任何强连通分量

      if a[j]=0 then zuo(j);//并且j没有进栈，则求j的强连通分量

      if(c[j]<c[r])and(a[j]<>0) then c[r]:=c[j];//若j的link值在r之前，且j未出栈，则更新link值

    end;

    i:=v2[i];//下一条r出的边

  end;

  if c[r]=a[r] then begin//若r不能连到前面，则r和r栈以后的点全部出栈。

      q:=a[r];

      for i:=a[r] to p do begin

        d[b[i]]:=r;

        a[b[i]]:=0;

        c[b[i]]:=0;

      end;

      p:=q-1;

  end;

end;