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-12-11 00:26 oyjpart 阅读(2854) 评论(14)  编辑 收藏 引用 所属分类: ACM/ICPC或其他比赛

一诀成都,金牌!

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

终于有时间来描画下这场比赛了。

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

南京回来之后,我一直在思考到底为什么会失误。

想了很久,觉得是算法面,模板的问题。

回集训队之后,我开始扫PKU的后缀数组,Trie题泄愤。

发现其实也挺容易的,并不是什么很难的算法。

和alpc62,alpc16在一起训练的几场,算然感觉没有尽力,但是成绩还可以。

所以我们非常有信心的来到了成都赛场

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

alpc62属于数学型强人,做的题也很多很杂,但是却和我有着惊人的互补.

这一点我早就发现了,我们两个合在一起战斗力是很强的.

可惜之前一直没有合作的机会.

alpc16是JaWs的队长,是高我们一届的老队员了.

在长春赛区已经拿银凯旋.这一次再次荣登队长之位,共赴成都一战.

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

热身赛比较搞笑,因为我们3个人都一致迷信的认为,

热身赛一定不要成绩好!不要浪费RP了!

所以等我们切了2个之后,本来不准备再做了.

后来发现第三个挺多人过了,我就上去随便切切.

等我交题的时候,我们3个一起大喊,"不要AC!不要AC!"

呵呵,结果,真的没AC.哈哈...

后来就没管了,测JAVA,玩solaris自带的游戏...等等..

期间发生一次极具RP的事情,就是ALPC16摔了狠狠一跤,当时:

全场顿时一片寂静.

3秒后,

还是寂静.

再3秒后,开始全场哄堂大笑...

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

正式比赛开始!

62ABC,16DEFG,我HIJ

我在读H,有点迷惑题目的意思,正在确认.发现有队过了J

我马上开始看J 看完之后就上

结果敲完了之后样例都没过,重新理解了下题目,改了1Y.

我下来之后开始观察场上形式发现D,H有人过了.

我再次确认了以下H题,推了下公式.62正在敲D.

62敲了没过.换我上H.敲到一半,他发现错了,改了还是WA.

我接着写,写完之后,根据SAMPLE改正了对题目的错误理解,然后1Y掉.

没过多久62也把D题错误找出来过掉了.

这个时候时间过去了2个小时.我们做的比较慢了.

观察场上形式后,他们给我讲B题题意,是图论.我开始想.

他们读A题.

我发现B是一个枚举+割的题目.但是要注意一些重边,不连通等特殊情况.

于是我和62确认了一下算法,开始上去敲.

敲完之后顺利的过掉SAMPLE和16的测试数据,很有信心的提交,WA.

然后就是62上去写A,我不清楚用的什么方法,但是得到了他们猜想可能的TLE.

我觉得可能是自环的问题,上去改掉还是WA.

过了一会发现自己重边的那个没判全,很高兴的上去改掉,居然还是WA.

期间62上去改了2次A,也还是TLE.

此时时间过去3个半小时.我们组陷入僵局.

我看了很多遍我的代码,都没发现问题.这个时候我发怒了

我冲上去就抓了2个极端数据来测.

结果居然测出了错误.3个点的时候有个判断错误.而且只有这个case会错.

我加了个特判之后立刻交上去,AC啦!

下来立刻看A题,准备全组奋力攻A.

正在我看完A题的时候,62突然很坚定得说了一句:

"这题我马上就可以过了!"

我们还没回过神来,不知道他给代码加了点什么,居然AC了!太赞了!

5AC,此时已经封版!

好,我们冷静下来.还有大概45分钟的时间.我来搞C,62考虑G.

我看到C是一个和Apple Tree很像的题目,只是边有了权值而已.

我写了一个状态转移方程,但是发现有些问题.

其实就是一个点的状态应该由他的子节点的一个排列的DP来决定.

而实际上这个排列可以简化成枚举最后一个不回到该点的子节点

这个DP复杂比较难估计,但是极端情况下会达到O(n^4)

时间已经不多!我决定用升序作为序来水一下这个题目,这是最普通的情况。

马上上去把代码敲掉。过测试数据,然后又过了N个16的数据。

我在祈祷。

祈祷自己过掉。

一次一次提交,始终WA。

唉。没办法。过不掉。比赛结束。

结束之后我非常郁闷。没想到金牌就这样错失。

我垂头丧气的走出了场外。

等我再回去的时候,他们对我大喊“金牌了,金牌了!”

我一愣,回去一看BOARD,原来最后一个小时大家过题不多。

我们顺利排在了第九!(罚时很大。。)

金牌了!

这一刻,这一年来的风风雨雨都有了见证了。

我和队友紧紧拥抱着。。。

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

赞alpc62,alpc16,我们的精彩配合是在难忘

感谢alpc01,daringQQ,你们带我走入ACM的殿堂

感谢YR, 你的鼓励让我有勇气摒弃南京的失落再次征战

感谢父母,背后默默的支持,你们太过伟大

感谢集训队的每一位队员给予的巨大帮助,我们是一个集体
他们是:ALPC01,02,04,05,07,10,16,25,33,37,44,50,55,62,milan

感谢窦窦,alpc55,我们开开心心的走过的备战旅程

感谢ASP, 感谢coral, 感谢夏榕泽,感谢yiyi,感谢所有关心我支持我的朋友们

感谢8600在我最菜的时候回答我的弱智问题

感谢byron,感谢butterfly, 感谢owen,感谢cxm

感谢所有的ACMERS与我一起奋斗!

Feedback

# re: 一诀成都,金牌!  回复  更多评论   

2007-12-11 07:40 by 深蓝色的音符
感觉你们很牛

# re: 一诀成都,金牌!  回复  更多评论   

2007-12-11 08:40 by winsty
赞!
哪个学校的俄?
以后多交流:)
可以去偶的网站上看看~
http://acm.zjuwinsty.cn

# re: 一诀成都,金牌!  回复  更多评论   

2007-12-11 11:51 by oyjpart
恩 好的

# re: 一诀成都,金牌!  回复  更多评论   

2007-12-12 10:40 by 绿茶加冰
这是什么比赛啊?

# re: 一诀成都,金牌!  回复  更多评论   

2007-12-12 12:39 by oyjpart
ACM-ICPC比赛介绍

ACM国际大学生程序设计竞赛(ACM International Collegiate Programming Contest – ACM-ICPC)由国际计算机学界著名的ACM学会(Association for Computer Machinery)主办,是世界上规模最大、水平最高的国际大学生程序竞赛。每年举办一次。ACM成立于计算机诞生次年,是目前计算机学界中历史最悠久、最具权威性的组织。

# re: 一诀成都,金牌!  回复  更多评论   

2007-12-12 13:38 by alpc62
难忘,难忘

# re: 一诀成都,金牌!  回复  更多评论   

2007-12-15 10:50 by 小神
终于还是赢了。。。太不容易了。。。

# re: 一诀成都,金牌!  回复  更多评论   

2007-12-17 18:21 by alpc12
呵呵 成都吃的还是挺爽的,印象很深

# re: 一诀成都,金牌!  回复  更多评论   

2008-02-14 11:56 by owen
喀嚓喀嚓 :)

# re: 一诀成都,金牌!  回复  更多评论   

2008-03-18 20:55 by l-y-p
顶,向牛人学习!

# re: 一诀成都,金牌!  回复  更多评论   

2008-05-14 01:39 by ecnu_zp
你们金牌的时候,我只会 hello world~~

# re: 一诀成都,金牌!  回复  更多评论   

2008-05-14 09:43 by oyjpart
那你很有发展前途的说~~

# re: 一诀成都,金牌!  回复  更多评论   

2008-11-30 14:36 by 长沙
再诀成都,XX!呵呵
听说你们A了5题,祝贺

# re: 一诀成都,金牌!  回复  更多评论   

2008-11-30 23:19 by 真圣灵骑士
饿。。。请问大牛是WHO,能有QQ交流么。。。谢谢。。
我一个BUAA的菜鸟……很菜的那种……

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理