这是我们队的mmd写的总结,发布在珞珈山水bbs上,转载过来。
今天我们做的并不是很顺利,前面出题太慢,我状态不是很好,导致罚时也比较多。
拿到题目,我们三个人都有点晕。觉得题目有点难。三个人的身体状况也并不是很好,都
有点小感冒,cz还在发烧, 我鼻子不通气。不过我们的心态还都不错。
我们在把题目几乎看完之后,没有找到简单题。但是我一直觉得F是一个可以水的题目。在
跟feli商量了几句之后,我去提交了F,在还没有返回结果的时候我就发现我交错了文件。
改之,得到了期望中的tle,然后我还知道一种要用到后缀数组的做法,不过太麻烦,所以
我在求速度的情况下,去提交了两个for循环,看看结果是tle还是wa,结果居然还是tle。
这时候我跟cz和feli他们俩个说,这是我已知的最好做法了,不可能有更快的,肯定有别
的问题。先放一下这道题。
这个时候cz跟我说j题是一个比较麻烦的搜索,让我想一下可不可以做,我按cz的思路想了
一下,觉得处理起来比较麻烦,所以我们两个决定先放一下,这时候feli看了一下board,
然后发现已经有两个队伍ac了j题。我们三个于是意识到了我们想复杂了,还好feli马上想
到是一个简单的dp,他去写这题。交上去之后,回来一个wa,feli想了一下,发现是题意
理解错误,改之,得到了第一个ac。
这个时候已经一个多小时了,而且很明显我们的成绩不是特别好。不过我们倒也没觉得什
么,因为平时比赛我们队就总会出现这种情况。罚时比较多,出题比较慢。
cz在看了f题之后,跟我说了f题的trie树做法,这时我才想到我想的做法,全想反了,所
以才会得出来此题非常难的结论。由于手头也没有trie树的模版,我也就只能硬着头皮现
写了,所以这个题出的比较慢,中间还差点写头晕,总感觉写的有问题。还好算是ac了。
此时我们二题,要出第三道题的话,就只有出g题了。g题是一个经典题,题目就是求最长
重复子串,但是题目里面并没有说明子串是不是可以重叠的。苦于,我没有带后缀数组的
论文,所以里面最关键的一部分求h函数,我忘记是怎么求的了,这才是最郁闷的,比赛之
前我还在那里念叨忘记带论文。我在那里郁闷的推了半天,推出来的时候交上去ac了。虽
然此时我们三题,但是时间比较靠后。
此时我们三个人都没有题做,然后我们大体商量了一下,我们决定放弃其它题,去做a和d
。
我和cz去做a,feli和cz去做d。
结果证明这并不是一个不太明智的选择,因为最后a和d也就才三四支队过。而i题有十几支
队伍ac,我们却连想都没有想。
i题数据太弱,如果数据强的话,是一个我们比赛之前就讨论过了非常经典的难题(最小外
接圆),队内没人会做。我们完全没有往数据太弱那方面想。事实上可以通过凸包+枚举a
c。郁闷的是天大他们就是这样ac了,而且因为罚时比较少,所以在我们前面。
feli在比赛还剩50分钟的时候,rp暴发把d题ac了。我们就这样四题了,剩下50分钟,他们
把时间全放在了我写的a上面,不过我状态比较差,一直wa到最后。此时board已经封掉了
,在还剩20分钟的时候feli无聊去看了一下气球,说只有6支队伍过了四题。
其实在很早的时候,cz就已经把h题的贪心想好了,但是他觉得没有完全证明,所以没有敢
去写这个题。我觉得这也是比赛失败的地方之一,华科他们就是贪心过掉了,我觉得cz也
肯定可以ac,因为这类的题,他赛前做过非常多的研究。
整体上来说,我们最后成绩虽然不差,但是比赛的遗憾还是非常多的,我相信我们在下一
站的吉林可以做的更好。