ACM-ICPC 2012 Asia Chengdu Regional Contest 小结 By edward_mj@ArcadiaConvent

随着复变考试以及我的补眠结束,终于有时间写这篇小结了。数据结构晚上快速看一下课件明天直接去考好了T.T
今年Regional,除了浙大出题的长春赛区,国内的赛区去光了,战绩是

  1. 天津正式(季军 + K题FB) 小结:http://edwardmj.wpengine.com/?p=768
  2. 金华打星(银牌) 小结:http://edwardmj.wpengine.com/?p=820
  3. 杭州打星(银牌)
  4. 成都正式(季军 + E题FB)

赛前prowindy一再强调别去北大出题的赛区,现在看来,还真是对的……
我一直说复旦出题很靠谱,虽然有点难被虐成狗,但是我觉得做起来很舒服,现在看来,也挺对的……
就像是冥冥中被克制了一样,中间两场总有万人轮的题被卡到死,然后感觉差不多要过了却死活弄不出来。
下面说说我对我们队伍的看法吧。

  1. 首先必须注意到的一点是,我们每场比赛到最后一刻都还在调试程序……
    这说明了什么?
    我们根本没把自己所能做(该做)的都做出来。
    这个问题可能代表了两点,一个是我们这个团队对算法的实现能力已经圡成狗了,另一个是我们会写的太多了,真的写不完……
    其实说白了就是代码实现能力和YY能力的不匹配?
  2. 我一直觉得每个人都比较全面的队伍才比较容易配合,这样无论和队友讨论什么,都能够互相理解
    讨论永远是建立在双方都对这东西有一点了解的前提下的
    但是时间短暂这个东西太难强求了,毕竟我们和THU,PKU的OIer队伍不一样,个人能力不是每个人都比较逆天那种……
    希望到final的时候,我们每个方面至少有两个人比较懂,也就是注意刷题的时候不要只刷单一方向的。
  3. 我发现我们现在的策略基本是:基本题就不提了;见到物理以及数学题直接扔zYc;见到比较繁琐的蘑菇题、几何等直接给prowindy;然后数据结构、图论、字符串之类的问题都直接给我。
    而我的那一块队友比较难帮上忙,如果要帮忙看代码的话可能也要讲好久,于是一般是放我单干。
    zYc那一块大家都比较相信他。其实有时候不需要推公式,直接来点暴力的递推就足够了,而这种时候zYc很可能会去推很久的公式,这上面还是有很大配合空间的,我和prowindy对这类问题都是可以搞一搞的。
    而prowindy的那类蘑菇题几何题其实往往更需要队友参与……就我个人而言属于看到这种题就头疼的=.=,虽然用力去做可能效果也不差,但是会有种比较本能的抗拒,这是我自己心理问题了,需要做一点调整。

前面是一些主要感受,下面来说说最后一站成都的比赛过程吧。
开场prowindy告诉我A题很简单,我阅读速度比较慢,坚持看完题目以后

5min 1Y A

然后zYc说他做过K,好像是什么bfs还是百度之星原题什么的……写了一下WA了,prowindy帮他一看就发现错误了,似乎是prowindy以前被那个东西坑过,于是

52min 2Y K

在zYc弄K的期间,我看了D和I,瞬间就想到了解法,D显然是分sqrt(n)的做法,I就一个递推算数目。
然后我觉得I比较好写,就告诉prowindy递推式子,我先去写D企图抢First Blood。
D TLE了好多遍,百思不得其解。于是在我看代码的时候prowindy在TLE了一遍以后改成离线的做法过掉了I

69min 2Y I

接下来就是我继续搞D,zYc去做BCJ三个数学题了。
这时__holy__过掉了D,First Blood被抢掉了T.T。
期间B题弹了个cla,zYc看了一下就去搞了,我向prowindy讲了一遍代码,突然发现重边会导致我的算法每个询问并不是sqrt(n)的,合并重边以后WA了一遍,把一个int改成long long以后就过了。

115min 5Y D

zYc很给力地把B的组合公式推出来以后也过掉了B

117min 1Y B

这之后prowindy交了一下H,T了以后就放弃了。
于是重点变为CEGJ。
G是个很扎实的蘑菇题,但是写起来比较麻烦,于是prowindy就去写了。
zYc徘徊在C和J之间没有思路……
我看了看形势不太对,去看掉了没看过的E,F有点长挺讨厌的让zYc看掉了。看看board发现C比J过的人多多了,于是去zYc就直接攻C去了。
权衡了一下,F显然是个贪心,可能要三分一下,然后算算gcd什么的,略麻烦……
E题是个字符串的题目,想通了以后应该不会特别难写。
我就跳E了。
于是成了三开的节奏 我 E prowindy G zYc C 机器基本让prowindy和zYc占着
E我很快想到这个过程就是KMP的过程,于是企图在这上面进行一些修改。不是特别久以后得到了一下看上去有点疼的算法。然后花了好长时间找了几组觉得会挂的反例,但是发现都没挂。
于是我又花了一段时间把这个算法证明了。
然后我pia掉正在写题的队友上机写了,很快写完以后发现过不了sample,打印了一份。
对那个sample模拟了一遍感觉我自己的算法没错,于是我看了看代码,不是特别久之后就发现了手写的KMP里面写漏了一句话= =b,于是改完以后过样例了。
在我交之前prowindy跟我说如果觉得水就封board以后交……然后我说了一句,不是特别水,于是交上去就1Y了。
志愿者送来了两个同色的气球。

235min 1Y E First Blood

接下来基本还是继续之前的节奏,zYc C prowindy G,我只能帮两边看……
然后到最后G没写完,zYc C没过sample……

后来我们觉得杯应该没有了,就打算不参加颁奖典礼,免得太过奔波,直接去机场附近找个旅馆住,方便好好复习……
走到一半老朱告诉我们有杯,于是又跑回去和fancy会合……预约了早上6点的面包车以赶去机场。

颁奖的时候被黑飞这种事情还是不要说出来丢人了。
于是看DS课件去

加入对话

16条评论

      1. 对,我在TC上做过枚举方式一模一样的,但是队友告诉我的那个是抽象过后的模型……于是我就不知道怎么搞法了……
        哎=___=,难得出一道前面的队伍几乎没人出的题,却把握不住机会,感觉很难再有这种可能夺冠的机会了…
        这个头像貌似是跟你id的hash值有关……

    1. 那题和这题不一样,那题喷了就不能喷掉的……所以既是前缀也是后缀。
      这题相当于找一个最短的s的后缀使之在当成KMP模板串来匹配s的过程中,不会出现j = 0还没有字符可以匹配的情况。

      那么先别管后缀这个条件,考虑如何构造一个最短的串使之满足“KMP匹配的过程中不会出现匹配不上的字符”这一条件。
      求解这个问题的办法,仔细观察一下
      cabc(这个cabc就能达到上面的条件)

      cabcd(这个要cabcd才能达到)
      这两个串的不同之处就知道了……这个要说清楚挺难的。
      大概思路就是贪心,不行的时候再在原结果后面加一些字符。

  1. 实现能力太土了
    C H G都是一步之遥能A的题,遗憾之美吧。。
    之后要更用力才行!

  2. 第7行, 程度..

    你们居然把E做出来了太牛逼了.
    其实缺乏经验啊, 还有5分钟就应该封board以后再交的..

留下评论

回复 s-quark 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注