南京之役
/*****************************************************/
在南京之前,我心里暗暗在想,Regional到底是什么样子呢
我也在想,ARTor的征战又会是怎样的故事呢
随着战役钟声的敲响,我带着初生的喜悦,踏上了南京的行程
/*****************************************************/
由于长沙没有直达南京的车,我们决定从上海转车
第一次来到上海 感觉非常气派 果然东方明珠高高地矗立在此地
然后辗转到南京的时候 却有点为印象中的古城失望
也许这就是城市与文化的不和谐了
/*****************************************************/
曾为篮球队长的alpc01,转身成为我们ARTor队的队长
稍黑的皮肤,明亮的眼睛,穿透着一股王者的霸气
1米9高的alpc55,却从来不会打篮球,运气中成了韩剧小超人
55是我们的秘密武器 因为他是MAN中难得的心细与沉着 等着机会就出手
剩下那个傻孩子就是我了 其实还是挺好的~
/*****************************************************/
热身赛开始的时候,我们都在笑
因为我们在想 进场的时候干脆拿上棒棒糖吧!吉祥~
55很顺利地上去干掉了B 被我一看是概率的题就扔了他的题
接着01给我说了A题的提议 立刻警觉是经典的最小割 用最大流上去搞掉了
然后01和55在闲聊C题中 想到了C题的算法 我上去照敲模板过掉了
热身赛排名第8,我们都楞了,因为我们没有配合,也没有认真答题
每当一个人敲完的时候,3个人一起喊“交!交!交!”
“测试数据呢?”我问道。
“交!交!交!”
“没有测试数据?......-_-|||”
就这样很不认真的度过了热身赛
/*****************************************************/
晚上的时候我意识到其实我们今天的表现实在差劲
当然热身赛本身也没大重视
所以晚上我们组开了一个小会议,开始做自我批评
早早的睡下,为明天的正式赛做准备
/*****************************************************/
第二天,正式比赛敲响。
我安静的坐着,那一刻,我觉得自己非常有斗志。
我微笑地看了看队友,他们都很有精神,很有力量。
好。分题。我ABC,alpc55 DEF, alpc01 其他。
我看了看A题,觉得可能是动态规划,想了想状态,比较大。跳过。
B题看了没想法,跳过,看C。这时候RANK上面J题已经有队过了。
于是01给我讲J,发现是一个经典的记忆化搜索。规划了一下就上去敲了。
敲完了一直过不了样例,试着调试输出也出现了很奇怪的值。
然后发现原来a = b == 1; 这样的语句在当时的编译器下居然会出错。
加上括号之后,过了数据,提交AC.
我下来之后01和55在讨论C题,初步讨论结果是用修改的并查集。然后55上去
敲了。
在几次提交的WA中,55有几次比较大的改动,到后来觉得没什么可以修改了
的时候,我们放弃了C.
因为那个时候还没有人过C(甚至一直到比赛结束也没有队过,不知为何)。
在这个过程中,我看着F题是一个比较典型的DP。估算了一下复杂度有些高,
但是看到在场有很多队伍过了,而且自己也想不出优化的方法,于是决定用
DP水一下。写完之后提交TLE了。于是我换了A题来想。
另外一个要提的就是01在这个时候看到I题是一道陈题,在我带的蓝书(国际
大学生程序设计竞赛例题解1)中有,翻开题目一看一模一样!01立刻仔细看
那题的标程。不过后来觉得是o(n^2)的,可能超时。
这个时候我在考虑A题的动态规划算法,经过几次改进和优化,到了一个可以
接受的量级。
比赛时间在我们C,F的磨蹭中已经过了3个小时。我们还是可怜的1题。这个
时候55看了看很多人过的F题,觉得可能是Trie。对,就是Trie。可惜我根本
不懂Trie(唉)。他也没怎么写过Trie,于是55在场上临时学了Trie,开始试
验性的在场上写出来。经过一次RE之后,在4个小时的时候把这个题目过掉了
!
在这个时候,我的斗志才刚刚恢复起来,可惜已经晚了。我的A题已经考虑的
比较成熟了,在没有题目上的情况下我上去敲了A。01察看G题许久无果(同
样的,我们组也没有人会后缀数组)。
这个时候01发现一个很奇怪的现象。在我们后面的一支队伍,过了J题之后,
拿出那本蓝书,就这样把I题过了。当时01很警觉的要求上I题。于是在我A题
很郁闷的WA之后上了I题。01不会PASCAL,55上去敲标程。敲着我们觉得速度
慢了,就交给01敲,55翻译。到了还剩6分钟的时候终于敲完,那个时候我们
组多么希望奇迹出现阿!可惜出现很多编译错误,直到比赛结束才改完。
比赛就这样无情的结束了。我们就这样水掉了。没有一点办法的水掉了。
/*****************************************************/
比赛结束之后,我们得知Glory.h队答了4题(最终ICPC 4th),心里又惊喜
又自叹。也许我从来就没想到自己在Regional上面会经历这样的失利。甚至
有种被捉弄的感觉。
记得在比赛之前的一个星期,我们组拿出《算法艺术与信息学竞赛》,前后
核对了一下,发现我们组主要的漏洞是组合数学(ploya, Burnside)和
Trie+后缀数组。在我的印象中,后缀数组是属于比较偏的东西。当时我问01
,“后缀数组可能考么?”,01回答说:“可能性比较小,至少我从来没有
看过。”当时本来打算两个都学的,但是我在国家集训队论文里面找了一个
Trie图的论文,看了很复杂,就没看了。后来我把组合数学好好看了下。
然而残酷的比赛就是这样,在最简单的3道题里面有两道都是我的知识漏洞,
而本来可以水掉的I题我们没有认清场上的形势。就这样非常无奈的眼睁睁的
看着ARTor失利。也许一切都是注定,谁叫我们组没有人会Trie,没有人会后缀数组。
擅长模拟题的55也因为没有模拟题而没有发挥出来。
我的A和55的C没有过掉是个遗憾。其实当时场上的形势不该做A,C。可是我们没别的题目可碰。
也许这就是RP。面对这套题,我们没有办法。铜牌/icpc29,结束。
/*****************************************************/
下篇:一诀成都 金牌!