记录第一次CCPC网络预选赛

· · 生活·游记

这是河边喝水的三只猫的第二场网络预选赛,本次赛事复旦大学命题,图论考了不少。一下午的奋战,A3 题,中规中矩。

赛前做了前两年的 CCPC 预选赛题目,难度合理但是颇感怪异,因此赛前略有紧张。但是在机房快乐的氛围下,调整心态顺利开始比赛。

由于最初是队长机看题,所以我们都在思考 A 题,但是我没什么思路,因此在队员机可以看题时,果断转向 E 题,当时 E 题已经 50+ 队伍解出,显然是签到题。因此我简单审题就发现了解法,只要考虑能确定谁赢得的场次更多,就可以确定胜者。因此很容易求出至少观看场次。和 zmx 简单交流确认正确,交了一发,AC

之后陷入了一段时间的瓶颈期。在 1h 内进展缓慢。我和 zmxG 题上长考,因为 G 题是很明显的数据结构,但是我想到的分块做法显然超时,因此需要优化;msc 在孤军奋战 A 题,因为他想到了数学解法,但是需要修缮的细节很多。又过了一段时间,msc 搞定了 A 题,一遍 AC,由此我们在题目数量上完成了追赶,而且做出了一道较少队伍解出的题目。

这时观察题目状况,发现 K 题有相当多的人提交,但是我们队的图论部分较为薄弱,一开始我甚至读不懂中文题面(没想到英文读不懂,换成中文也看不懂,悲),但是经过 zmx 的解释,我对题目再度审视,逐渐理解了题目的含义。而且我通过递推的方法,推演出了一种较优的解法。但是由于数学的薄弱,我无法证明这种排列的优越性。msc 提出写一个暴力的方法在小数据范围内验证我的想法,于是他开始写暴力代码,验证正确,我迅速交了一发,AC

不过 $G$ 题并没有想象中的顺利,我们一直在思考时间复杂度的问题,反而忽略了空间复杂度。在我发现我的分块解法可行时,经过讨论我马上上机。写的很快,但是交上去居然内存超出限制;我尝试删去一个前缀和数组,缩小内存,再交一发仍是内存超出限制。这时 $msc$ 决定试用离线算法。于是剩下的时间里,$zmx$ 考虑 $C$ 题,我优化自己的算法,$msc$ 尝试离线算法。 最后 $30$ 分钟提交一次,但是惊讶的 $WA$ 了,于是我们当即在本地开始造数据,用我的内存超限代码跑出正解,再和离线算法代码核对。改掉 $bug$ 以后,交上去又是超时。这时剩余 $10$ 分钟,我决定再试一次,把我的分块代码进行二次离散化,取消 $map$,节省内存。但是由于我写错了一个数组大小,在最后没能调对代码,遗憾收场。 不过这场比赛我们更有秩序,心态平稳,相较于上次 $ICPC$ 网络预选赛,更有经验。同时也暴露了代码能力不足、数据结构应用不熟练、图论知识点掌握欠缺等问题,希望我们继续调整。 ***河边喝水的三只猫,不会一直低头饮水,也会偶尔抬头,看看天上的明月,河面的波光。*** ***也许,每只猫都有一个 $ACM$ 梦。***