关键字: ACM ICPC 珠海赛 金山杯 2009 BNUEP int_ijk
注：这是高手的心得，高手就是高手。。。 学弟怎么能不MB+YM，收藏之
===================================================================================================
这是有史以来最神奇的一次比赛.
这种神奇的迹象从一大早就开始持续...去科干院要坐车一个半小时, 和去一趟广州差不多的时间. 10点钟开始比赛, 我们学校8支队伍7点半悠闲地坐着大巴过去了. 按照北理工的教练的说法就是, 你们学校也太不重视比赛了, 怎么都不住那边. 不过也的确, 要是这次来得及的话, 那么省赛的时候一大早出发应该也来得及>_<
然后一个神奇的地方是, 比赛一共分了6个机房. 而且机器良莠不齐, 差距及其巨大. (据说把机房分成了三个等级,上等房,中等房和下等房, 每个学校按比例分配...)然后我们队自从用了int_ijk队名之后, 每次比赛都是在角落里. 这次也不例外, 被分配到了最后排的左下角, 纵观全场.
--------按照惯例 下面是流水账----------------
先列举一下题目
Apple Tree: 线性DP. Banana Game: 博弈. Cross Words: 字符串查找.
Download Again: 简单题. Encrypted SMS: 中序遍历. Football Match: 概率.
General Problem: 三次方程求根. Horse in Chinese Chess: 广搜.
Insect World: 模拟. Jack's Lost Lists: 枚举.
开始分头看题, 尚鹏ABC, 我DEF,许翰中GHIJ. 大约20分钟的时候交流了一下, 尚鹏说B是博弈, 之前做过的原题. 我看了DE, 觉得都是简单题, 不过还感觉应该不是最简单的题目,所以没有马上上去写(后来发现整套题目都是这种难度,没有很大的区分度). 过了一会儿我先去写D, 许翰中说不用模拟, 直接用文件总大小除以带宽就好了. 于是很快写完, 一次AC了.
尚鹏说B做过, 然后很神奇的拿出一篇论文, 上面有一个终极公式. 敲上去瞬间过掉了. 我倒比较担心的是怕我们学校的其他几个队伍跟风的话肯能被卡住.
然后是许翰中上去写了A题, 尚鹏帮忙看了一下DP公式. 好像怎么错了一次, 然后就AC掉了.
这个时候大概是1小时多一点. 我换上去写C题. 这个题题意挺奇怪, 我们交流了好几次才确认了题意. 看了一下数据量不大, 也有好几个队过了, 应该不用字典树, 二分查找就行. 敲完代码也一次AC了.
E题其实按照题目所说的方式递归进去, 前序输出就好了. 许翰中上去敲, 我帮忙看代码, 貌似也是一次AC的.
这个时候尚鹏弄完F题, 用最直接求概率的方法就好了, 打了个表, 也一次AC的.
看了一下排名, 发现I题挺多人过, 于是我看了一下, 发现直接模拟就可以. 找最近点线性扫描也不会超时. 于是也很快AC了.
现在还剩三个题, G,H,J. 大约还有两个半小时吧. 时间很充裕. 但是华农那个队已经9题了...我们排在第二, 已经觉得赶不上了, 于是心理上已经做好了最后排在第二的准备...
许翰中看完J题就惊呼--原题!于是拿出黑书,我一看果然..>_< 这个时侯尚鹏上去敲G题, 我在旁边帮忙看J题, 也准备着些H题. 敲完发现有点问题, 于是打印下来. 换许翰中上去写J, 用黑书上的n^3的算法. 提交了, 发现不对... 于是换我上去些H. 但是我又有点担心说这个时候开三个题是不是有点冒险, 然后他俩说没事, 大不了回去写检讨. 我说好, 于是就去敲H. 敲完发现也不对..于是又换尚鹏继续改G. 好像是代码里面某个地方敲错了, 改好了提交AC了.
现在剩两个题, 代码都差不多写好了, 还有一个半小时不到吧. 我和许翰中轮流纠结H和J. 许翰中错了好几次, 后来觉得是不是可能枚举出来的解会不合法, 于是加强了对解得限制, 然后AC了.
还有一小时, 还剩我这个题, 应该很快就能AC. 第一次提交犯了低级错误, 调试的时候把枚举的步数改小了, 提交忘了该回来. 结果得到一个TLE. 这个TLE吓了我一跳, 反复算了复杂度不可能超时啊. 估计是裁判判错了, 害我好几分钟都没敢提交. 改了两个地方之后提交还是WA. 检查了好久才发现, 判断重复的时候,我是判断记录步数的数组值是否为0, 这里导致了BUG, 因为计算的时候有模2008, 求了模之后原来不为0的也可能为0了... 汗.改了这里提交AC了.
这个时候, 还有大约半小时比赛结束, 教练在遥远的某个地方收到一条裁判发来的短信"你们圆满了"...汗.
-----------------------------------------------
第一次比赛的时候做完所有的题目, 感觉题目没有拉出梯度来. 简单的不够简单, 难题也不够难. 而且我们惊呼了好几次--原题...(不过也情有可原, 出题者的时间实在太仓促).到最后的时候时候看排名发现华农那队依然9题..我们等比赛结束的那段时间就一直在算罚时...
最后结果是, 我们学校1个一等奖, 2个二等奖, 3个三等奖. 还有两个08级的队伍缺乏经验可惜没能拿奖.
总的来说这次比赛运气的成分占了很大因数, 遇到好几个原题, 而且这么多次比赛第一次用上了带来的资料. 这次我们队正确率还算可以, 不用写检讨, 不过我最后一个题还是犯了一个低级错误和一个高级错误, 有点过意不去...