2009宁波全国邀请赛总结

1个评论27次阅读2009.05.03 21:47; 作者:Felicia 

这次去宁波的目的是带新人,然后去上海happy。所以我没有什么心理压力。
4月24号晚上18个人出发了,一路杀人游戏。郁闷的是我经常被首杀和首票。
25号早上抵达宁波,很不幸,我和韩帅一起住在2楼,没有无线网。带来的路由器放在金毅那里,功率虽然调到了最大,但信号穿一层楼板之后非常弱,只能在走廊里收到。于是打消了上网的念头。

25号下午是练习赛,4个题目都不难。操作系统是Open Solaris,让我想起了被买的Sun。试了一下,没有gVim,于是用NetBeans。A题金毅写了个用cin的,超时。但是题目的数据应该是非常小的,应该不可能超时才对。后来想了很久还是改成scanf过掉,到现在还没想明白是为什么。CD都是SB题,瞬秒了。B题是个几何题。韩帅初步想了个枚举的方法,有些bug,大家讨论之后得出一个都认为是正确的方法。韩帅上去写了,因为输出精度wa了两次。后来改成ceil过掉了。
练习赛发现的问题是,输入一律用scanf。三个人讨论了正式赛的策略:如果有几何题一定要和我讨论;每个题至少要两个人知道算法;我尽量不代码,让韩帅和金毅多做些。目标是不管别的学校,只要超过SilentWhisper就行。
练习赛结束后大家无聊散步了一会儿,有些人借到了一个篮球打起来。大概6点钟大家吃完饭回到酒店。我感觉很累,直接睡着了,一直睡到第二天早上6点多。貌似韩帅也睡的很早。
26号正式比赛。比赛之前自带键盘被发现了,只好又拔下来。三个人发现忘记带吃的,于是去附近的超市买了汽水和巧克力。
9点半比赛开始了。我从前面看,韩帅从后面看,金毅从中间看。很快韩帅发现I题是水题,我发现C题是水题,合计了一下韩帅先写了I,1Y。然后我写了C,忘记考虑空集,3Y。貌似我们两题还比较快。之后就是J题。韩帅和金毅讨论了J题,貌似金毅一直没听懂。韩帅坚信他的贪心是正确的。然后我和他讨论了一下,确实是正确的,韩帅上去1Y之。这时我们是第2,以后就一直保持在非常前面的位置了。然后我和金毅讨论了一下F题,认为可以做,但是非常麻烦,我就上去慢慢的写。这时E题和H题有些队过了。我写F的时候韩帅和金毅讨论了E题,韩帅上来写了个二分的方法,写完貌似没过样例,我继续去写F,韩帅下去想了一会儿,发现想的很清楚了,于是就让他上来改,交,终于得到Yes。这时我们4题,看了一下board,有5题的,我们是4题第一。F题写完后没过样例,我发现F题想的有bug,不是像我和金毅想象的那样,而是还需要加挺多东西。加之场上没有队伍过F,而我们对面的队伍只过了3题,有一题是D。我就把F放下了,和韩帅讨论了D。一开始是没有想法,感觉必定超时,后来我发现可以把输入读进来,采用离线算法,预处理出一个表来。感觉挺正确的,就让韩帅上去写了。韩帅写了一半发现要二分,于是我帮他写了一下lower_bound和upper_bound,折腾了一下过了样例,交上去就Yes了。过D的时候已经封榜了,我们接下去的策略是同时做两题,要么超神,要么超鬼。因为金毅和我已经想好了H的AC自动机做法,并且花了很多时间把洛克的标程修改好了(洛克的AC自动机标程太难用了……我们改了好久好久啊),韩帅和我讨论了B题,说是非常想上去写。于是最后一小时我就辅助金毅搞H和辅助韩帅搞B,主要是H,因为H希望比较大。很不幸,H写完后交上去超时了,韩帅继续写B。金毅发现H的数组开小了,改之,超时。我和金毅商量着把状态改成用map保存,仍然超时。交了3次超时后我们认为没有办法了,此时时间剩下不到半个小时。最后我想到H题状态转移的时候可以不沿我们的AC自动机的边转移,就是说我们的AC自动机少边了,大囧,发现已经来不及改了,只好放弃。最后的希望是韩帅的B题,可是到倒计时的时候,韩帅没能把B写完。我和金毅听者倒数看着韩帅奋斗到最后一秒,比赛结束了。
比赛结果是我们5题,排名第3,前面复旦和浙大的两个队伍都是6题。我们少了H题,主要原因是算法没有事先想的非常清楚(其实写之前我和金毅都想到了可以添废的01,可是在画AC自动机的时候就都忘记了),还有我去写F是个大错误,浪费了机时也让我思考别的题目的时间变少了,这些时间用来多想想H说不定就能搞定了(当时H有人过,而且是比较后面的队伍过,F没人过)。这场比赛韩帅做的贡献非常大,思路清晰,代码很稳,是前途不可限量的队员。金毅发挥的不是很好,和平时表现出来的强大实力不能匹配,希望能够通过训练,在赛场上能发挥应有的实力。
宁波比赛估计是我最后一次参加ACM性质的3人组队赛了,在Finals遭遇最惨痛的失败之后,又找回了我大一刚进入集训队时候的感觉。感谢韩帅和金毅能给我这样一次机会,希望你们也希望全体WHUACM集训队员在2009赛季一路走好!

相关文章

  • 评论 (1)
  • 引用通告 (0)
发表评论 引用通告

  • yayamao | 回复 1F

    五月 17th, 2009 at 23:21

    能否讲下D题的详细解法?….

暂无引用通告