台湾菜

宁波理工杯全国邀请赛总结

twcai • acm/icpc

周六上午做校车出发去NIT比赛,上午10点左右到的,发现宁波大学园区绿化超赞。等注册完比赛,入住宾馆已经是11点钟了,吃完饭在两位志愿者的带领下逛了下校园,就开始了1点钟的热身赛。
热身赛的题目没有想象中那么水,剩下三十分钟的时候我们开始测一些杂七杂八的东西,我们只做了两题,看到周围的全是4题的大牛,感觉很有压迫感……结束前测了下Java,不过感觉Srbga应该不会出考察大数这么恶心的题。
结束后和杨MM见了个面,他还是跟以前一样那么有艺术家气质……晚上躺在宾馆床上看了会论文和比赛需要注意的细节,看了会电视。接着ZJFC的庄大牛来我们房间热情接见了我们,Orz。
第二天,匆忙的起床和洗漱,吃了好大分量的早餐,参加了简短的开幕式,然后在9点左右进入了比赛场地。
比赛开始后,我从后往上看题,看到了描述很短的I题,我第一个念头就想不会是和四月月赛差不多的题目吧。抱着好奇心读了一下,发现是简单题,于是第一个上机敲代码,交完返回一个WA,于是打印代码查错,Teddy上机打C。我检查了一遍代码,发现输出的时候一个空格不小心打成了两个空格……改完后,再检查了一会儿,提交后终于返回了一个yes。
Teddy打C的时候,我读了一部分题目,感觉:A肯定不像题目描述那么简单;B可能用搜索,但是没什么感觉可行的想法;D是碰到过的题目,但是数据量大了很多,感觉不好下手;WYB看过E了,据说是DP,这个我不会;最后看看还是J可能上手,想了一下觉得是贪心,不过不敢肯定,因为在之前的正式比赛中,我的贪心屡战屡败……
在和WYB讨论后,我决定上机打一下,这时候Teddy的C已经Yes了。我上机的时候,Teddy和WYB讨论了E,似乎很快得出了可行的算法。因为我不是很肯定(n^2的算法怕超,只遍历一遍我又担心不是最优),于是Teddy换下我,上机打E,我在打印出来的代码上继续写(我发现我在纸上写代码的时候,思路会比较顺畅,可能跟上机有压力有关系)。Teddy写好后交了一下,返回RE,于是他下机察代码,我上机打J。中间Teddy交了一到两次,都是WA。我打好J后提交了下,WA……于是换人,我检查了一遍代码,发现很多错误……一一改掉,为了保险起见,我把算法换成接近n^2 (区域赛的题目没有在题面中规定时限,有时候也许就是暴力+一些优化),在Teddy拿到了E的Yes后,我上机改代码,提交——返回Yes!
这时候已经三个钟头了,我们排名第9,比赛看上去很顺利,但是悲剧就从这里开始了……
当时过的人最多的题目是H (赛后据说H是最难题……),然后我们就在题面最短的A和H之间纠结,但是一直没有想法。中间甘露又跟WYB讨论了一下F,据说是图论……等到还剩50分钟的时候,我建议转到B,但是又确实没有什么想法(也许是没有试过深入的去想吧)。当时觉得剩下的时间只够打A的代码了,然后就开始死磕A一直到比赛结束,因为罚时多,我们队封版排名跌到14……
比赛完是晚宴,中间刘老师和TJU的于老师开玩笑,很有意思。颁奖典礼,我们坐在DD牛的后面,请他讲了一下A和H的做法:A是数论,H是全排列+简化的AC自动机。颁奖典礼比较简单,但是主持人MM很nice。女队出三题拿了铜奖,其他队都出4题拿银奖。
这次比赛我们队发挥的应该还不错,A和H是实力有限,没有办法,要想取得更高的荣誉,必须在实力上有所突破。这次比赛也有失误,赛后看到刘汝佳说B和D都是最暴力的解法 (B的判非法的细节我还不是很明了,但这在比赛中确实是个可下手的题目),但是我们都不敢上去尝试了。
省赛只剩一个月了,什么杂七杂八的作业都滚一边去吧。

Update : A题解法见GCC大牛Feli的博文:(a/b) mod m 的算法

comments powered by Disqus