RoBa’s Blog

这次只写比赛，比较扯淡的东西以后再补。先简单列一下题目，这里列的只是当场的想法：

A. 我没看题，被lx秒杀了

B. 也没看题=,=，好像是离散对数，但是是经典问题的加强版。据说有结论，我们不会做

C. 图论，利用求割边的那些东西

D. 图论，利用强连通分量缩点和传递闭包

E. dp，要用线段树优化，时限比较卡，我超时到最后

F. 一个特殊图(区间图加强版?)的最大团，不会做

G. 二分+Farey序列

H. 计算几何的计数题，不会做，只会暴力，超时到最后

比赛开始后，仍然按照惯例，lx从前往后，mdz从后往前，我从中间开始。读了D题，有一些大致的思路，但也有一些地方想不好如何处理，感觉不是马上能做，lx读了A说能做，就上去写了。mdz跟我说H暴力的话复杂度是10^8量级，或许能水过。然后跟我说了F，然后我就直接走上了不归路……没仔细想就以为是区间图的最大团了，这时候正好lx把A题1y了，然后我就开始翻出区间图求PEO的那些东西来搞，但是我那个模板只是判断弦图的，关于最大团问题的具体结论我已经记不大清了，当时很后悔没有带一本图论书来。猜了两种结论，都WA掉了。这时候已经耽误了不少时间，当时虽然是把这题放弃了，但还是一直留着一个幻想以为过一会儿我就能把结论想起来。这时候旁边WHU已经过了C，lx也正好想了一个C的算法，在我改F的时候交替着上机把C写完了，但也是WA，后来又改了个小错还是WA。然后我就一边依依不舍地yy着F，一边给lx查错，结果听lx讲完算法后发现他的想法基本不靠谱=,=，马上被我举出反例了……他说当时跟mdz商量了一下，mdz说感觉是对的于是就上了=,=，看来一上场大家的感觉都不大准啊……然后我们讨论出了利用双连通分量的方法，感觉是没什么问题了，我就上去重写C，结果写完又WA……崩溃……同时mdz在写H的暴力，不知道他后来交了没有，然后又来帮我们想C和D，这段时间我们做得有点混乱，大家也都有点着急，这就是中期之前我们出了一题就囧住了的原因。

还好C题我的算法框架还是没有问题的，不久发现了一个小错，这时候我又急躁了，直接改完就再交。然后又WA……奔向厕所，然后突然想到还有一个小错，回到座位发现lx也发现了那个错误，改之再交，终于在150min，两人写了两份代码，5次提交之后得到了第二个Yes。这时候我才突然反应过来F题因为时间区间可以跨过零点，所以不是一个真正的区间图，那么可能要对经典模型进行修改才行，不过我连经典模型都忘记怎么证的了=,=，于是直到这时才真正把F放弃。这时mdz提出了D题的解决方法，我感觉前期心情有点太急了，于是有意求稳了一下，这题我俩讨论了较长的时间，把所有细节都分析清楚了，然后我才开始上机，同时让mdz出数据。与此同时lx也基本想出了G题的做法，但他那题有点不太好写，我在他下机规划的空隙把D完成了，mdz出的数据也直接全部通过，然后直接提交1y。几分钟之后lx的G题也改对了，又一个1y。感觉这两道题我们是完成得比较好的。

这时候还有大概100分钟，我们4题排第二，但第一名很快做出了第6题，而且他们过的几题我们都没有好的思路，当时就感觉压力很大了。这时候场上过得稍多的是E，很明显是一个需要优化的dp，但这题一开始他们两个都不愿去想，这种优化dp也一直是我们队的薄弱环节，我又一直在和自己的弱智错误搏斗，所以直到这时候我才有时间开始想这题。同时lx想B，mdz继续对H加一些常数优化，不过B和H我都没有好的想法。写E题的时候我又有点着急，一开始转移方程没想好，后来线段树的实现还出了好几个小错，直到结束前半个多小时才过了Sample，结果交上去却TLE了。从数据规模上分析这题的时限确实很卡，复杂度是O(MNlogN)，M=100,N=10000，但因为过的队比较多我就硬上线段树了，没想到真的会TLE。后来又加了些常数优化，但还是TLE。最后lx说了一个O(MN)的算法，但被我反驳掉了，我也试图想过O(MN)的算法，但总是感觉想不好。后来问WHU他们就是用O(MNlogN)过掉的，这几天我要好好检查一下我的线段树为什么那么慢了……另一边mdz的H也在TLE中。lx的B本来还有些不太确定的想法，也没时间写了。比赛就这样很囧的结束。

从总体上来说，我们确实没有完全发挥出来，但也并不能算是做得很烂。如果我最后的E能过，那么我感觉我们就已经几乎做到最好，没有什么遗憾了。冠军那支队表现出的确实是超越我们之上的实力，我们输得心服口服，这样水平的队伍也确实足够有资格进入Final。虽然不计名次，我知道大家都有点YY能拿个冠军，不是我们没尽力，只是对手太强大啊……虽然我这么说有点推卸责任，呵呵……

当然这次比赛也暴露出了我们队的很多问题，前期我太早地把时间浪费在一道没有把握的题上，而且因为我在敲F导致lx不能把C题与我进行讨论，得出了错误的算法，然后又因为我着急把C题赶回来而出了一堆小错，浪费了大量的时间。如果我们前两题的速度能够跟上当时的第一梯队的话，后面的E可能也就不会没时间仔细优化了。这一系列的连锁反应都是由于我的草率造成，这个我要检讨一下。还有就是冠军队诡异的过题顺序确实对我们造成了一定的影响，这次比赛的8个题我们都没有轻易放弃，每道题都有某人或某两人想过不短的时间，甚至对于没把握的题都完成了代码，只因为已经有人过了就想水一下而已。所以赛后lx一直纳闷怎么感觉时间过那么快。如果能尽早集中火力的话或许结果会好一些。两个队友的表现都比我好得多，mdz想出了D的正确方法，lx单枪匹马干掉了G，相当的赞。我自己则是先跳了一个到最后也没人过的F坑，还没爬出来又让C坑拌了好几个跟头，最后终于挂在E坑里了。囧……

好了就写这么多了。我代表全队给大家道个歉，希望大家能认为我们还不算太给TJU丢人，请期待Neptune在后面赛区的表现。

ps. 最后要赞一下Zing，最后一分钟搞定D题。可惜还是rp差了一点，没有银牌。在杭州爆发吧，哈哈。

标签： 区域赛, 合肥

这篇文章发布于 2008年11月17日，星期一，02:28，归类于 算法竞赛。 您可以跟踪这篇文章的评论通过 RSS 2.0 feed。 您可以留下评论，或者从您的站点trackback。