发信人: czogogo (cz ★野人部落★), 信区: ACM_ICPC
标 题: cz@GCC 最近比赛总结
发信站: BBS 珞珈山水站 (Mon Dec 17 21:47:27 2007)

我基本没有写过总结, 因为我不是很喜欢写总结.但最近连续2场比赛, 加上今天突然看到
这么多总结, 突然有种想写总结的冲动.

我们队从成立到现在一起做了很多场比赛, mmd从一开始就主张每次比赛只用一台机器, 无
论是各种网上比赛或者内部比赛.从开始到现在一直是这样, 我觉得这样非常好, 基本上来
说我感觉我们在做现场赛和平时做联系赛没有太大差别.我们受益匪浅.

相对来说我们队的状态是很平稳的, 一直是这样. 唯一出现的低潮就是2次亚洲区域期间,
尤其是在长春的比赛, 堪称建队历史上的最差一次比赛, 无论从过题数,名次还是最后的
心态(最后我们卡2题, 而且这两题的难度不大). 不过在之前南京金牌光辉的笼罩之下我们
还是很happy的… 其实南京我们做的也不好, 最后时候太乱了, 还有那个可恶的银色气球
和白色气球误导我们. 但结果很好的, 其他队伍做的更差, 于是我们才可以拿金牌, 想想
有些后怕~

最近的两次比赛我感觉和区域赛有很大区别, 最大的区别是题面, 区域赛读题面是个难点
也是个重点. 而这两次比赛题面的因素就弱了很多. 还有综合难度上也有一定的区别.

先说地大的比赛, 地大比赛题目相对简单, 具体题目已经忘了, 印象里在比赛中卡了2道题
目, mmd中途卡了一道题目, 我最后卡了一道题目. 最后也不知道为什么没有过.

以前的比赛我很少写代码, 只要是我能不写的基本上我都没写. 我是这样考虑的, 充分发
挥每个人的优势, 我代码弱就不写.mmd和feli代码写的多他们能写的比我更好. 所以我想
这样对队伍是最有利的.
但是我现在觉得这样并不好. 因为有这样几个原因:
1. 在比赛中如果一个人代码写多了身体会很疲惫. 影响状态.

2. 如果我看到的是简单题目, 这样的交流有些浪费时间.

3. 如果我看到的是难题, 交流是很麻烦的, 很难说清也不好听清.

4. 我似乎有些低估我的编码熟练度. 我虽然写题比较少但是一般的基本程序还是比较稳
的. 我也不知道为什么我会这样没有自信, 也许是跟mmd和feli一队的缘故吧

5. 其实脱机的思考是很重要的, 总在机器上写程序会出现问题的. 而我很少上机无形中剥
夺了他俩思考的时间.

6. 我和feli的配合有问题, feli看题很好, 在比赛一开始, 如果让feli去写题, 我只能去
看题. 哦, 说错了, 是看数据. 因为我看题基本不看题面, 直接看数据, 当然这样也是
无奈之举. 英语不行没有办法. 所以这段时间我觉的效率很低.

7. 每次比赛完, 我都觉的脑袋发蒙, 其实上机写较简单的程序是一种休息. 我总是在想题
目, 开始还好, 最后1个多小时就挺不住了.

所以我觉的如下可能会更好一些:
1. 比赛开始时, 我能写的简单题让我去写. feli一开始尽量不要写题, 去看题.

2. 自己觉得没问题的题目尽量自己去写, 减少不必要的交流.

3. 我负责的题目是杂题, 没有什么固定套路. 我们组队有些时间了, 基本上我知道什么样
的程序或程序段他们能够很稳的搞定.以后若非出现这种程序或程序段时, 尽量自己写
. 我去写简单题目, 一方面可以休息一下换换脑子, 一方面可以让mmd和feli去有更多
的时间思考以及看题.

华科的比赛, 我们做的很好, 基本上是组队来做的最好的比赛之一. 我觉的这和我的策略
的改变有些关系.
这次比赛我写了3道题目, 和feli合写了1道题目, 这在以前是从未出现过的. 一开始我看
到了J, 以前但凡这种简单题目, 我都是让feli写, 因为我觉得feli一定可以瞬秒, 而我写
就可能要花一些时间, 这就有点不必要了. 但这次是我去写了. 我写完题目后, feli立刻
跟我说了几道题目是组合数学相关. 这就避免了我看题. 提高了效率同时feli也多了看题
时间. 之后是C题, 同样的自己去写. 然后B题也是自己去写. 因为像BCJ这样的题目, 让谁
去写都是一样的. 而在这种情况下由思考人去写是最高效最明智的.之后是D题目, 有点失
误的是我没有过多的考虑范围只有15这个条件, 于是搞了一个挺恶心的公式, 看着就没有
写的欲望, 在这种情况下加上要马上赶回去参加Java考试, 我动摇了-_-!, 把feli拉来,
让他一起搞. 不过我和feli对这种合作编程很有经验, 基本上我们写的两部分之间是没有
很多耦合的.
我们队每次比赛的最大问题是出题慢, 时间多, 经常出现稳居相同题数的最后一名. 一直
不得其解. 现在回来想想也许就是以上的原因吧.

说一下我们队的情况吧.
1. mmd基本功非常扎实, 对于一些套路性的题目是千锤百炼, 这与他的个性稳重有很大关
系, 他就像一个重型坦克, 是战斗胜利的保证.

2. feli看题很快, 写程序也很快, 就像是战斗机, 在战斗伊始与乘胜追击阶段起到了至关
重要的作用.

3. 我比较喜欢把所有题目都当做新题来看待(这和mmd正好相反, 但相反也等于互补), 仔
细琢摸. 比较喜欢出数据, 找出陷阱.我想用排雷兵和导弹拦截系统能很恰当的形容我
的作用, 保证坦克和飞机的安全.

下面说一些我对比赛以及做题的一些看法(更多是给新人的建议):
1. 不要抱怨比赛中卡题. 一场比赛不卡题的概率和题目全切的概率相差无几. 卡题后的处
理方式更为关键.

2. 看题是非常关键的, 看题的同时应该看清楚这道题目是什么类型的, 让最适合的队友去
做. 看题和思考是同时进行的.

3. 平时练习, 题目最好独立去想后再交流, 不要忽视对从题面抽象出模型的能力的培养,
事实上这种能力在比赛中是非常重要的, 抽象出好的模型, 是转化模型以及进一步处理
的先决条件. 就比如说一道匹配题目, 知道是匹配题目的话基本都能做出来, 但从题目
中抽象出匹配模型就很难. 如果在做题时事先询问别人得知这是匹配题目, 那么很显然
就失去了对抽象模型能力进行训练的机会. 大家可能经常会发现有很多人在各个OJ做了
非常多的题目, 但比赛(尤其是现场赛)就总是成绩很差. 我猜想并不是巧合或者运气不
好. 而是因为平时做题养成了习惯, 总是在为做题而做题, 忽视了对抽象模型能力的锻
炼. 而现场赛都是新题, 办的好的现场赛甚至模型都是新的, 这样自然就应付不来了.
其实有些时候即使题目方法已知也可以强迫自己把这种方法忘掉, 从头开始思考, 思考
这种模型的本质与性质, 为什么这种做法是最优的, 为什么没有别的方法. 这其实是很
有趣的! 没准你能发现更好的方法比如贪心方法或者数学方法也说不定呢.

4. 我们队能出一些成绩跟我们的分工合作有很大关系, 我们各司其职又不乏讨论并且知识
覆盖面较全面. 当然这并不唯一的方式, 不过有兴趣的队伍可以借鉴一下.

下面我想说一下我们队需要改近的地方的看法(mmd,feli看一下):
1. mmd卡题对咱们的影响过大, 因为(1)mmd负责的题目是比赛经常出现的类型(2)我们队分
工非常严格,有些题目其他人不好去写的. 解决办法我觉得: 首先mmd在做题时最好先做
较容易的题目, 避免难题被卡从而一卡卡两题或更多的情况出现. 其次我和feli在平时
应做一些你负责的那部分题目. 这是因为你负责的那部分类型的题目是比赛的最爱. 出
现频率太高了.

2. 我应多分担一些上机任务, 这已经在上详细讨论过了.

3. feli继续努力, 你还年轻~

4. 模拟题目依然是个薄弱环节.

整体感觉我们队伍已经度过了磨合期. 队员之间的深入了解已经建立完成. 我们已经可以
打出配合来了.
坦克, 战斗机, 排雷兵已经可以进行部队的协同作战了!


–

※ 修改:·czogogo 於 Dec 17 21:51:25 2007 修改本文·[FROM: 222.20.240.*]
※ 来源:·珞珈山水BBS站 http://bbs.whu.edu.cn·[FROM: 222.20.240.*]

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

整体上来说，我们最后成绩虽然不差，但是比赛的遗憾还是非常多的，我相信我们在下一
站的吉林可以做的更好。

前面mmd已经把BMW队的比赛情况说过了，我补充一些。
一开始我从最后一题倒着看，发现I似乎是博弈，就给猫猫了。事实证明我是错的。我没有认真把题目分析清楚，只是大致看了一下题目意思，这个题目实质上是搜索。我的错误（还有题目本身描述错误）导致猫猫浪费了大量时间，减少了我们队的思维输出。
过掉3题以后，我们队都在做G。一开始我们考虑的方向错误了，mmd上去写了个搜索，TLE。然后我考虑了一个dfs算法，但是很快证明它不能得到最优解。在这里卡了一段时间后，我们转向变形的floyd算法，一开始没考虑清楚，交了个wa的。后来搞了个n^5的算法，TLE。mmd优化到n^4，还是TLE。估计是常数因子大了些。做这个题的失误主要在于：一开始错误的算法先入为主，浪费了时间；然后好不容易转型接近了正确算法，但是没有仔细考虑，导致设计的算法时效低下，连朴素的算法都不如；最后还没等我们第二次转换思维，比赛就结束了。
mmd在做G时，我和猫猫时不时讨论一下I，总觉得这题可以做，而事实上很难做。而且我们讨论的都是错误的方法，虽然有想过搜索后打表，但是没有去实现。最后都想的是错误的递推。

BMW存在的问题：
1。队员磨合不够。我们没有经常在一起训练和做比赛，每个人对其他两个人不是很了解。
2。比赛时没有决策者。猫猫是队长，比赛时没有对场上局势做出判断，在危急时刻（卡题了），没有提出解决方案。另外两个人没有意识到这一点而临时替代队长做出决策。导致队伍凝聚力不够。最后没人做B题，也是因为这个。
3。知识不足。体现在不知道G题在《算法导论》上有。lzx就知道。说明我们队没有人认真把《算法导论》读完。

BMW应该做的事：
1。平时多加训练，三人在一起做做比赛，当成正式比赛做，标程用手打，只用一台机。
2。注意比赛时的赛场情况分析和决策。
3。有空多看看书，尤其是经典书籍，要认真看。