从 GDKOI 2009 回来了

记得一年前的此时此刻，我写了一篇文章叫做从GDKOI回来了，现在还是评论最多的文章。看来大家对Lys的兴趣（抑或是我的笔触）是十分强烈啊。

===============我是分割线===============

其实，一直很羡慕珠三角的OIer。KOI，都是周六早晚周日回的。而我们呢，坐车时间2天，比赛时间2天。

过去广州坐长途客车，因为鲘门服务站开了间M记，汽车公司拿不了回扣，结果就把我们拉到了一个叫汝湖的垃圾服务站。哪里的所谓牛肉丸粿条15元而且难吃得要命。苍蝇漫天飞舞，十分恶心。

回来本来想要搞个火车硬卧好好休息，结果亲爱的潮阳实验的指导老师给我们买了硬座票。卧槽，刚开始我就说要换成卧铺。结果由于其他同学和姚老的惰性，最终也没有换成……刚开始还好受，等到龙川，就是广梅汕铁路与京九线交界的地方，一大堆破破烂烂外省仔穿得邋邋遢遢挑着一大堆乱七八糟的东西涌上来，拿着站票就硬抢我们的座位不让我们坐，最后我没座位只能坐在椅背上度过好几个小时。椅背上空气至少比下面好一点，在下面是完全没有办法呼吸的。

以后比赛一定自己买机票过去。不过姚老师告诉我一个极其恶心的消息，就是GDOI在韶关举行……韶关什么地方嘛，用Google Earth如果没有开任何图层，根本就跟江西湖南连成一片的嘛……虽然风景是很漂亮，可是那个什么交通条件就真的是太那个了，连飞机场都没有！

===============我是分割线===============

我逼火说，等有一天让他们都来汕头考试。可是据说这种烧钱的事汕头政府系不会做滴。政府没钱了官员贪污什么捏？姚老师说不要补成卧铺是没办法报销，报销要向汕头财政局，而他们总是千方百计拒绝。

也许拒绝也是正常的：别人是“再苦不能苦孩子，再穷不能穷教育”；汕头政府是“教育也是生产力”。而且在实践中认真贯彻落实：金中收了那么多择校生那么多择校费，结果都被当成是汕头的财政收入暸。

结果竟然连我们教室电教平台的幻灯机坏了四五年还没能够更换，洁癖勇逼迫我去当电教员，众教师众同学总是对我说：“找你姨”（“你姨”在潮汕话的意义可类比普通话的“他妈”），结果我申请了n!次还没通过。

为了避免被继续叫“你姨”，我只能自己捐钱买了个幻灯。结果某天学校开会，向全体教职员工表扬洁癖勇勒索学生的行为……

汕头经济落后，绝对不是那些“具有正义感的”语文老师所认为的所谓“没诚信”的问题——这种问题在开始发展的任何地区都存在。在这个自上而下没有自由的国度里，绝对是政府的问题（我指的绝对不只是市政府，毕竟市政府权力有限）。

我也不会像姚老师那样只是抱怨……绝对不会……

===============我是分割线===============

题目本身不是很难，主要还是DP和搜索。

这次成绩还好，第四。第一不认识……第二是蛤蟆阳，第三是初三的小鱼儿。第二第三第四的分数成公差为-1的等差数列，这个差距还是比较猥琐的吧。幸好这个是练习赛不是GDSOI。如果SOI我1分没进省队那就……算了，不要想太多，等一下真的成为现实那就惨了。

之前一段很长的时间被郭晓旭翁斯帆那群高一拉去研究数据结构。不过毕竟省赛高级的数据结构至多至多一试一题，根本不需要那么多时间学习。所以KOI前回归最原始的DP和搜索还是正确的。最近在USACO做new problems那些DP题，顺便加强一下搜索，看来还是正确的。特别是搜索，不会做的题目还可以骗一点分数。

===============我是分割线===============

第一试，我坐在一排的最左边，我右边是石门中学的邓尚文，右边的右边是5班林衍凯神牛。

我一过去就把我右边的电脑踢翻了（绝对不是体积问题），结果第二试结束发现邓牛还没发现他的电脑是倒着的……

邓牛是用C++的，由于最近我也没事玩玩C++，所以就请教一下。当我说到C++编译出来的程序要比Pascal要快，不是很公平的时候，邓牛说：“P本来就是应该淘汰的”。

结果呢，当时试机的时候邓牛打了一个qsort调了n久。我清晰的看到他的程序有着如下片段（节选关键部分）：

for (;;)
{
i++;
if (a[i]>=sign) break;
}

本人极其厚道，用C++写了个qsort给他，结果导致被GSS教授点名批评。上面语句对应语句如下（并不严格等价）：

while (a[i]<sign) i++;

第一试的题目比较简单，结果第一题邓原牛和龟牛都写了子序列……这种明显太大牛的人我们实在比不上。我写了个最基础的DP。结果在n=1时wa了，我输出0。其实对这个错误我持保留态度：去年KOI第一试第一题评委们说，1个就不能算连续，于是我wa了一个点；今年评委们又说，连续的绿豆饼包括1个绿豆饼，于是我又去分了。

第二题1小时写了ac程序，结果突然脑残又花半小时写了个新版程序，才发现原来的程序没有错。这道题我用O(nlogn)的算法，但确实有 O(n) 算法，但是评委说的三等分点法是错误的。这道题数据比较小，不一定用O(n)，所以奇妙的解法还是比较多的，比如随机调整……

第三题裸的网络流，由于我菜，不会写匈牙利，所以只能写一个sap……

第四题，由于第二题浪费太多时间，只剩下1小时，于是我写了45分钟，边写边念法克鱿，发现才做了1/3，于是便写了个cheat程序。如果n=1就特殊判断，n>1就输出“出这道题的人心理变态”。结果竟然一个n=1的数据都没有，只得0分。郭晓旭一直怂恿我复评，让评委们看看我的程序的输出。

===============我是分割线===============

第二试，四道都会做，也都可以做到满分，但结果还是有一些遗憾的地方：方展鹏姜碧野他们都是144，看来并不是不可能做到接近满分。

第一题水过，结果还是有牛挂……

第二题比较遗憾，明明想到可能爆栈，把1h写好的递归的DP用了0.5改成非递归。结果忘记把建树过程也改成非递归，挂了2个点。

第三题更加遗憾，分析复杂度的时候忘记前面还乘多1个m，结果把哈希表开大了，复评的时候发现，如果把bigprime常数从1991改成91就可以多得12分。估计哈希表直接fillchar而不要回收内存的话就可以不tle了（我对不回收回收内存极其恐惧，因为我曾因为没有回收内存拖垮过学校电脑）。

当时由于第二题改非递归花多了半个小时（结果8分还是拿不回来），所以只剩最后1.5小时写第三题，结果又看错m的范围又多花0.5小时。最后只剩1个小时做第三题。关于全部模3的贪心被我的反例推翻，可是我也有想到111 222 333等价于123 123 123（这个是我平时打麻将的时候想到的）。可是由于时间紧迫，我认真贯彻落实皮炎平的做题哲学“当你想到优秀的解法的同时，别人早就用简单的解法把题目解决出来了”。当时我只想到暴力的从左到右DP+状态压缩hash，于是我就这么做了。

其实可以证明（当时只是感觉一下），状态数不会指数级增长，总的状态数会限制在一个范围内。其实就是那个贪心的缘故，也就是方展鹏神牛的方法。所以我的方法按照刘祖立评委的分类也算是O(m^2)的。但是实际上那个所谓常数似乎是跟m有关-_-|||，运行起来还是差不多。理论的东西是骗人的……实际运行时间才是硬道理。

第四题有人说，合并同样长度的棍子只能让评委的程序通过。但好像最坏情况总是有同样长度的棍子，没有同样长度的棍子达不到最坏情况。而且还可以加hash优化，所以挂掉那个点还是输得心服口服的。

顺便说一句，郑戈迪抓题还是比较准的，我发现他最近在做ZeroJudge的一堆线段，结果他就竟然真的出了。

===============我是分割线===============

如果说，GDOI2008对我来说，是知耻而后勇。

当然，GDKOI，只是练习赛，剩下4个月，我会不顾一切的努力的！省队，才是目标_1.

我昨晚吃饭时候开玩笑说，这是我最后一次在西苑吃了，如果有下一次，不是进国家集训队而过来GDKOI2010玩，就是高考考挂来中大读书了……

希望我会是前者。

===============我是分割线===============

贴图：

在Day 2晚上，珠江畔，顺便赞一下Sony Ericsson 的全景照相功能。

回汕头的火车上。

整理相片是发现的上学期某个同学在渡船上拍的相片。