记08年北大ACM选拔赛（转载）

早晨7:40的闹铃。到36楼下面见到了我的两个队友后，随便吃了点东西就出发了。

计算中心门前特别热闹，N多人围在一张大桌子前，好像是在签到。我挤进去找了半天发现没我的名字，名单上全是信科的人。我抬头问，中文的在哪儿呢。一个美女姐姐用手指了远处的一个几乎没人的地方说“中文的在那边”，并说了一句“哇，中文的呀，太牛B了”。我顺着她手指的方向望过去，另一张小桌子前面贴了“中文”二字，桌子后面没有人，估计是交给了旁边负责数院和元培的人，让他们顺便管一下。从我目前所了解的情况来看，那张桌子应该是特别为我准备的，它在历史上很可能是第一次出现。

第四题是做得最顺利的一道题。我把所有题粗略看了一遍后，首先决定就想这道题。题目描述巨简单，就是问你沿对角线把一个正n边形剖分成三角形和四边形有多少种方法。上图显示了n=5时所有的10种方法。熟悉组合数学的人都知道，三角形剖分方案对应的是Catalan数列，其递推公式的推导相当经典。设C(n)表示凸n+2边形的剖分方案数，枚举底边和哪一个点相连（下图左），容易看出C(n) = C(0)*C(n-1) + C(1)*C(n-2) + … + C(n-1)*C(0)。

现在，如果剖分中允许有四边形的出现，又该怎么办呢？看看数据规模n≤5000，估计应该是叫我们寻找类似的递推公式。容易想到，我们可以枚举底边与哪一个点相连构成三角形，统计出底边属于某个三角形的剖分方案T(n)=ΣC(i)C(j), i+j=n-1；再枚举底边和哪两个点相连构成四边形，统计底边在一个四边形上的剖分数Q(n)=ΣC(i)C(j)C(k), i+j+k=n-2。但是，枚举四边形需要O(n^2)的时间，这样的话整个程序就是O(n^3)的了，n=5000绝对超时。那怎么办呢？两分钟后，我想到了一个具有决定意义的点子：计算Q(n)可以直接利用以前算过的T(i)。枚举四边形的两个顶点时，固定四边形的左边那个顶点，你会惊奇地发现右半部分的所有情况加起来正好就是一个T(i) （上图右）。因此，ΣC(i)T(n-i-1)就是我们所需要的Q(n)。

一个有趣的细节是，这道题要求选手输出结果除以2^64的余数，不知道会不会有人想不到这个该怎么处理；事实上只需要直接用64位无符号类型来运算就可以了，超界了后计算机储存的本来就已经是2^64的余数了。

Hanoi塔那道题也是一个有趣的数学问题。题目大意是说，如果允许Hanoi塔上有相同大小的盘子，最优解又是多少。输入数据给出盘子大小的种数和每种盘子的个数，叫你输出最优解的步数。我的第一想法就是，大小相同的盘子始终要在一起，移动时就排着队啪啪啪地挨个移动，总是保证大家一起行动。其实说穿了就相当于把大小相同的盘子当成一个整体，只是移动的时候有一个权值。这样，只需要考虑经典Hanoi塔中每个盘子需要移动几次就行了。但很快我们发现，这连样例都过不了。为什么就只有两个一样大的盘子时，输出会是3呢？再仔细看了一遍题目，发现麻烦了：一样大的盘子也是可以区别的，目标状态的盘子顺序必须与初始时一模一样。但我们很快发现，加上这个条件后对我们的原始想法影响并不大。在经典Hanoi塔中，第i大的盘子需要移动2^(i-1)次，除了最大的盘子只需要移动一次以外，其它盘子都要移动偶数次。而对大小相同的几个盘子整体转移一次后，盘子的次序正好完全颠倒，因此移动偶数次后次序不变。于是，我们只需要集中考虑最大的那种盘子该怎么处理。队友leimiaos做出了一个大胆的猜想，事实证明他是对的：把最底下那个盘子加大一号（最大的那种盘子就变成第二大的了，并且少了一个），这样就巧妙避开了多个最大号盘子的问题；这样做的结果显然是合法解，并且应该是最优的。

第一题是所有题目中最科学的一道。给你一个有向图，给定它的起点和终点。每一条边都有且只有一段开放时间，其它时间里这条边是不允许通过的。给出每条边的开放起始时间、关闭时间和通过这条边所需要耗费的时间，问你从起点到终点最少需要多少时间。我和leimiaos同时想到，在这道题目中我们要尽可能早地到每一个点，可以用直接套用Dijkstra算法更新到每个点的最早时间。反正你早到了也不亏，如果接下来要走的边还没开放的话我等一下就是了。leimiaos很快写完了这道题，但连样例都过不了。仔细研究了一下样例，我们发现问题严重了：我们要求的不是到终点的最早时间，而是从起点到终点全程所需的最少时间。换句话说，我可以先在起点处等着不走，看着时机成熟后再出发，虽然到终点时间更晚，但路上花的时间更少。怎么办呢？枚举出发时间是一个好办法，但时间的范围很大，肯定会超时；二分出发时间？显然不行，这个问题不具有单调性（考虑从起点直接连到终点的多重边，且所有边的开放时间都不相交）。十分钟后，我一拍大腿说，至少存在一个最优解，使得整个路程在某条边上正好卡着时间进去或者卡着时间出来。如果整个路程中所有边上的实际通过时间都是“松”的，就把整个行程时间安排挪动一下，直到某条边上的通行时间正好碰到开放时段的端点。这样的话，我们只需要枚举整个行程时间卡在哪条边上，然后用刚才的算法顺着推出从这儿走完剩下的路到终点的最早时间，并且反着推出从这儿往回走能够得到的最晚出发时间。这道题太精彩了！！可惜后来时间不够，算法的代码没有完成，算法的正确性和效率也不得而知了。

第二题是一道很难的数学题，很少有人做出来。因此我非常得意:) 说一个n阶的满Steiner树是指一个有2n-2个节点的无根树，其中n个叶子节点从1到n标号，另外n-2个节点（叫做Steiner顶点）连通了那n个点，并且每个Steiner节点的度都为3。你可以在这里(http://acm.pku.edu.cn/JudgeOnline/problem?id=3595)看到n=3时的惟一一个满Steiner树，以及n=4时的所有三个满Steiner树。输入一个n(3≤n≤10^7)，输出n阶的满Steiner树有多少个。要求用8.687E36这样的格式输出。

随便把一个叶子节点砍掉，剩下的就是一棵正宗的二叉树，我们的问题实际上就变成了“有n-1个叶子节点的二叉树有多少个”，其中叶子节点带标号，并且二叉树不分左右。依据这个思路得到的递推公式就是( ΣC(n,i)F(i)F(n-i) )/2，那个C是组合数的意思，F(n)表示n阶满Steiner树的个数。但是n可能达到10^7，绝对不可能直接用我这个递推公式。我开始计算n=3, 4, 5, 6的情况，想看看有什么数学规律没。算出来的数是1, 3, 15, 105。然后牛B的事情就发生了，我眼睛突然一亮，发现它们间的比正好是3, 5, 7，也就是说F(n)=(2n-5)!!！（前两个叹号是双阶乘的意思，末一个感叹号是感叹号）。我立即写下一个程序，按这个公式计算F(30)，发现它果然得出8.687E36，和样例一模一样！

真正戏剧性的事情发生了：暴力计算双阶乘超时了。怎么办？注意到，(2n-1)!!=(2n)!/(2^n*n!)。leimiaos突然想到，在这个精度要求下完全可以用Stirling近似公式。我们可以让n到了一定大时利用Stirling近似公式直接输出结果。n的阶乘约等于根号下(2πn)乘以(n/e)^n，在比赛中我们发现这个公式的精确程度令人瞠目结舌。非常神奇地，π和e居然出现在了阶乘的近似公式中！

发现Problem I是一道水题已经是很晚的事了，最后仍然没来得及把它调试完，太可惜了。前40名队伍中就只有我们没做这道题。Problem G据说也是水题，很多队伍都做了。Problem E也是一道相当科学的题目，我发现了一个nlogn的算法，但没时间写代码了。还有一道题目就是Zen Puzzle Garden游戏求解，一看就是BT的搜索，没一个参赛队伍做了那道题。Zen Puzzle Garden真的是个电脑游戏，就和尚扫地那个，网上都有下载的，还不错。另外两道题分别是一道简单的计算几何和一道简单的图论题。leimiaos顺利完成了那道图论题，计算几何那道题我们都不敢写。所有的题目都可以在这里(http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1291)看到。

最后的结果，我们只AC了10道题中的4道。ACM果然是拼时间的，好多题目我们都会，就是没时间写了。我N多年没写过代码了，昨天绝大多数代码都是leimiaos写的。也好嘛，这次就是抱着玩玩的心态来的，也长了一些经验。明年赛前我可能真的会认真准备一下。还有三年的机会呢，慢慢来吧。

整场比赛的第一名AC了8道题，其中5道都是一次通过。你们猜这个队伍是哪三个人？告诉你，牛大B了，真的牛大B了。三个人分别是唐文斌、郭华阳、王栋。这次比赛是允许外校队伍报名参加的。