Beyond the Void

WC2010 重建计划
WC2010 能量场
WC2010 排序机

这可能是我的最后一份信息学竞赛解题报告。

问题简述

给定一个初始的排列P和M个轮换，每个轮换可以将排列P中的每个数值轮换为排列中的另一个数值，轮换后仍然是一个排列。求出从排列P到排列1,2,3,…,N至少要经过多少次轮换，输出一个方案。

问题分析

本题非常困难，好在是个提交答案题，可以看数据，然后针对每个数据设计合适的算法。不过在看数据之前，首先还是稍作一些转换，以便简化思维复杂度。本题中的“轮换”用了一种很别扭的转换方式（转换数值），与以往的习惯格格不入（轮换位置），因此要把它转化一下。用一个哈希表记录每个数值的位置，形成新的排列Ti就表示原序列中数i在第Ti位，例如样例中的4 3 1 2，转化后就是3 4 1 2，在转化后的序列上变换只用变换位置即可，这样就符合我们的习惯了（至少是我的习惯）。

接下来可以观察数据了。首先发现测试点1、2、3的N、M都很小，可以直接搜索求解。用迭代加深或者广搜即可拿到满分。

观察测试点4，N、M很大，没办法搜索了。但是发现所有轮换都是交换相邻两个元素，而且M=N-1，恰好囊括了N个元素所有相邻两对。这让我联想到冒泡排序的方法，由于冒泡排序每次交换的都是相邻两个元素，因此可以用来解决这个测试点。

测试点5的输入文件是最大的一个，主要是由于M相当大，而且一时没发现什么规律。不过突然发现M=N*(N-1)/2，令我联想到完全图顶点和边数的公式——是不是任意两个都可以交换呢？写程序判重以后发现果然是无重复的M个轮换，这意味着任意两个位置可以交换。因此我们可以从1到N逐个确定每个位置上的值。
Read the rest of this entry »

问题简述

给定一棵边上带权的树，求一个平均价值最大的简单路径。路径的平均价值定义为路径的带权长度与不带权长度的比值。

问题分析

在一棵树上直接找这样的路径是很困难的，因此我们考虑将问题分解。一个基本的想法是在树上分治，为保证对数级别的时间复杂度，必须使用基于点的剖分[1]。每次找到树的重心[2]作为根节点，然后将根节点的子树平均分为两部分，两部分共用根节点。对每一部递归求解，然后把这两部分合并。求树的重心的方法是随便找一个根，求出每个子树的大小，找到max{i.child.size,N-i.size}最小的i，i就是树的重心。重心可能有多个，找一个即可。

对于一个分治的局面，每一部分都是当前根节点的一些子树组成的森林，再加上根节点，所以每一部分仍然是一棵树。最优的路径可能在某一个分治的部分中，也可能跨过根节点在两个部分中。前者可以直接递归下去求解，重点是处理后者的情况。这时需要做的一个重要转化是二分答案，由于答案的范围是已知的，我们可以在答案的范围内二分答案的值A，然后把树上每一条边的权值都减去A。判断有解的方法也就变成了判断是否存在一条带权长度大于等于0的路径，继续转化就是，判断最长的带权路径的带权长度是否大于等于0。
Read the rest of this entry »

问题简述

能量场中有N个粒子，每个粒子都有一个质量m和结合系数c，两个粒子a,b合并时会产生m_am_b(c_a - c_b)的能量。(1)找出两个粒子相结合，使得产生的能量最大。(2)从中找出任意k个粒子排列成一个环，相邻两个粒子分别合并，使得总能量最大，产生负能量的粒子必须是环上连续的一段。

问题分析

乍一看这个问题的第一问好像很简单，枚举每对粒子即可，但是时间复杂度是O(N²)的，而且难以想到如何优化。第二问则更加困难，搜索、动态规划是肯定不行的，贪心、图论也难以找到建模方式。分析发现这个问题可以归约到一个0/1规划问题，如果没有特殊性将无法解决，而特殊性无非在于能量产生的公式，因此将目光聚焦到这个公式上，对公式进行一些变形：

• m_am_b(c_a - c_b)
• = m_am_bc_a - m_am_bc_b
• = m_ac_am_{b –} m_bc_bm_a
• 设x_i=m_ic_i，y_i=m_i则原式
• = x_a*y_b – x_b*y_a

Read the rest of this entry »

今年有幸能再次参加CTSC和APIO的比赛。CTSC(Chinese Team Selection Contest 中国国家队选拔赛)在北京大学举行，APIO(Asia-Pacific Informatics Olympiad)在天津大学举行。CTSC号称世界上最难的OI比赛，不无道理，因为要从国家集训队的20位精英中选出4位，其难度可想而知。APIO是一个新兴的国际区域性比赛，始办于2007年，今年是第三年。APIO赛题难度不及NOI，接近于IOI。

出乎意料的CTSC

5月4日早晨，马浩、我、赵陈晨和王国正老师乘坐动车D134次前往北京，中午抵达北京西站。乘坐公共汽车到了北大附近一个的招待所，住宿条件好得出乎我的意料，按照杜子德的说法是“准四星”的水平。下午去机房使用比赛环境，出乎意料的是，比赛环境是Windows，有VC6.0,VS2003,VS2005,VS2008等强大的IDE，而提交方式是poj。这是我参加过的任何一次比赛都没有遇到过的情况。

CTSC的两试中，poj还挂了一次，导致第二试延长了很长时间。做CTSC的题纯属被虐，所有的题我都是朴素搞定的，于是拿到了铜牌。不过收获还是很不小的，尤其是了解了A*算法，模拟退火等有用的方法。

更大的收获是认识了张昆玮和王谟大牛。和张昆玮大牛讨论问题，真是听君一席话，胜读十年书。张昆玮大牛有些话令我十分震撼，例如“网络流问题建模不是很难，关键难在算法的实现上”，“我不会写二叉堆”，“平衡树的问题我绝大多是都是用线段树搞出来的”，“线段树怎么能写成递归呢？”，“求强连通分量的算法5行”，“计算几何本不难，只要别拿精度来开涮”……这是我与大牛的第一次近距离接触，这才叫真正的大牛。

我、马浩、赵陈晨这几天把北大内部及周边转遍了，5月6日晚上我、张昆玮、赵陈晨、马浩租了四辆自行车，骑车去了鸟巢，路途来回有近20公里。在路上，我多次想要半途而返，但是在赵陈晨和张昆玮的说服下，我们坚持骑车到了鸟巢广场。一年前也曾来过这里，那时还是铁网围墙，现在已经成了一个旅游胜地。水立方在夜晚的灯光下，显得十分优美别致，令人有一种如临仙境的感觉。近距离地望着鸟巢的巨型钢架，我觉得自己十分渺小。鸟巢旁边还有一条河，在夜晚的灯光下，河水泛出梦幻般的光芒。就在我陶醉在这种美景中时，我突然不禁要问，到底为什么要修建这样华丽的鸟巢？国家修建这样庞大的工程，耗费了无数金钱和资源，这都是纳税人的血汗，是谁允许把这些钱花在修建一个巨大的体育场上？

APIO与北洋大学

5月8日早晨，我、马浩以及王老师乘坐火车前往天津。抵达天津站后，我们就受到了热烈的欢迎，有天津大学志愿者来接站。和志愿者聊天，我了解到了天津大学的历史。天津大学的前身北洋大学是中国近代第一所大学，创立于1895年。这是一所不折不扣的工科大学，至今其化工系都排在全国第一名。然而令我失望的是，进入天津大学却没有感受到想象中的那种深厚的文化积淀。令我印象深刻的是，北洋大学内有4个不小的湖，这在北方是罕见的。

下午去试机，令我不满的是，居然机房要按省进入。河南省就只有我和马浩两个人，于是就排在了将近最后。至今我都不知道他们为什么这么搞。次日上午参加APIO2009的比赛，比赛还分了正式选手与非正式选手，大概是NOIP2008中拿到了330分或更高的，就是正式选手。正式选手有一个帐号，可以在http://apio2009.iarcs.org.in/上面提交。

拿到试题，我的第一感觉就是：不难，但在仔细一看，又觉得也不简单。首先我就看中了抢掠计划这道题，明显的收缩强连通分量，然后动态规划就行了。但是500000个点的DFS递归极有可能栈溢出，我就先写了递归，心想如果有时间再改。接下来我看到第二题，一开始就想了一个错误的O(N^2)动态规划，然后就开始想办法优化了。花了好长时间在这个题上，我终于想出了O(NlogN)的方法，还欢欣鼓舞地写了出来，直到讲题之前我都不知道自己的算法本身就是错的。最后时间不多了，开始做第一题。不论如何，先要拿住30%的分数，于是就写了暴力枚举。最后只剩不到一个小时了，此时我已经晕了，根本想不出正确解法了，于是就写了随机爬山法，只可惜没有拿住分。

第二天去看成绩，我发现第一题30分，第二题0分，第三题居然93分！一定是栈溢出了，手动测评后果然不出所料。令我诧异的是，马浩同样的DFS，他就能拿到100分？！而且手测同样是要溢出的，但机器测出来是满分！我的123分，排名66，应该是铜牌了。但最后一天颁奖出乎我所料，我是银牌最后一名！原来我的程序报到官方后，第三题成了100分。

某日晚上吃过晚饭，我和马浩走出北洋大学的南校门，进入了南开大学。这两所大学距离之近，可谓一墙之隔。南开大学给了我另一种感觉，它比北洋大学更精致，更优美。漫步在南开大学之中，犹如置身一片园林，而行走在北洋大学只能，好似穿越一个平原。南开大学偏重于文科，而北洋大学精研理工，也许这就是区别吧。实际上，我更喜欢南开大学的校园。

一些感想

这次CTSC和APIO归来，我更多的是认识到了差距。我想，许多知识我都还没有掌握，需要努力的地方还很多。例如平衡树的灵活运用，动态规划的优化，贪心算法的设计和证明，随机算法、模拟退火、A*及IDA*，树链划分，子矩阵问题等等等等，都是我需要掌握的。关于计算几何和博弈论，我只想浅尝辄止，毕竟时间不允许了。今日看到距离NOI2009也只有不到80天了，我一定会在这些日子里内羽化而登仙，涅磐而重生。