前几天，在2009年全国信息学竞赛冬令营中，CCF 的杜秘书长提出了近期要取消 NOIp （全国信息学竞赛分区联赛）的一等奖保送资格，取而代之的是高考加分。有些人就不高兴了，我在冬令营的寝室里就经常听到众多选手的埋怨。接下来，CCF 的网站被黑了，大概也是这个原因。还有就是 cnBeta 里发的这一篇《论NOIP取消保送与CCF被黑——NOIP选手自白》。
网络流是图论中相当重要的一部分，也是计算机科学中比较难掌握的一类知识，在这我就给各位讲一讲网络流的有关知识。要注意的是，网络上，包括很多书籍中关于网络流的名词很容易被理解错，为了方便大家理解，我在这里对很多名词作了详尽解释。
冬令营17日
首先说一下，今天的内容是我目前为止的收获最大的，因为今天的内容很多都涉及到了数学，还有就是晚上论文答辩的时候，吴文虎教授特别提到了一些有关信息学前景以及有关我们学习信息学的目的的问题，吴教授的发言我应该会在冬令营录像发下来之后录进电脑。
上午
内容: 信息学竞赛中的数学建模初探
授课: 李学武, TGC
李学武教授我仰慕很久了，因为李教授在数学理论方面建树颇丰，很有研究。今天听他的讲课更是深有感触。其实学信息学，数学是最重要而且密不可分的模块，不，不是模块，信息学就是数学的一部分，信息学研究的用强大的计算速度解决数学问题，其中有求解的，也有证明的，关于机器证明的那一部分，今年的集训队论文有人提到了，还不够彻底，我记得有一套书叫做《好玩的数学》中有一章就是讲的机器证明，很经典。这部分我以后再谈。
李教授讲的就是有一本数学名著《具体数学》中的一些经典问题，这里我提一下比较重要的部分。
递推关系与求和: 引入是 Josephus (约瑟夫)问题，我们已经知道，关于约瑟夫问题，有模拟的方法可解，但是，有没有更好的方法呢？答案是肯定的，我们观察每次报数出圈，有当前为偶数号的一部分人出圈，接下来，又是新一轮的报数出圈，而且有一部分人成了新的偶数号，我们不难发现，整个出圈的过程，就是一个递归的过程，好，那么我们定义 J(n) 为在有 n 个人的圈上，最后剩下来的人是几号。易得出如下三个递归定义的表达式：
(1) J(1)=1
(2) J(2n)=2J(n)-1
(3) J(2n+1)=2J(n)+1
其中 n 为正整数。
然后我们易得出一个闭形式 (closed form) 的表达式: J(2^m +l)=2l+1.
我们来看一下能不能再化简，我们把 n 化为一个 m 位二进制数，第一位为 B1，最后一位为 Bm，那么我们从那个闭形式表达式惊异地发现，每一次 J(n) 操作，只是把 n 这个二进制数的第一非零位 B1 ，移到 Bm 之后！多么神奇的性质啊！（原因请自己推导）那么，在进行多次 J(n) 操作之后，在进行 J(n) 操作值就会不变了，原因是 n 的所有二进制位都变成 1 了，我们把这样的值叫做“不动点”，这个概念在复合函数中经常提到。多次调用这个函数，不动点会出现在原 n 二进制数中 1 的个数 k 次以下（因为尾部可能有连续的 1），而不动点的值就是 2^(k+1)-1.
我们再把刚刚那些递归定义的式子拓展一下：
(1) f(1)=α
(2) f(2n)=2f(n)+β
(3) f(2n+1)=2f(n)+γ
我们再来尝试用闭形式来描述这些递推式。
观察后知，我们把这个函数写成 f(n)= A(n)α+B(n)β+C(n)γ.
我们列表发现，A(n)事实上是等于 trunc(log n), 而 B(n) 呢，则在 A(n) 不变的周期中随着 n 的增加而从 A(n)-1 递减到 0, C(n) 则恰好相反，在 A(n) 不变的周期中随着 n 的增加而从 0 递增到 A(n)-1. 这些结论，事实上可以由归纳法证明。
接下来，李教授讲了一些关于 sigma 式的化简，由于过于简单，我在这里就不再叙述了。但是李教授提出的思想却是相当好的：
递归<–>求和
| |
>闭形式<
在有诸多表达式形式的情况下，我们要熟练掌握表达式的转化，这样我们才能高效地分析问题，从而解决问题。但这又需要我们有相当扎实的数学理论功底，以前对于名言“数学是无穷的科学”的理解一直停留在“数学题是做不完”的层面(哈哈！)，而我们现在发现，数学的代数变换，几何变换，以及数形结合还有最新的机器解题（信息学）等方面的探索是无穷无尽的，数学是最基础的自然科学，它的发展推动着整个科学界的发展。
下午是 TSU 的周源同学讲随机化算法，由于牵扯到很多概率的知识，我留到以后再讲；晚上答辩时吴文虎教授的讲话，我准备单独地写一篇文章，就不在这里写了。
冬令营 Day 1.
上午
内容: 游戏中的数学模型与解题思路
授课人: 吴文虎教授,TSU.
今天上午是冬令营的第一堂课，按照惯例，第一堂课都是国际信息学奥林匹克中国队总教练清华大学教授吴文虎教授上的。
吴老一上课就给我们演示了一个“人鬼渡河”游戏，游戏规则是：有3人3鬼在东岸，有一条船容量为2，初始停在东岸，若某一岸（包括停在该岸边的船）上的鬼比人多，那么人就会被鬼吃了。请问如何将3人3鬼安全送到西岸？（注意：船不是电动的，必须要人或鬼划船）。
吴教授首先按照东岸的人数与鬼数表示一个状态：东岸的（人数，鬼数），有一些状态是安全的，有一些是不安全的（东岸或西岸鬼比人多），然后考虑状态的转移方式（即决策），转移（人数，鬼数），有：(1,0),(0,1),(1,1),(2,0),(0,2). 然后我们看我们的转移次数，当目前转移是奇数次时，一定是从东到西，所以是状态量减去决策量；若是偶数，则是从西到东，是状态量加上决策量。接下来我们要考虑判重，当我们东岸状态已经达到过并且船在同一侧时，我们需要剪枝。这样，一个标准的广搜就完成了（最初吴教练是用类似递推的方法，不记录历史状态，其实这样是有反例的：当我们把决策的考虑顺序打乱时，我们很容易走进死胡同，没有历史状态就没法回溯，所以是不正确的）。
休息几分钟后，吴教练开始讲递归，简单介绍了与或节点图，然后又简要地提了一下评估函数，东西都很简单，都是讲一下思想，我在这里就不写了。
当然，作为国家队总教练，吴教授讲的都是一些程序设计时的思想方法，比如说人鬼渡河这个例子，我们要从冗长的题目描述中提炼出关键信息，抽象成数学模型，然后从考虑数学模型中转移的方式，找到在数学模型中的转移决策，我们就能够很快地找到解决问题的较优方法。
另外，递归思想事实上是很奇妙的，在数学中也有很广泛的应用，还有很有趣的递归构造的分形Sierpinski三角形，以后我接着写吧。
下午
内容：IOI 2008 试题分析
授课人：周冬，原国家队队员,TSU.
这个试题分析其实就是简要地分析一下年鉴上的 IOI 2008 试题解法。有兴趣的可以去看看年鉴，我就不写了。
内容：博弈论相关
授课人：余林韵,TSU.
很有意思的课，首先这位同学简要介绍了 TSU 的“BIDU杯”程序设计大赛，然后他介绍了最近一届大赛“TankCraft”的情况，事实上就是 AI 竞赛，选手们的 AI 间互相打游戏，胜者为王。我们看了决赛的几个回放，真的很精彩，AI 算法都很强大。只是有一次出了一点小 Bug ，双方的3辆 Tank 都相持不动，因为双方都采用了预测对方策略的算法，而且两边都预计对方下一步会攻击，所以原地不动，很有意思。接下来，这位同学简要介绍了一下博弈论，提到的有 Nash均衡点 等博弈知识，其中有一个例子很有意思：有两个囚犯带枪准备犯案，被警察抓住了，警察发现他们以前也犯过罪，但找不到证据，于是拘留了他们俩，隔离突击审讯。如果两个都没招，那么他们俩因“非法携带枪支”各判一年；若有一个招了，另一个没招，那么，没招的那个会判15年，招了的那个因为是证人所以没有被起诉；如果两个都招了，则各判10年。我们来看一看 Nash 均衡点 在哪里：甲想如果甲不招，乙很可能会招，甲会判15年，而甲招了的话，有可能不会被起诉，也有可能是被判10年。所以，甲会招。同理，乙也会招。所以他们两个各被判10年。所以这个问题的 Nash均衡点 在两个都招了的状态这。说明 Nash均衡点 对于某些问题并不是最优的方案。
晚上
我们去了位于办公楼的机房，很惊讶地发现装的系统是基于 Ubuntu (Linux) 的 NOI Linux 系统，是中国计算机学会 (CCF) 联合北京航空航天大学开发的一套系统，包括一套开源的信息学竞赛 IDE 系统和一套信息学竞赛评测系统，估计 NOIp 2008 就是在这个环境下评测的。很不错的一套系统。
用 Vista 的感觉很好。我一直没用过 Vista ，现在 Vista 和 Windows 7 一起用，感觉真不错哈！
看了柯南兄的Blog，感觉他的操作符描述很模糊，在这里我想讲一遍。
不多废话了：
1 program cnPhil_operator; 2 3 operator **(a,b:longint)p:longint;//定义双longint**操作 4 var q:real; 5 begin 6 q:=exp(b*ln(a)); 7 p:=trunc(q); 8 end; 9 10 operator **(a,b:string)p:longint;//定义双string**操作，注意声明同名运算符时，运算量类型一定不能一样，比如有了一个双integer的-操作，你不能再次声明双integer的-操作，但是你可以声明双string的-操作，否则会重载！ 11 var 12 i,j:longint; 13 ok:integer; 14 begin 15 val(a,i,ok); 16 val(b,j,ok); 17 p:=trunc(i**j);//调用以前声明的双longint的**操作，其实运算符声明也可以递归实现！但此处不是递归，而是利用了运算符可以因不同运算量类型而重复定义的特性。 18 end; 19 20 21 22 23 begin 24 writeln('2^3=',2**3); 25 writeln('''2''^''3''=','2'**'3'); 26 end.
另外贴一张我的本本跑 Vista 的图，现在我的本本可是四系统啊（XP,Vista,Win7,Ubuntu），很强吧？
 |
| 发件人 cnPhil/Photo |
测试数据和完整解题报告在此下载： DropBox | Skydrive
正文：
10月28日_G122_cnPhil_的解题报告
先看哈：
选手列表
编号 姓名 总分
02.mt 02.mt 400.00
standard standard 400.00
–测试器上一角，Orz mt大牛。
简单题目
Easy
时间限制：1s
空间限制：128M
【题目背景】
经典题目自有经典算法。
【题目描述】
给你一个N*M（N,M<=1000）的01矩形，求一个面积最大的不包含数字1的矩形。
【输入数据】
第一行两个数N，M。
接下来N行，每行M个数为0或1。
【输出数据】
一个数ans表示最大空矩形的面积。
Sample
Easy.in
2 4
1 0 0 0
0 1 1 0
Easy.out
3
Solve:
这道题，我是用类动规方法做的。对于一个点，记录其竖直向上、水平向左两条最大可以达到多长，再根据这个点左边、上面的点的值求出以这个点为右下角的矩形最大能达到多少。mlj的方法：枚举每列，求出每两个1或边界之间的最大可取矩形。（预处理时标记每点最左最右双向可取长度）
SB题
SB
时间限制：1s
空间限制：128M
【题目背景】
题如其名啦……
【题目描述】
给你一棵N（N<=10000）个节点的树，求每个点到其他点的最大距离。
【输入数据】
第一行一个数N。
接下来若干行每行两个数k，t描述一条点k到点t的边（输入数据保证无重复边）。
【输出数据】
N行每行一个数表示每个点到其他点的最大距离。
Sample
SB.in
5
1 2
1 3
1 4
4 5
SB.out
2
3
3
2
3
Solve:
这道题，有个两遍深搜的方法：首先对于每个点，先构造树结构（任选一点作为根），回溯时求出它到底层的最长路和次长路，然后再对于每个点i，枚举这个点到根的每个点j，若这一段ij不在j的最长路上，那么用ij长+j的最长路更新i点值，若这一段ij在j的最长路上，那么用ij长+j的次长路更新i点值。另外还有一个树形动规的方法，貌似很难实现：从底层到根，一层一层来，对于一条边u,v，求出去除其后，以u为根，最长的一条 路径（有边就是路，不管是子是父）就等于u连出的边的目标点的最长路径值，然后对v为根也做一遍。最后，加一个废点指向根，求出经过根的最长路径。这个方法被指有误！不知道是我听错了还是怎么地。哪位大牛能给我讲讲这个树形动规的方法？
判断
Compare
时间限制：1s
空间限制：128M
【题目背景】
这不是道水题！这真的不是道水题！这绝对不是道水题！！！
【题目描述】
给你一个n(n<=1000)个点m(m<=n*（n-1）/2)条边的图和k(k<=100)个程序对这个图做从点1到点n的最短路后得到的的结果，写一个compare判断谁的输出最优。
【输入数据】
第一行三个数n，m，k。
接下来m行，每行三个数a，b，data表示点a到点b有一条长度为data的无向边（任意两点间最多只有一条边）。
接下来k行，每行为一个程序得到的路径方案(保证路径方案的长度不超过2000)。
【输出数据】
如果所有输出均不合法，输出’Wrong‘，否则输出一个保留4位小数的实数，表示k个人得出结果中最小的一条合法路径长度。
Sample
Compare.in
3 3 4
1 2 5.2000
2 3 3.5000
3 2 6.0000
1 2 3 2 3 2 3 2 3 2 3 2 3
1 2 2 3 3 3
1 3
1 3 2 3
Compare.out
8.7000
Solve:
我觉得这道题目内容和上一道题的标题很配。
最优序列
Best
时间限制：1s
空间限制：128M
【题目背景】
背景的意义就是没人看得懂……
题目的意义就是没人做得出……
【题目描述】
给出一个长度为n(n<=1000) 的正整数序列，求一个子序列，使得原序列中任意长度为m 的子串中被选出的元素不超过k(k<=m<=10) 个，并且选出的元素之和最大。
【输入数据】
第一行三个数n,m,k 。
第二行n 个数，表示各元素数值大小。
【输出数据】
一个数，表示最大元素和。
Sample:
Best.in
10 4 2
7 3 4 8 2 6 5 7 4 8
Best.out
36
Solve:
与其说是动规，还不如说是搜索。以一个二进制串表示状态情况，然后考虑第i个取不取时，若第i-m个状态值为0，那么这个i状态值一定为0，否则枚举0,1。冷吧！
呃，今天电脑有点卡。
测试数据和解题报告完整版在这里下载：DropBox, Skydrive
正文：
东汉末年，颖川书院，有一日老夫子给他的学生出了一道问题，书院中有一口清澈见底的池塘（什么都看得见），老夫子要吃鱼，池塘里有很多很多鱼，而池塘是一个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;
高斯消元法是一个解线性代数方程组的重要消元法，其重要作用是可以应用于计算机的解线性方程。应为通过它可以构造一个三角矩阵（又称行梯阵式），然后通过迭代的方法求解。
根据高斯消元法的理论，我们只需要n个系数非零的n元方程，即可求解这一方程组。
所以讨论一个n元的行梯阵式，我们只需要看前n行，即可求解。
高斯消元法把一个阵式构造成行梯阵式（三角矩阵）的过程是（只讨论n元矩阵的前n行）：设要求解的未知数分别为x1,x2,x3……xn，有R1……Rn个线性方程，线性方程Ri中xj的系数为aij，则用-(ai1/a11)R1加上Ri来消除Ri的x1项，其中i>1。接下来，同样地，用-(aij/ajj)Rj加上Ri来消除Ri的xj项，其中i>j，且Rj……Rn的x1……x(j-1)项应已被R1……R(j-1)消除。
太抽象了？我给出3*3矩阵的求行梯阵式的过程。
算出行梯阵式后，可以将Rn（即xn）代入R(n-1)求出x(n-1)，然后将xn,x(n-1)代入R(n-2)求x(n-2)，……，一直迭代到求出x1.
懂了吗？呵呵，我的数学研究方向已经从计算机偏向自然科学了。