ACM-ICPC 2019 亚洲区域赛 南昌站

  • 2019-11-11
  • 208
  • 1

Day1

由于上半年邀请赛已经来过,所以一路上都挺顺畅的,就是酒店订的有点偏僻,周围没什么吃的,就直接打车去校内吃。当时已经过了用餐券的时间,就在食堂内随便买了一点东西吃(再加上教练给我们买的一个柚子)

接下去就是热身赛,A题很顺利过了,B题题面没写需要将答案对 1e9 + 7 取模,导致一开始我很高兴的抱着高精度的板子上去一顿乱敲(队友在干嘛???坐在旁边吃柚子???我……(廉价劳动力无疑了!)。之后在答疑里面发现这一点的时候,已经WA了几发~~后来lzh发现一个性质,看不下去我那丑陋的代码,就亲自敲敲敲过了(我好菜呀~~)而且在这之前,lzh已经过了C(我连看题的资格都没有,他就过了~~我好菜呀~~ 至今未知C题题意~~)

最后剩下一道D,删除一些边使图上不存在环???又是似曾相似的题???但是又没带板子???无奈之下我决定敲个 Tarjan 的板子改一改,测样例手推一下发现满足题意,但今天没 special judge???(所以之前C题输出8位小数WA了,10位小数AC也是因为没有 special judge ~~~)可题目最后明确说了需要 special judge!!!是把题目搬过来的时候忘了把 special judge 的代码搬过来嘛???但为什么还是有这么多人AK了???

赛后得知,这题将从标号小的点连向标号大的边放在一起,将标号大的点连向标号小的点放在一起,再输出两个集合中数量少的~~~

如果数据是这么出的,那么第五个样例咋回事???

群里说那是随便写得一种情况!!!

所以它并没有在测试数据里……

我们……

去食堂,用餐券换了晚饭,味道就那样吧~~然后感叹了一句银川站这一点还是挺好的,吃的喝的可以随便换(虽然味道也不是很好~~

之后买了点面包当明天早饭,就回酒店了,三人间没了?免费升级成套房?两张床的那种~~ 只能按老规矩,掷骰子,小的单独一张床。610一开始就掷了个2~~~都感觉没了的时候我最后来了个1!!!(从银川站到南昌站,一共掷了三场骰子,正好一人赢一次hh

向酒店再要了一床被子之后开始愉快的备战(打游戏

三个人都说要看一下虚树(因为武大校赛的时候,他们有个出题人说比较喜欢这个玩意儿,这一场又是武大出的题,所以……)结果,三个人都在打游戏,打着不同的游戏~~

终于,他们两个开始干活了,一个找了一些虚树的题面+代码+题解,另一个再整理些别的板子,明天一起印出来。(此时我继续打游戏~~

最后打游戏打累了,就洗个澡先睡了~~(后面具体发生了啥,我也不清楚~~


Day2

一大早在朦胧中听见610接了教练的电话,然后又躺了一会,说7:30下楼~~

果然,前一天准备的早饭只有我一个人吃了,他们全是鸽子。下楼后,开了酒店的发票,打车去学校。教练把我们扔在打印店门口,自己去恰饭了,然后我们等了快半个小时打印店才开门~~嘤嘤嘤

印完之后就是赶去体育馆(有一说一,这两个人怎么体力这么好,走那么快,还不时跑两步~~ 已经半年没运动的我跟不上啊,现在还能感受到当时的疲惫~~嘤嘤嘤

最后坐下的时候离开场还剩大概五六分钟(所以为什么要走那么快嘛~~

开场后疯狂找签到题,C题题面短,就先瞅一眼,感觉可能得dp???过了几分钟发现L题过的人也挺多的,610就去读L,发现是个计算足球得分的签到题,上去敲敲敲,过了样例提交,WA???

lzh重新读题,发现有什么净胜分???这是啥?幸好这位神仙队友看过足球,改了改顺利过了L。(此时的我仍然在默默坐在一边死磕C题的dp,写了个四维的数组推状态转移方程,至今仍然不知道L的啥啥分是干嘛的~~)(如果以后的题都是这种类型的话,我一定会逼着未来成为我队友的小学弟看各种赛事,至少要了解计分规则hh

十几分钟之后,个人感觉终于推出了像样的状态转移方程,抢过电脑一顿敲,连样例都过不了???他们貌似又讨论出了E题的做法???(队友强就是好!!!

不知道为啥,对于自己推的转移方程有种莫名的自信,就觉得是自己写炸了,debug了一会调不出来,就打印了一份代码,把电脑扔给lzh写E。

就在小姐姐把我C题的代码送过来不超过3分钟,我发现了,有两个方程在两种情况下都得转移,我直接特判掉了~~ 抢回电脑,把那两句话注释掉,再移到if的外面,过了样例耶(^-^)V

不记得还有没有测一个手推的数据,反正提交之后直接AC!!!

接下去lzh继续敲E,610给我讲E题题意再确认一下做法。嗯,整体上没问题,又口头讨论解决了一些细节。确认没什么毛病之后lzh继续敲敲敲,我在610的带领下,看了眼榜单,决定看G题。

要对 998857459 取模???这个数字怎么这么奇怪,为什么不是常见的 998244353 或者 1e9 + 7 ???

这个数字肯定藏了点东西!!!

上述是我第一直觉。

很快,lzh敲完了E,简单调试了一下顺利过了样例,提交,AC!!!(大佬tql)

趁着大佬去上厕所,我偷偷在电脑前坐下敲了个test,发现阶乘只要到2803以及之后的数字,取模之后的结果全都是0!!!

那么,对于 n ,这个数实际的操作范围直接从 50000 缩小到了2802!!!

很自然可以想到用 O(n2) 的复杂度直接处理出所有的结果,接下来就是对于 m 组询问,如何快速出解的问题。

最后发现貌似线段树可以处理~~ 诶,那不就是学校新生赛最后一题的线段树的询问嘛???lzh压中题了??? tql!!!

这时候午餐送过来了,汉堡 + 鸡块 + 香蕉 + 牛奶

这两个人又开始压榨我了,指挥我敲敲敲,然后自己吃吃吃 ┭┮﹏┭┮

终于敲完了,直接甩给lzh检查,自己开始吃吃吃~~

由于lzh看不惯我 n2 暴力的方式,直接将这部分代码全改了,嘤嘤嘤~~ 然后测个样例,过了!!! 提交 WA???

再一看,是我写的下标搞混了???改一改再交,还是WA???再看看,发现下标还是没理清楚,无奈之下lzh拿起来纸笔画了画,我们一起再理一理,改一改~~再交,AC!!!(好吧,我承认,这题是我演了~~

接下来就是愉快的看榜,吃东西时间(((o(*゚▽゚*)o)))

此时距离比赛结束,剩下不到两个小时(。ì _ í。)

榜上除了我们已经过了的4题,还有B题过的比较多,再就是J,由于J题面比较短,决定优先读J。

四种元素?一定顺序爆炸?循环同构???貌似在我们的知识储备中…又想了几分钟,发现我们可能确实不可做,就去读B题。

乍一看图是二分图,再一看数据范围只有18,再读一读题面,暴搜???感觉可以写一写诶,要是过了就可以稳一稳银了!

再仔细读了读题,确定了一下搜索顺序,但感觉会TLE,再想了一会决定我先敲一遍这个代码,就算真T了还可以用来验算数据。

成功跑出了样例的答案,但lzh随手造了一组数据就让它T了o(*////▽////*)q

由于想不到更好的做法,只能尝试着剪枝优化一下。

先将矩阵存联通性改成了vector来存每个点与哪些点联通,再跑那组数据,肉眼可见出解加快!

但交上去还是T了. .

此时离比赛结束已不足一小时,当然也已封榜,封榜前的排名为90,如果不过这题,可能又只有铜. . .

我玄学性的在每次dfs刚进入的时候就计算一遍ans用来跟全局最优解比较,如果加上未来的最优情况仍不如现在的全局最优,则直接返回。(其实这种剪枝很常用,只是这题每次都需要重新开个循环计算一遍ans,一开始就没加(但赛后想了想,貌似也可以将这个ans当参数直接传. . .

跑一遍那组数据,瞬间出解!!!

满怀激动交上去,WA. . .

回到代码界面,三个人盯着这个剪枝看,又是lzh发现了问题(tql!)未来的最优情况,就是0. . . 也就是计算出当前结果后直接与全局最优比较!

貌似没啥问题了,再交一发

……它测了好久. .好久. .好久. . 我们都以为它又T了……

然后突然蹦出来一抹绿色,象征着生命的颜色!!!过了☆*:.。. o(≧▽≦)o .。.:*☆

所以测得慢只是因为测试数据多(((o(*゚▽゚*)o)))

此时离比赛结束还剩半小时左右的时间,看了看榜单,如果这个罚时放在封榜前可以上升到三十几o(≧v≦)o

只要封榜后达到5题的不超过60队,就能稳稳拿个银^ _ ^

还开题嘛,剩下半小时

看一看吧

那就继续看题,看了一两题发现短时间内都写不出来,我就愉快的写了个随机数交最后一题,虽然几乎为0的可能通过,但我仍然乐此不疲,最后一共交了56发随机数,毫不意外,全是鲜红的WA

这次能够愉快地看滚榜,看颁奖了,不用像邀请赛的时候那样灰溜溜地改了高铁时间跑路了

讲题 + 乐器表演 + 志愿者小哥哥小姐姐合唱,接着就是滚榜

人生当中第一次在现场看滚榜,不过这次滚榜中间部分有些无聊,都没几个队过题,当看到榜单更新到一百二三十名的时候,我们还在前面,就觉得银稳了,毕竟我们封榜后过了一题,排名还会再往上滚

第一次滚榜到我们是100名左右,过题,排名上升,直接到了42!

再滚一滚,最终排名60,领了块银牌☆^ _ ^☆

接着就是例行的拍照,教练高高兴兴请客恰饭,在高铁上一卡一卡地看完了 FPX vs G2 的第一局,当时就预感 LPL 又会捧回奖杯,毕竟我们都银了(。ì _ í。)


最后附上610的帅帅的学侄的照片(他们的教练是610高中时候的学长,话说他们也过了5题,只是罚时比我们多了差不多200分钟而已,可他们才两个高二一个高一呀,如果不是打星队伍,也有块银,哎,我们好菜啊) 以及我校第一块icpc银牌,也是第一次封榜后过题的成果!

评论

  • Enal回复

    手中抓住了未来

浙ICP备19014917号

浙公网安备 33068302000569号