这是我们队的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,因为这类的题,他赛前做过非常多的研究。

整体上来说,我们最后成绩虽然不差,但是比赛的遗憾还是非常多的,我相信我们在下一
站的吉林可以做的更好。
posted on 2007-10-28 23:36 Felicia 阅读(2403) 评论(19)  编辑 收藏 引用 所属分类: ACM/ICPC 纪事
Comments
  • # re: 2007南京赛区总结 by mmd
    Felicia
    Posted @ 2007-10-28 23:37
    其实我应该去做I的,其实cz应该去做H的,其实mmd应该能ac A题的……
    有太多的其实,却成为了遗憾  回复  更多评论   
  • # re: 2007南京赛区总结 by mmd
    wywcgs
    Posted @ 2007-10-29 11:29
    最小外接圆真正算法不是传说中最远点意义下的Voronoi么  回复  更多评论   
  • # re: 2007南京赛区总结 by mmd
    cuiaoxiang
    Posted @ 2007-10-29 16:41
    mmd功底还是很强的
    要是我如果手头没有论文,是不可能在比赛这么紧张的环境下把suffix array
    当场写出来的

    话说你们怎么比赛没有带上模板呢?很吃亏啊  回复  更多评论   
  • # re: 2007南京赛区总结 by mmd
    Felicia
    Posted @ 2007-10-29 19:18
    @wywcgs
    有期望为线性的方法,清华的一个队用这种方法过了,有的队用凸包+枚举过了  回复  更多评论   
  • # re: 2007南京赛区总结 by mmd
    Felicia
    Posted @ 2007-10-29 19:20
    @cuiaoxiang
    呵呵,mmd就忘记带了两个东西,一个是后缀数组论文,一个是Amber的最小割论文
      回复  更多评论   
  • # re: 2007南京赛区总结 by mmd
    wywcgs
    Posted @ 2007-10-29 23:31
    expected O(n)? 哪里有资料?  回复  更多评论   
  • # re: 2007南京赛区总结 by mmd
    Felicia
    Posted @ 2007-10-30 09:05
    @wywcgs
    算法艺术与信息学竞赛上有提到期望线性的方法,但是没有具体讲怎么做.
    现场赛的时候唐文斌那个队就是这么过的.据说是用递归做的,直接写会stack overflow,他们改成非递归过了.
    orz
      回复  更多评论   
  • # re: 2007南京赛区总结 by mmd
    wangfangbob
    Posted @ 2007-10-31 00:29
    大牛就是大牛,呵呵,看大牛们的讨论学习不少  回复  更多评论   
  • # re: 2007南京赛区总结 by mmd
    jiessie
    Posted @ 2007-11-01 00:18
    欢迎来吉林  回复  更多评论   
  • # re: 2007南京赛区总结 by mmd
    tbk
    Posted @ 2007-11-01 13:32
    I题其实在中大老师出的那本书 第一本计算几何数论搜索那本书上有讲 一样的   回复  更多评论   
  • # re: 2007南京赛区总结 by mmd
    Felicia
    Posted @ 2007-11-01 16:39
    我知道了……以前没看过,也没带那本书去
    算我孤陋寡闻了  回复  更多评论   
  • # re: 2007南京赛区总结 by mmd[未登录]
    Neal
    Posted @ 2007-11-01 17:39
    在网上经常看你的文章.没想到你们就是gcc那支队伍~~
    呵呵!祝贺你们拿到了金牌
    不过也很可惜,我们队伍参加的是北京和成都赛区,遇不到你们队
      回复  更多评论   
  • # re: 2007南京赛区总结 by mmd
    Felicia
    Posted @ 2007-11-01 19:00
    汗  回复  更多评论   
  • # re: 2007南京赛区总结 by mmd
    lee hark
    Posted @ 2007-11-03 22:37
    goo d luc k in ChangChun.....  回复  更多评论   
  • # re: 2007南京赛区总结 by mmd
    Felicia
    Posted @ 2007-11-04 18:33
    @lee hark
    thank you  回复  更多评论   
  • # re: 2007南京赛区总结 by mmd
    solofandy
    Posted @ 2007-11-08 11:36
    你好,我是南京在你们下面的华东师大那个队呢,那天长春的时候我们还为你们加油来着,呵呵,你们果然是实力相当强的队伍 赞~~~  回复  更多评论   
  • # re: 2007南京赛区总结 by mmd
    Felicia
    Posted @ 2007-11-08 11:49
    我们要是出线对你们的压力就小啦,呵呵
    不过长春比的确实垃圾  回复  更多评论   
  • # re: 2007南京赛区总结 by mmd
    silvermoon
    Posted @ 2008-05-17 11:16
    我(大一的)现在一直在备战能进这个比赛呢,好想感受一下那里的气氛啊  回复  更多评论   
  • # re: 2007南京赛区总结 by mmd[未登录]
    不告诉你
    Posted @ 2008-07-03 20:56
    无限仰慕Feli大大大大牛
      回复  更多评论   

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理