今年有幸能再次参加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天了，我一定会在这些日子里内羽化而登仙，涅磐而重生。
上次修改时间 2017-02-03