ACM/ICPC 2014 World Finals —— 退役战

zjuWF2014

sigh,到最后还是没有拿到奖牌,不过好歹刷进了第一版。
imag0141

第15也不错了。

说说过程吧。

开场大家看题,肚子白ABCD,我EFGH,猛犸IJKL,看了好一阵,没有一题会做……

然后猛犸跟我讲了K的题意,我知道不是圈的怎么做,感觉圈的肯定是类似的,在那个做法上改,结果想了好久都没想出来。清华一下就秒了,有点欲哭无泪。这显然这是个原题,但是我们却不会做,当时就感觉不妙。
我和猛犸轮流想K,还是不会。

有人也过D了,猛犸就问肚子白题意,弄了一下终于有题会做了,令人感动。 D 55min 2Y

C也有人过,肚子白开C,调了好久,sample也不对,好不容易调对了,一交又是好几个WA……
猛犸只得又跑去看,我在G和K中交替想,终于发现我K题想的方向根本是不对的,告诉了猛犸这个题的关键:每个区间的后继是固定的。然后终于想清楚了,猛犸问我写还是他写,我觉得G我还可以想一下,I裸平面最大团有人过感觉也可以上去乱搜一发,于是觉得猛犸上比较科学。于是猛犸想了一会儿直接就过了。K 127 min 2Y
其实我觉得K题还是挺难的……但是navi说是东京大学校赛的原题,USACO据闻也有,于是就被万人轮了……我们没做过智商又一下子没上线,只好被碾压了。

期间我I写完了,交了一发TLE,顿感没救。

猛犸又去写了一半B,然后说复杂度好像不太对,跟我讲了复杂度不对的部分,让我去想。
我弄了一下,发现这就是多重背包的凸优化。正确做法是用dp中的重量对“当前物品重量”取模分剩余类,然后每个剩余类的转移利用决策单调构建单调队列来做。有点讽刺的是,这是dd的背包九讲里,唯一没有讲的多重背包的姿势。

虽然我会做,但是那个单调队列的维护需要推的公式很复杂,我推错好几次……

因为这个题除了这个离散的部分,后面还有连续的部分,我的代码和猛犸的代码套在一起,也不知道是谁的错了,怎么交都Wrong Answer。
期间我的部分发现的几个错误,猛犸的部分本来说没问题的,结果又被肚子白发现了几个致命的错误,改来改去也没见过。

然后猛犸和肚子白就去想E了,想了一会儿想出了科学的方法,封榜后1min就过了 E 241 min 1Y

这时候,猛犸选择了去改我的I看能不能搜过去,我弄了好一会儿也没弄对B,于是就跟肚子白讲。然后肚子白大概没怎么接触过这种姿势,好像也没怎么听懂。然后我发现我有一个正负号搞反了,改了以后还是无尽的WA。

然后比赛就结束了。

最后B也不知道是我的代码有问题,还是猛犸的代码有问题。
I搜不搜的过去只能看脸……中国队里也只有北大脸好搜过去了。

如果猛犸过了E以后,和我一起折腾B的话,我觉得九成就5题了,这样第10就有铜牌了(前12有奖牌)。还是有点太贪了。
当然也不怪猛犸,毕竟I也是有可能搜过去的,只能说结果是我们都悲剧了。

于是就这样在大三和FQW,GXX一起退役了,也许后面会补一个退役贴吧,不过现在得用力准备回去连续5天的考试了T_T

说实话,这两年final打下来,真是挺伤的,上一年final刚好是考试周,一坨考试都缓考了。
今年是考试周之前,回来就连考5门,= =b只能求老师们尽可能手下留情了……

ACM/ICPC 2014 World Finals —— 退役战》上有10条评论

  1. I题不是搜啊。

    你枚举最后最大团的最远点对,然后会发现剩下的可用的点就是一个二分图的最大独立集。

  2. ym可以去wf的,据说这次题目是为俄罗斯准备的?不明觉厉。

    无限ym~~~(其实可以缓考没什么不好的,考完试优哉游哉地嘚瑟一下……

    只为留名……

发表评论

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