早晨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的余数了。

查看更多 »

    昨天本来写了很大一段文字的。经过再三的考虑，我还是决定删掉了和古汉MM及其现任男友相关的一些很纠结的文字。到底我写了些啥，大家自己YY去。
    长话短说，昨天上午发生牛B事儿了。有人发个短信来，问我参不参加ACM选拔赛。我以为是什么牛B人搞到我手机号码了呢，结果古汉MM来一短信，说他男友要了我的手机号来找我组队来了。本来一直在说，大学只在道上混，不搞ACM的；但当ACM真正来到我身边时，我开始犹豫了。有趣的是，若不是古汉MM她男友发短信来找我，我还真不知道有ACM选拔赛这回事。我在BBS上寻找今年ACM选拔赛的消息，开始盘算我还需要复习多少东西。找到了一份去年的题目，看见最后一道题名字叫“选课”，心想估计是那个著名的多叉转二叉。看来这个选拔赛的难度还是比较适中的。我在想，信科的竞赛班现在应该还不会涉及多叉转二叉的树形DP吧，那个信科的看到了肯定立马就愣了。我开始考虑是否需要另外找人组队，不要那个信科的了。然后我毫无防备地点开链接，“叭”的一声晕倒在地上：

Description
教务网站如期的在选课之日出问题了，这次的问题是登陆窗口的验证码无法显示了，同学们只能靠猜验证码来登陆选课。教务的登陆系统刚刚经过改进，改进后的验证码均为1..N的一个排列。一般的同学们在试验的时候都是按照所有排列的字典序逐个试验，但是TN发掘这样试验很乏味，所以他决定每次尝试前一个排列后面的第M个排列。
但是一段时间之后他发现，寻找一个排列后面的第M个排列并不是一件容易的事情，所以他希望你帮助他。
Input
Line 1： N (1 <= N <= 10000)
Line 2： M (1 <= M <= 100)
Line 3： 1..N的一个排列
Output
所求的排列

    看来，和传说中的一样，PKU的ACM果然抓得没有那么紧。我又开始犹豫，到底要不要去参加这个选拔赛，又要不要跟古汉MM的男友一起合作。如果有谁心烦了想虐题的，我负责去找些信科的作业来。
    大家上得了这个网页不？点那个“竞赛题目”进入愉快的虐题之旅吧。07年的那个页面貌似有几个死链。06年的题目很全，我在这里发一下。长期被题目虐？准备开始虐一下传说中PKU的ACM选拔赛吧。顺便给某个跟我说想学Computer Science的MM看看，信息学会涉及一些什么样的问题。
查看更多 »