2017ACM/ICPC南宁站区域赛总结

终榜: http://acm.gxu.edu.cn/board-2017-regional/

人生的第二场ICPC区域赛,也是最后一次,6题铜归,算是对我等蒟蒻退役的最好礼物了。

day -2:

       中午,在大铁门外黄焖鸡我们仨队友碰头,上次聚在一起还是上上周的区域赛题练习。解决好午饭,出门滴滴送往火车站,开始了从绵阳到成都,从成都到南宁的漫长卧铺路。

 

day -1:

       下午六点,终于到达了南宁,当时天已经黑了而且刚出站就下雨,还好雨不大,坐地铁到学校,再快步走向酒店。东西扔在房间,出门吃晚饭,两个队友一走来就选了老友粉,当端上那两碗满满酸竹味黑暗料理的时候,我十分庆幸自己挑的是比较正常口味的炒河粉…

 

day 0:

       第一天,上午去报道拿衣服,下午两点开幕式,三点半热身赛,一共有四道题,我们一人看一道,A、B题题面比较长,我看的是B题,两个队友都看完了我才看到一半,最后读完题之后感觉是一个非常麻烦的模拟+搜索,就先放了。C题是求找4个可重复数的和不大于M,最大是多少,一开始L觉得是背包,就在想怎么写动态转移,我和W就去想A题,A题加点然后查两点最短路,dijkstra可以做,但是查询次数有一百万,每查询就可能会重新计算一次最短路,用优先队列优化dijkstra是O(nmlogn)的复杂度,最坏有10的十次方,不过考虑到这次很有可能是doc老师出题(不过的确是doc出题),我先尝试了一发普通dijkstra暴力,秒TLE。然后就放了,看D题,才发现是道签到题,速A之。之后就一直在磨A题,换了floyd加一个优化思路之后,居然WA,后来才发现是一个地方没有考虑到,但是已经没有时间了。所以最后两个小时,我们只出了一道题,不过我还是比较平静…(可能是因为有上次沈阳打铁经历了吧)。我们对面的是苏大二队的大佬,他们做的比较快,比较早地就A了三道题,不过第四道B题的确是有点恶心。正解的话,A题的确就是用floyd,C题是思维+二分,将n以内的数组两两相加,结果放入一个n平方的数组,再二分这个数组就可以了。

       热身赛完了之后,我们一直在讨论热身赛的题直到七点过,然后W提出想一起来开把农药,我说还是刷题吧,然后我们就打开了codeforces,点了外卖,开始刷题到11点。十二点的时候W回去打算睡了,我想把自己的模版再刷一遍,于是又刷了一个小时多点,把一些简单的算法写了一下,复杂的算法过了一遍。

 

day 1:

       一早九点开始正式赛,很意外这次比赛居然提前了至少五分钟发题,我和W分工读题,当时L在厕所,W很快读了A题,并且认定是道签到题,当时我赶紧敲了一波之后还有些犹豫,检查了一下确认没坑再交,结果果然是道水题1A,再一看榜单,一群0分ac的,我们正好排在铜尾了。然后把我刚才看的那道L题交给W之后,我和L跟榜看第二题F题,F题看似是模拟,暴力肯定超时,但是分析一下,答案都是有规律的,只用按照规律输出即可,只是输出数据会很大,所以要用大数。因为我们仨都不熟悉java,我平时是写python的,因为上次沈阳赛也遇到两道java题被坑时间了之后,在比赛前段时间我特地熟悉了一下java的大数写法,结果没想到这次真用上了。但是…本来我直接用我自己的模版两下就敲好了,但模版没有来得及打印,eclipse还编译运行不显示控制台,调了好一会才弄好,中途加上队友要L题暴力打表看看,差点我们就放弃用java了。不过好在eclipse控制台神奇般地好了,最后在接近50分钟的时候才交了第一发,还是CE,又CE两次之后发现是PC2里没有把C++改成java…然后赶紧改了交,第54分钟AC。

       在我做F题的时候,L在想J题,W在想L题,这时候他们都还没有思路,我问了J题题意后,先思考之前看的L题,L题已经知道是一个规律题,我对照着打表数据看了一会,只看出a[i]和a[i-1]之前有个6倍关系,并且随着i增大a[i]越来越小,这时队友W突然把规律推出来了,比较类似于斐波那契数列,然后他再上机验证了一下,确认了规律就是:a[i] = 6*a[i-1] – a[i] + 2,因为输出最大10^190次方,也要用到大数,我就直接修改之前F题的代码,很快写好,第90分钟1A。而且鼓舞志气的是,这时候L也说知道J题该怎么做了,我们看了一下对面的队伍才A了两道题,也是感觉比较有希望。后面我去上了个厕所,回来的时候他们已经J题交过一发,但是WA了,特判上还存在一点问题,于是L就继续想,W就继续和我说他看的其他题,他给我将了M题,就是给一个有向无环图,求最大不连通的点集,我一开始想到的是Tarjan求强连通分量,这道题就相当于是反着来,然后翻了一下模版,这个题应该就是模版题,甚至是原题,应该就是求DAG最大独立集,即求补图最大团数量,但是模版上并没有求最大独立集的代码,我觉得这个题试着写应该也能A,不过抱着先看其他题的心态,就把这道题放下了。然后开始看I题,另外一边,队友L和W也把J题给A了,一共WA了两次,不过当时做了四道题,已经是铜区中上位了。

       I题是两个人玩矩形求和的游戏,一个人想要最终累加和最大,一个人想要最终累加和最小,游戏矩阵为4*4,每人可选2*2的矩阵,每累加之后原游戏矩阵对应部分需要逆时针转90度,求最终的累加和。因为这道题最初我读的时候没有读透,导致这道题在解题思路上绕了我们仨很大一圈,从枚举到模拟,再到博弈,浪费了比较多的时间,最后队友L用自己写了一波枚举和样例进行对比,才确认了题意。在知道了真正题意之后我和W都表示对这道题比较无奈,感觉做不出来,于是开始看H题。H题是一道简单模拟题,一开始一个3*5的二维矩阵中会有死、活两种细胞,他们每一回合按照要求的四个规则进行生长和死亡,然后跑321个回合,输出相应的数据即可。题读完没多久,队友L说之前的I题样例过了,我们就很惊讶,因为我们手工推样例都比较困难,并且根据题意枚举所有结果去选择也不能确定正确答案,我当时就觉得应该没问题,他说用的是记忆化搜索的思想,然后队友L一交,第210分钟1A。

       虽然出了5道题,但铜还不稳,封榜之后必有血战,我们赶紧开始敲H题,不过敲完测样例才发现,这道题没有我们想的那么简单,这个二维矩阵的大小是无穷大的,并不是固定3*5的大小。不过即使这样也不是很难,在封榜后几分钟我们交了第一发,意外的WA了,然后我们又出了N组数据,包括各种极限数据,都没有问题,中途也交了很多发WA,最后我和W放下看的数学概率题E题,选择了打印一份代码,L和W一起找错,让我来重新写一版I题代码,但是当时比赛只有不到半个小时结束了,我觉得我应该来不及写了,就一行行地检查打印打码,发现一个二重循环里面的某个操作中,变量i和j的用法似乎弄反了一样,让L来看,结果果真是搞错了,于是立马改了代码,测样例,交,第289分钟AC,WA了6次。然后我们仨就咸鱼了,都不想做了2333,只剩下11分钟,我们给L讲了E题和M题,L觉得E题可以做,我觉得M题可以做,只是没有时间了2333。

       最后滚榜还是很刺激的,我们觉得6题也不算很稳,毕竟最后一道题WA了6次,很有可能是铜尾,一不小心就掉了。不过还好这反向flag奶奏效了,铜尾5题,我们在铜中段,算是拿到了第一个牌。晚上吃了顿好的,我们三个浪到晚上一点半再睡觉。

 

day[3,:]:

       第二天一大早赶去火车站,同样卧铺返校。虽然前面手速再快点/读题快一点肯定能出7题再拿个银什么的,但是这场总归可以说是收获大于遗憾了,ACM三年无悔。

 

 

One Comment on “2017ACM/ICPC南宁站区域赛总结

发表评论

电子邮件地址不会被公开。