oyjpArt ACM/ICPC算法程序设计空间

// I am new in programming, welcome to my blog
I am oyjpart(alpc12, 四城)
posts - 224, comments - 694, trackbacks - 0, articles - 6

南京之役

Posted on 2007-11-28 19:04 oyjpart 阅读(1290) 评论(1)  编辑 收藏 引用 所属分类: ACM/ICPC或其他比赛

南京之役

/*****************************************************/

在南京之前,我心里暗暗在想,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,结束。

/*****************************************************/

下篇:一诀成都 金牌!

Feedback

# re: 南京之役  回复  更多评论   

2009-06-30 03:14 by alpc12
这场比赛留下的记忆好深刻...
永远的记忆..

虽然是失败...

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理