2014 39th ACM-ICPC 北京赛区 总结

万万没想到,拿金了。

在经历了西安赛区的打铁经历,感觉我们已经很坦然了。怎么说呢,虽说有阴影,但那也是成长的一步。我在西安打铁之后跟队友跟姐姐说过“如果北京是铜或者铁,我就退役”。记得曾经,很多人问我要搞ACM搞到几年级。有不懂ACM有了解ACM有熟悉ACM的人。好像我只对姐姐正面回答过“看看今年打的成绩吧,感觉今年是关键”。因为大二的时候跟PZ,JM一队,那次有个银,不过主要是靠他们,而且那次也有一定的运气成分。如果今年的两次成绩的最好是银尾或以下,大概我就会退役吧。因为那样的话大概就说明我尽力之后也就这样,清清楚楚无怨无悔。

西安的时候打铁了,那天晚上想了很多很多。本以为今年就此结束,我的ACM也就此结束。打铁真的太不应该了,对不起很多人。对不起那些让我任性让我*的亲人,对不起那些帮我应付课业的同学,更对不起那些谅解支持我的朋友、好朋友,对不起队友、教练、师兄、学院、学校。仿佛所有的一切都是做梦,当时的我真的很辛苦,可以说是,大学里最出乎意料的事情。

那天晚上,教练说我们队原本定于北京的赛区的还可以去,需不需要换成上海赛区,那一刻真的不知道说什么了,本失去的机会竟然还在。记得那晚,我们三个纠结了很久很久,都不敢妄下判断去哪个赛区。大概大家都害怕都恐惧,这大概就是阴影的一个体现吧。北京的题是上交出的,比较靠谱,我们之前网络赛的时候上交的题也是不错的;上海的时间靠后,便于我们调整失败心态和竞赛状态。最终我们决定北京。

来之前,我已经不敢定下什么目标了,我只想好好珍惜这个机会,享受这个本该没有的机会。听说北京很冷,把最厚的衣服带过去了。到北师大注册,这次纪念品有google笔记本、明信片之类,还是不错的,不过其实当时没有太高兴,因为我还沉寂在西安的阴影里,应该说是没有心情开心吧。去饭堂吃饭,不习惯那里的东西,就把饭吃光了,然后把肉丝挑着吃完了。另外的2.5份菜和一份汤都没吃。然后就是,上面写着20块的饭票竟然只能换到1支饮料,这喝的就是情怀。然后就是晚上回酒店,也没买零嘴吃了,没心情。

那个google笔记本是我认为神奇的力量的地方之一,因为一年前我们拿银的那次有google魔方。

周六——热身赛

身后是中大一队,好紧张。

周六开了个vj的手感赛,跟JM,WJ码得挺愉快的~(董老师的建议——保持手感)这是我认为神奇的力量的地方之二,神奇之处见后文。然后就是去热身赛,AD是“不正经”的题,B是水题,C是中等题(?)。A是数习题册有多少个ACM单词,D是针对单测试样例枚举答案2^3的题,B是质数搞一搞,C据说是差分约束,不会╮(╯▽╰)╭。

这里又有第三个神奇的力量的激活点。A题,比赛前,上交的裁判(非常好的裁判,不愧是拿过final冠军的上交的裁判)说ACM可以解释为Always Challenge Miracle!至于这句话的神奇力量可以说是最神奇的地方。这里卖个关子,详见后文。哦,当JM数完26个ACM后,发现A题里有Always Challenge Miracle!我当时深深以为这个缩写后也算,在JM交了发26个后,跟他说了声就交了发27个。

周日——正式赛

早餐继续吃庆丰包子铺~jm开pc^2,cb之类,wj看中间,然后jm让我这次从前边开始看。jm的头文件还没include完之前,我发现A是个签到题,抢电脑,敲之,6分钟1A。这时候很多过最后一题,jm好像是在看前边的题,wj在看中间,我跟wj转看最后一题。因为一开始我感觉K有点像冒泡搞,而冒泡搞之前在西安热身的时候是wj搞出来的。讨论后发现可以O(n),由于我对这题比较熟悉,我去敲之,23分钟1A。前2题的1A我觉得都是周六早上的手感赛的功劳。然后在我敲的时候,jm和wj好像就发现不少人过的H题的真相。jm敲之,wj看D,我看I,我问wj那个D题的题意,然后我顿时觉得是贪心,说了贪心思路,wj也觉得像是,不过碍于复杂度是n^2,不像是数据范围为n<=200的正解,有点不确定。jm顺利1A之后,比较多人过的还是D和I,我让wj先去敲,我跟jm搞I,jm推圆与圆相交的面积,我推一个简单的容斥。wj交了一发D,返回wa。就先让jm敲I。就在jm敲I的期间,我看着wj的打印代码,发现有个bug,感觉贪心策略要对边界作修改。80分钟的时候jm再次1A。这时候,我让wj改一改那个贪心边界,jm再次提出怀疑,我跟wj也动摇了。然后wj改完后试样例,发现不过样例,我写了个数据证明这个策略是错的。。。然后wj突然来一句“难道是区间dp?”,瞬时,我跟jm都安定了。因为每一次,wj说出“难道是XXdp?”之后,只要让他安心推导写写再让他稍微一写就可以1A了。真的是dp小王子=。=(赛后看他的那个dp转移,深深觉得美妙神奇)这个时候,我们5题了。比赛进行了2个小时。如果之后不出题大概就是银尾左右。

接下来,就是搞B和F。。。我们先是想到F题的简化版的解法。F要求的是一个东西的3次方的期望,但是我们只能想到这个东西的1次方的期望。B则是一个YY构造。一开始我们三个都说出自己的YY,然后都被内部证伪,都不可以采用。然后我想到一个从中间往两边贪心填充的YY,好像可以过比较多的样例,我们也想不到什么反例,看到这么多人过,我也就去写写了。。。他们则继续搞F。。。当时我打B题打了好久好久,真的是打得很倦了。。。应该有1个小时,感觉比较多的细节什么的,期间他们突然说F可以做,就让他们先搞了。因为B题的YY不一定正确,但是F那个应该是算法一出样例一过就可以顺利1A的题的样子。我就打印B题debug了。。。。然后jm打完后调试的时候不知道哪里错不过样例,打印之后机器继续交回给我YY模拟。。。我把一个地方改一改,也过样例了,交一发,wa了。。。然后jm也发现他少了个memset什么的,果断改之交之,顺利1A,那个时候,银是一定有了。那个时候其实已经封榜了,时间大概剩下30分钟吧。我继续改B。。。静态调试没发现什么错,然后wj建议我随便输数据测试,然后我试了一些,很庆幸,测试出一组错误数据,发现这个YY是有漏洞的。。。那个时候将近崩溃了,因为想不到别的YY了。。。。我抱着侥幸的心理,写多一种贪心策略,即如果两个策略都no才是no,否则输出可行解。不过我认为T有5000应该是过不了的,本想着再想一个策略再交,不过考虑到时间可能不够就加一个策略就交了。果然,wa了。这时候,wj说话了,大概就是说,lc说过“比赛快结束的时候这种题就是要不断地打补丁,然后就可以过了”。jm也同意,然后就像是点亮我心中的火。仿佛冬天里又温暖了些。可是那个时候大概只剩下13分钟左右,如果要重新写多一种贪心策略应该是来不及的了,之前写了2个都写了很久。然后我灵光一闪,我有用到一个优先队列,然后优先队列默认是大顶堆,我就把前边的代码复制了一遍,然后再嵌套一个no,然后改成小顶堆的贪心策略。也就是,现在是3个no才是no,否则为yes输出可行解。(这个解法我依然认为是错的)这时候剩下10分钟左右。提交!YES!

据wj说,我看着那个YES愣了2秒,然后我大叫一声“啊!”,前后左右、志愿者、参赛选手都看过来了!!当时那个兴奋啊!!都合不上嘴了!!

7题结束比赛,这次真的是,再一次,少了谁都不行,没有jm大概就搞不出那个F的3次方期望,没有wj大概就写不出那个区间dp,没有他们的鼓励我大概就没有3个no才是no。。。。更何况还有罚时。

最感动的是最后B题我写太久有倦的心情的时候,队友很支持很鼓舞。而热身赛那个ACM单词个数的Always Challenge Miracle也变成了事实。最后那一题在我看来就是个Miracle

===================================================================

最后的结果是7题排名14(除掉打星)真金哟(^U^)ノ~YO

颁奖的时候我想让jm或者wj上去的。。。可是他们推我。。。。然后我在上边一直抖抖抖o((⊙﹏⊙))o.抖了好久好久哈哈哈

拿着金牌,我回到座位上还是抖,站不稳了哈哈哈

===================================================================

好像这次总结有点长。开心就好。

怎么说呢,ACM一路走来,很多人都照顾了我,无论是队内还是队外。

不想在这里特别谢谢某个人,因为我想谢谢的人太多太多。。。

ACM可以说是陪伴我走过了2年的大学,还记得大学还没开学就自学C++,新生选拔赛前学习dfs、bfs、并查集等等、后来的寒假暑假集训、校赛省赛邀请赛区域赛。日常训练。太多太多。。。。

喜欢ACM的干脆利落、实打实干。

====================================================================

这篇总结写了好久,可能有2个小时以上?之后或许会再补上,还有太多想说

上一篇:[转]Linux服务器上11种网络连接状态 和 TCP三次握手/四次挥手详解


下一篇:SPOJ D-query(主席树入门)