2016中国大学生程序设计竞赛总结

  最近事情比较多,所以这份比赛总结姗姗来迟。趁今晚有空,总结之。

2016CCPC·安徽

2016CCPC·安徽

  CCPC合肥比赛是在10.15-16两天,第一天热身赛有3题,题面是中文的(后来有人发clarification问正式赛是否也是中文题面,得到肯定的回复后,全场沸腾。果然是中国大学生程序设计竞赛,题面都用中文写,就不用带厚重的字典啦…)三道题目,刚好一人写一道热身,之后就测了下比赛环境,特别是$pc^2$的使用,我们队伍是第一次使用这个软件。在热身赛时,$pc^2$好像评测的特别慢,基本上是提交了半个小时之后才返回结果,如果正式赛也这样,那将大大影响发挥。还好,后来从志愿者那得知,正式赛会有人工评测,评测的速度将会提上去。

2016CCPC·安徽

  第二天正式赛,这个就有点意思了,恰好遇上了更高级别的赛事——国际铁人三项比赛,导致我们的比赛从九点开始一再顺延,期间走到半路又折返回酒店休息,整个上午处在比较奔波折腾的状态,好在十一点多比赛顺利开始了。首先我负责登录系统,准备好编译器,然后开始找水题,由于是中文题面,迅速都扫了一遍,好像没发现特别水的题目。zt开了H题,不过由于种种原因卡住了,我跟gy讨论I题(之后看来,I题应该是最水的一道),也讨论了半个多小时之久。一个小时过去了,一道题都没过,zt让出机位给我敲I题,终于在71min时过了I题,算是吃了一颗定心丸。后来H题好像一直调不出来,zt心里就有点急了,于是换gy上机又重新写了一遍,终于跌跌撞撞在106min过了H题。在gy敲H题的时候,我跟zt在看过的最多的E题,应该是一个麻烦的递推,zt在推E的递推关系,我则在旁边辅助他。推完后,zt上机敲,测了几个样例就交了,然而返回了WA,我跟他检查了半天,他改了之后在177min时过了E题。然后,我跟gy说了A题的题意,是关于图论的一道判定性问题,说完题意之后,我顺口说了一句这道题可以用rand去跑(这也为后面埋下了伏笔…)不过嘛这显然不是正解,被gy给搁置在一边。本着不浪费机时的原则,gy就上机边想边敲。此时过得比较多的还有C题,是关于一个树上博弈的题目,虽然我在队内有负责博弈论,但是在树上的博弈我还是接触的比较少的。于是,先放下这题,又看了其他几道题,不过也基本上都没什么想法。到了封榜的时候,我们队只过了3道题,由于过题晚+罚时多,大约处于铁牌区。封榜后的前半个小时,A、C两道题毫无进展,此时我的心态也近乎崩溃,感觉这次比赛估计又得打铁了。大约还剩25min时,我又跟gy提了下A题rand的想法,于是gy迅速写完了rand的版本。我们先rand了10w次,返回TLE,于是改rand1w次,然后“情理之中,意料之外”地就过了…情理之中是指这道题是一道判定性问题,它的输出只有Yes和No,因此只要找到一个反例不满足题目的条件即可判No,所以采用随机的办法可以有很大的概率找到反例从而得出正确的答案(暑假训练赛的时候也遇到过一题判定性问题,那题的正解就是随机判定)。意料之外就不多说了…于是我们在284min过了A题。现在,我们手上还有一道完全没想法的C题(虽然我盯着样例已经研究看了一个小时了),zt表示要不把树上的博弈用树链剖分弄成线段,再去博弈。然而C题的博弈不仅有询问,还有修改操作,每次询问的树根又都不一样,数据规模又很大,我表示依然没办法处理。此时离比赛结束还有15min,突然间,可能是刷过博弈论专题带给我的“灵感”,一般博弈论都会往一个变量的奇偶性上去靠,而且数据规模很大,询问和修改操作只能在$\mathcal{O}(1)$或$\mathcal{O}(logn)$内处理出来,肯定这个处理不会太复杂。于是,我凭直觉猜了个结论,然后我们就马上上机敲了,zt写好建树部分,我则写博弈部分。写完后发现还剩不到3min,于是立马提交。回过神来,发现程序还没有编译,也没测样例。在等待$pc^2$返回结果的间隙,我们赶紧编译一下,还好没有编译错误。接着测了一发样例,都正确!我们在紧张地等待评测结果,最终返回了绿色的Yes!

ccpc.jpg

  284min过A题,297min过C题,最后这几分钟,我们没有放弃,反而让我们如过山车般地从铁牌到银牌,这真是我打过最紧张刺激的比赛!后来,我们打趣说到,C题应该等299min再交,说不定还能拿个顽强拼搏奖(当然,这都是后话了…)

2016CCPC·安徽

  总结一下这场比赛,前期基本处于血崩状态,水题找的慢,找到了也被卡住很久,三道水题写了三个小时。前期失常的发挥特别影响心态以及中后期的发挥,好像这属于我们队的通病,出去打比赛经常这样。这次能够拿到银牌,除去运气成分来说,我觉得应该归功于暑假的训练,正因为暑假训练遇到过一题正解是随机算法的题目,才让我们更有底气去过A题,同时因为在暑假训练的时候刷过博弈论专题(只算是入门专题,没涉及到树上博弈),C题才能找准方向,得到的结论才会比较靠谱…

  简而言之,比赛心态重要,题目见多识广也重要!

分享到 评论