记09年北大ACM校内赛

    大学生活混起来很快，不知不觉又是一年过去了。去年5月10日的ACM校内赛给我留下了许多美好的回忆，因此今年我主动去报了名（上次是被人给拖去的）。今年有点装怪，题目数量不变，但时间缩短为4个小时。原计划是从8:00做到12:00，结果可能是因为我们所在的7号机房迟迟没有开门，时间临时改成了8:15到12:15。总的来说，今年的题目比去年要糟糕得多，但也不乏一些精彩的题目。

    和去年一样，第一题依旧是所有题目中最科学的一道。题目给定一个不超过2000*2000的网格，你在最左下角的位置（即(0,0)点），你的目的地在(x,y)。要求你的路线不得经过同一个交叉点两次，且不允许左转（题目背景让这个条件顺理成章：街道靠右行，左转不方便），问合法的路线共有多少种。题目难点就是你不一定要走最近的路，完全允许你绕上一大圈；这破坏了有序性，很难构造出递推公式或动态规划模型。稍微画一下图，我们发现了一些显然但很有启发性的规律：每一次右转后，你左手边方向的所有区域都不能再走了，这很可能产生出规模更小的子问题来。另外，所有合法路线必然是有如螺旋线一样的一圈一圈绕着终点走，这种隐藏的有序性也为动态规划提供了可能。但顺着这个思路想下去屡屡碰壁，我猜不少队伍都卡在这儿了吧。

 

    后来我完全打翻前面的全部思路，猛然想到了一个具有决定意义的想法：街道的选取唯一地决定了整个路线。例如，假设我想计算转弯恰好11次的路线有多少条。这样的路线一定含有三条向上走的路、三条向右走的路、三条向下走的路和三条向左走的路。除去第一条路和最后一条路的位置都是确定的，其它的路选在哪一行或者哪一列唯一地决定了整个路线。因此，我们可以用排列组合直接计算出答案来。向上走的路是五选二，向右走的路是七选三，向下走的路是四选三，向左走的路是三选二。把它们各自的选取方案数乘起来就得到了拐弯11次的合法路径。于是，计算所有的路线数只需要从小到大枚举拐弯的次数，每一次计算都是常数的，总复杂度是O(n)的；整个算法的瓶颈反倒是O(n^2)的组合数预处理，不过这个复杂度完全可以承受。


    另一道题也很不错。有n只猫猫排成一排，初始时每只猫猫都没有花生。定义三种操作：给第i只猫猫一颗花生，令第i只猫猫吃掉它所有的花生，交换猫猫i和猫猫j的花生。给出长度不超过k的操作序列，输出循环执行m次操作序列后的结果。数据规模n≤100，k≤100，m≤1 000 000 000。看到这道题我们立马会想到矩阵乘法。如果能为每种操作构造出一个矩阵，m再大二分下来也能承受。我们可以先把序列中的k个操作乘起来，再利用二分自乘m次就可以了。

 

    但这一思路碰到了一些困难：交换和清零操作都好办，但加一操作怎么弄？我们可以借用这里的第一题的思路，在猫猫向量的最后面加一个额外的“1”，从而解决了加一操作的难题。

 

    这道题最后TLE了，而我们没有充足的时间去优化它，最终残念离去。算法的瓶颈就是把k个操作乘起来的过程，它的复杂度是O(k·n^3)，也就是100的四次方，最坏情况下铁定会超时。不知道用O(n^2.81)的矩阵乘法是否可以AC。网上还有人提到，由于矩阵很稀疏，做乘法时写成if(a[i][k]&&b[k][j])c[i][j]+=a[i][k]*b[k][j]会大幅度提高效率。下来跟外校参赛选手512MM交流了一下，她告诉我一个操作序列的最终结果可以用O(k·n)的复杂度直接构造出来，这样就可以保证AC。另外，同队的leimiaos还提出了一个完全不同的算法：把交换操作看作置换群，然后把单个操作序列的交换操作分解成若干个循环。每个循环都将在100次序列重复以内产生周期性状态，而不同循环之间又互不干扰，问题即迎刃而解。

    今年的题目确实没有去年的精彩。D题和G题都是很纯粹的数学题。D题是说有n个木块排成一行(n≤10^9)，你可以给每个木块涂红蓝绿黄中的一种颜色，要求最后红木块和绿木块都有偶数个，问染色方案共多少种。leimiaos用满满一页草稿纸推出来公式4^(n-1) + 2^(n-1)，大家也可以试试看。G题更干脆，题目描述压缩了就一句话，给定圆锥的表面积，求最大体积。作为根正苗红的理科生，同队的徐谷子MM和leimiaos都赶在我想出圆锥表面积怎样算并准备操键盘写二分之前飞快地算出了公式解。这两道题分别有108支队和160支队做出来，而走路题和猫猫题的AC数分别只有9和11。
    其余的题目绝大多数都是比较复杂的模拟，几乎没人去做。这次比赛第一名AC了6道题，第二、三、四名AC了4道题，接下来有十几支队伍AC了3道题，然后就是不计其数的只搞出两道数学题的队伍。不管怎样，这次比赛再一次勾起了我做算法题的欲望。最近打算没事时稍微练练手，到时候大家在百度之星和有道难题上见！

58 条评论

发表评论

32  +    =  41