新的blog站点：http://liulixiang.info (与IT有关，主要内容不是关于ACM/ICPC)

     如果有很重要的事情一定要与我交流，请联系 liulixiang {AT}liulixiang{DOT} info。

注：最近低潮一段，加上本人处于高原期——水平急待提高的阶段，所以一直郁闷，做题相当少，贴休息时看到的好文章充数……

在ICPC比赛中，个人 能力方面，如果粗略地分的话，大致可以分为算法能力、代码能力和查错 能力。那些大学才开始参加比赛的选手，写代码的基本功一般会比较扎实，主要瓶颈应该是算法能力。而对于OI转ICPC的选手来说，代码能力往往是最大的缺 陷。随着OI转ICPC的选手逐渐增多，代码能力的问题愈发暴露了出来。

一、如何定义代码能力

Comars曾经给代码能力作过一个比较准确的定义。2004年暑假时，Comars曾经说 过：他认为150行以内的题目，他的1Y率非常高，并且保持稳定；而当代码长度超过150行以后，1Y率就开始急速下降了。如果我们画出一条1Y率的曲线 的话，150行就是一个转折点。我们不妨认为，150行就是Comars当时的代码能力。一年以后，经过努力，Comars把代码能力提高到了250行。 不过，这已经是后话了。

二、如何提高代码能力

我一直觉得写程序和写文章是一个对很好的类比。

写文章需要先从宏观入手，构思文章的结构。写程序同样需要。一个好的结构，就是一个好的开始。一个好的开始，是成功的一半。

一篇好的文章需要各种句式和词藻的合理组合。体现到写程序上来，就是一些单句以及三五行的小结构的熟练使用。这些都是需要平时总结和积累的。

但凡文章写得好的人，一定看过很多别人写的文章。同样的道理，多看别人的程序，用心地去看，也可以提高自己的代码能力。

我鼓励队员去看别人写的程序，特别是像Comars这样的选手写的程序。从优秀的程序中，我 们可以体会别人良好的程序结构，同时也可以学到很多写程序的技巧——三五行的小技巧。在和Comars做队友的两年时间里，我通过看Comars的程序， 学会了很多小技巧。逐渐地，我觉得我写的某些程序已经和Comars有点相像了。

那么，如果身边没有Comars这样优秀的选手可以借鉴，该怎么办呢？其实没关系。任何一个程序都是可以看的。一个程序，就算写得再差，总还会有一两个闪光点，要想办法把它们找出来。另外，程序里写得不好的地方，也要一一找出来。

读程序，从某种角度来看，就像读史。好的历史是用来借鉴的；不好的历史则应该引以为戒。读程序也是一样，择其善者而从之，其不善者而改之。

三、谨慎地对待STL和SCL

STL - Standard Template Library。在ICPC的选手中，STL是相当受欢迎的。的确，如果STL用得好，程序可以精简很多。既提高了编程的速度，也提高了编程的准确性。

SCL - Standard Code Library，就是标准程序库。对很多选手来说，SCL可是命根子啊 :)

我觉得STL和SCL都不是坏东西，但是需要谨慎地使用。

我向来不主张队员一进队就开始用STL（虽然这种现象普遍存在 :(）。我认为，STL的作用是锦上添花，而不是雪中送炭。比方说，一个heap写得很熟练的队员，我觉得他可以偷偷懒，用一下STL。但是，那些不太会 写heap的队员，就不应该用STL里的heap。因为，他们真正应该做的是掌握写heap的能力——这才是最本质的代码能力。

学会用STL是件很爽的事情。但是须知有所得必有所失。如果过早地接触STL，会让你失去很多锻炼代码能力的机会。

至于SCL，我的主张是尽量不用。

不可否认，队里确实有一些人SCL用得很好。但是，我至今仍然没有见过一个SCL用得很好，同时有拥有很强的代码能力的人。同样是有所得必有所失，你平时习惯了去抄程序，必然少了很多自己构思程序的机会，从而影响代码能力的提高。

当然，我也不是完全反对去使用SCL，偶尔用一下也是可以的，例如在比赛中。但是，需要注意 的是，一定要用自己整理的SCL。我见过有人拿着一本别人整理的SCL，虽然内容很齐整，但是我没见他用对过。因为这本SCL不是他整理的，他自己都不知 道每个程序在使用的时候应该注意些什么，于是一用就错。

    我们学校的计算机学院从去年起开始组织学生参加世界上最具权威性的大学生程序设计竞赛——ACM/ICPC。从这学期开始，学院计划有组织地进行训练和讲 座，以帮助大家在有限的时间内尽可能多地提高自己的能力，这对有兴趣投入数据结构与算法研究的同学来说无疑是一件好事。但是，刚刚接触信息学领域的同学往 往存在很多困惑，不知道从何入手学习，在这篇文章里，我希望能将自己不多的经验与大家分享，希望对各位有所帮助。

一、语言是最重要的基本功

    无论侧重于什么方面，只要是通过计算机程序去最终实现的竞赛，语言都是大家要过的第一道关。亚洲赛区的比赛支持的语言包括C/C ++与JAVA。笔者首先说说JAVA，众所周知，作为面向对象的王牌语言，JAVA在大型工程的组织与安全性方面有着自己独特的优势，但是对于信息学比 赛的具体场合，JAVA则显得不那么合适，它对于输入输出流的操作相比于C++要繁杂很多，更为重要的是JAVA程序的运行速度要比C++慢10倍以上， 而竞赛中对于JAVA程序的运行时限却往往得不到同等比例的放宽，这无疑对算法设计提出了更高的要求，是相当不利的。其实，笔者并不主张大家在这种场合过 多地运用面向对象的程序设计思维，因为对于小程序来说这不旦需要花费更多的时间去编写代码，也会降低程序的执行效率。

    接着说C和C++。许多现在参加讲座的同学还在上大一，C的基础知识刚刚学完，还没有接触过C++，其实在赛场上使用纯C的选手 还是大有人在的，它们主要是看重了纯C在效率上的优势，所以这部分同学如果时间有限，并不需要急着去学习新的语言，只要提高了自己在算法设计上的造诣，纯 C一样能发挥巨大的威力。

    而C++相对于C，在输入输出流上的封装大大方便了我们的操作，同时降低了出错的可能性，并且能够很好地实现标准流与文件流的切换，方便了调试的工作。如果有些同学比较在意这点，可以尝试C和C++的混编，毕竟仅仅学习C++的流操作还是不花什么时间的。

    C++的 另一个支持来源于标准模版库（STL），库中提供的对于基本数据结构的统一接口操作和基本算法的实现可以缩减我们编写代码的长度，这可以节省一些时间。但 是，与此相对的，使用STL要在效率上做出一些牺牲，对于输入规模很大的题目，有时候必须放弃STL，这意味着我们不能存在“有了STL就可以不去管基本 算法的实现”的想法；另外，熟练和恰当地使用STL必须经过一定时间的积累，准确地了解各种操作的时间复杂度，切忌对STL中不熟悉的部分滥用，因为这其 中蕴涵着许多初学者不易发现的陷阱。

    通过以上的分析，我们可以看出仅就信息学竞赛而言，对语言的掌握并不要求十分全面，但是对于经常用到的部分，必须十分熟练，不允许有半点不清楚的地方，下面我举个真实的例子来说明这个道理——即使是一点很细微的语言障碍，都有可能酿成错误：

    在去年清华的赛区上，有一个队在做F题的时候使用了cout和printf的混合输出，由于一个带缓冲一个不带，所以输出一长就混乱了。只是因为当时judge team中负责F题的人眼睛尖，看出答案没错只是顺序不对（答案有一页多，是所有题目中最长的一个输出），又看了看程序发现只是输出问题就给了个Presentation error（格式错）。如果审题的人不是这样而是直接给一个 Wrong Answer，相信这个队是很难查到自己错在什么地方的。

    现在我们转入第二个方面的讨论，基础学科知识的积累。

二、以数学为主的基础知识十分重要

    虽 然被定性为程序设计竞赛，但是参赛选手所遇到的问题更多的是没有解决问题的思路，而不是有了思路却死活不能实现，这就是平时积累的基础知识不够。今年 World Final的总冠军是波兰华沙大学，其成员出自于数学系而非计算机系，这就是一个鲜活的例子。竞赛中对于基础学科的涉及主要集中于数学，此外对于物理、电 路等等也可能有一定应用，但是不多。因此，大一的同学也不必为自己还没学数据结构而感到不知从何入手提高，把数学捡起来吧！下面我来谈谈在竞赛中应用的数 学的主要分支。

    1、离散数学——作为计算机学科的基础，离散数学是竞赛中涉及最多的数学分支，其重中之重又在于图论和组合数学，尤其是图论。

    图 论之所以运用最多是因为它的变化最多，而且可以轻易地结合基本数据结构和许多算法的基本思想，较多用到的知识包括连通性判断、DFS和BFS，关节点和关 键路径、欧拉回路、最小生成树、最短路径、二部图匹配和网络流等等。虽然这部分的比重很大，但是往往也是竞赛中的难题所在，如果有初学者对于这部分的某些 具体内容暂时感到力不从心，也不必着急，可以慢慢积累。

    竞 赛中设计的组合计数问题大都需要用组合数学来解决，组合数学中的知识相比于图论要简单一些，很多知识对于小学上过奥校的同学来说已经十分熟悉，但是也有一 些部分需要先对代数结构中的群论有初步了解才能进行学习。组合数学在竞赛中很少以难题的形式出现，但是如果积累不够，任何一道这方面的题目却都有可能成为 难题。

    2、数论—— 以素数判断和同余为模型构造出来的题目往往需要较多的数论知识来解决，这部分在竞赛中的比重并不大，但只要来上一道，也足以使知识不足的人冥思苦想上一阵 时间。素数判断和同余最常见的是在以密码学为背景的题目中出现，在运用密码学常识确定大概的过程之后，核心算法往往要涉及数论的内容。

    3、计算几何——计算几何相比于其它部分来说是比较独立的，就是说它和其它的知识点很少有过多的结合，较常用到的部分包括——线段相交的判断、多边形面积的计算、内点外点的判断、凸包等等。计算几何的题目难度不会很大，但也永远不会成为最弱的题。

    4、线性代数——对线性代数的应用都是围绕矩阵展开的，一些表面上是模拟的题目往往可以借助于矩阵来找到更好的算法。

    5、概率论——竞赛是以黑箱来判卷的，这就是说你几乎不能动使用概率算法的念头，但这也并不是说概率就没有用。关于这一点，只有通过一定的练习才能体会。

    6、初等数学与解析几何——这主要就是中学的知识了，用的不多，但是至少比高等数学多，我觉得熟悉一下数学手册上的相关内容，至少要知道在哪儿能查到，还是必要的。

    7、高等数学——纯粹运用高等数学来解决的题目我接触的只有一道，但是一些题目的叙述背景往往需要和这部分有一定联系，掌握得牢固一些总归没有坏处。

    以上就是竞赛所涉及的数学领域，可以说范围是相当广的。我认识的许多人去搞信息学的竞赛就是为了逼着自己多学一点数学，因为数学是一切一切的基础。

三、数据结构与算法是真正的核心

    虽然数学十分十分重要，但是如果让三个只会数学的人参加比赛，我相信多数情况下会比三个只会数据结构与算法的人得到更为悲惨的结局。

    先 说说数据结构。掌握队列、堆栈和图的基本表达与操作是必需的，至于树，我个人觉得需要建树的问题有但是并不多。（但是树往往是很重要的分析工具）除此之 外，排序和查找并不需要对所有方式都能很熟练的掌握，但你必须保证自己对于各种情况都有一个在时间复杂度上满足最低要求的解决方案。说到时间复杂度，就又 该说说哈希表了，竞赛时对时间的限制远远多于对空间的限制，这要求大家尽快掌握“以空间换时间”的原则策略，能用哈希表来存储的数据一定不要到时候再去查 找，如果实在不能建哈希表，再看看能否建二叉查找树等等——这都是争取时间的策略，掌握这些技巧需要大家对数据结构尤其是算法复杂度有比较全面的理性和感 性认识。

    接 着说说算法。算法中最基本和常用的是搜索，主要是回溯和分支限界法的使用。这里要说的是，有些初学者在学习这些搜索基本算法是不太注意剪枝，这是十分不可 取的，因为所有搜索的题目给你的测试用例都不会有很大的规模，你往往察觉不出程序运行的时间问题，但是真正的测试数据一定能过滤出那些没有剪枝的算法。实 际上参赛选手基本上都会使用常用的搜索算法，题目的区分度往往就是建立在诸如剪枝之类的优化上了。

    常 用算法中的另一类是以“相似或相同子问题”为核心的，包括递推、递归、贪心法和动态规划。这其中比较难于掌握的就是动态规划，如何抽象出重复的子问题是很 多题目的难点所在，笔者建议初学者仔细理解图论中一些以动态规划为基本思想所建立起来的基本算法（比如Floyd-Warshall算法），并且多阅读一 些定理的证明，这虽然不能有什么直接的帮助，但是长期坚持就会对思维很有帮助。

四、团队配合

    通过以上的介绍大家也可以看出，信息学竞赛对于知识面覆盖的非常广，想凭一己之力全部消化这些东西实在是相当困难的，这就要求我们尽可能地发挥团队协作的精神。同组成员之间的熟练配合和默契的形成需要时间，具体的情况因成员的组成不同而不同，这里我就不再多说了。

五、练习、练习、再练习

    知 识的积累固然重要，但是信息学终究不是看出来的，而是练出来的，这是多少前人最深的一点体会，只有通过具体题目的分析和实践，才能真正掌握数学的使用和算 法的应用，并在不断的练习中增加编程经验和技巧，提高对时间复杂度的感性认识，优化时间的分配，加强团队的配合。总之，在这里光有纸上谈兵是绝对不行的， 必须要通过实战来锻炼自己。

    大 家一定要问，我们去哪里找题做，又如何检验程序是否正确呢？这大可不必担心，现在已经有了很多网上做题的站点，这些站点提供了大量的题库并支持在线判卷， 你只需要把程序源码提交上去，马上就可以知道自己的程序是否正确，运行所使用的时间以及消耗的内存等等状况。下面我给大家推荐几个站点，笔者不建议大家在 所有这些站点上做题，选择一个就可以了，因为每个站点的题都有一定的难易比例，系统地做一套题库可以使你对各种难度、各种类型的题都有所认识。

    1、Ural：

    Ural是中国学生对俄罗斯的Ural州立大学的简称，那里设立了一个Ural Online Problem Set，并且支持Online Judge。Ural的不少题目算法性和趣闻性都很强，得到了国内广大学生的厚爱。根据“信息学初学者之家”网站的统计，Ural的题目类型大概呈如下的分布：

    这和实际比赛中的题型分布也是大体相当的。有兴趣的朋友可以去看看。  

    2、UVA：

    UVA代表西班牙Valladolid大学(University de Valladolid)。该大学有一个那里设立了一个PROBLEM SET ARCHIVE with ONLINE JUDGE ，并且支持ONLINE JUDGE，形式和Ural大学的题库类似。不过和Ural不同的是，UVA题目多的多，而且比较杂，而且有些题目的测试数据比较刁钻。这使得刚到那里做题的朋友往往感觉到无所适从，要么难以找到合适的题目，要么Wrong Answer了很多次以后仍然不知道错在那里。如果说做Ural题目主要是为了训练算法，那么UVA题目可以训练全方位的基本功和一些必要的编程素质。UVA和许多世界知名大学联合办有同步网上比赛，因此那里强人无数，不过你先要使自己具有听懂他们在说什么的素质：）

    3、ZOJ：

    ZOJ是浙江大学建立的ONLINE JUDGE， 是中国大学建立的第一个同类站点，也是最好和人气最高的一个，笔者和许多班里的同学就是在这里练习。ZOJ虽然也定位为一个英文网站，但是这里的中国学生 比较多，因此让人觉得很亲切。这里目前有500多道题目，难易分配适中，且涵盖了各大洲的题目类型并配有索引，除此之外，ZOJ的JUDGE系统是几个网 站中表现得比较好的一个，很少出现Wrong Answer和Presentation error混淆的情况。这里每月也办有一次网上比赛，只要是注册的用户都可以参加。

后天校赛，赛前给自己做一下比赛培训……


+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

标  题: 比赛经验 
发信站: 天大求实BBS (Sun Sep  4 21:08:12 2005), 本站(bbs.tju.edu.cn) 

在天大，偶参加的比赛可以算是最多的了，说说比赛经验。 
可能现在说早了点，需要大家在正式比赛之前再看一遍。 
推荐此篇文章打印，与模板放在一起。 

1. 比赛中评测会有些慢，偶尔还会碰到隔10分钟以上才返回结果的情况，这段时间不能等

结果，必须开工其他题，如果WA，两道题同时做。交完每道题都要先打印。 
2. 比赛时发的饭不是让你当时就吃的，那是给你赛后吃的。基本上比赛中前几名的队都没

人吃，除非领先很多。 
3. 很多选手，尤其是第一次参加比赛的，到一个新环境，全当旅游了，参观的参观，找同

学的找同学，玩玩乐乐就把正事抛到脑后了，结果比赛自然没什么好成绩，这样的例子太

多了。所以到参赛地后要时刻不忘自己是来比赛的，好好休息、备战。 
4. 参赛前一天要睡10个小时以上，非常有助于保持比赛中的精力，很多时候比赛到3个多

小时队员就没劲了就是这个原因。前一天晚饭与当天早饭要吃好，理由同上，要知道下顿

饭得下午3点赛后才能吃。 
5. 到新环境，时刻注意远离疾病，感冒肠炎病不大，却是成绩的天敌。 
6. 英语不好，看不懂的，要勤查词典，懒一次就少一道题，远离奖牌。 
7. 可以紧张，杜绝慌张，慌张是出题的敌人，任何时候，如果发现自己或者队友出现慌张

的情况，提醒深呼吸。 
8. 照着纸敲代码和sample数据时不要敲错，特别注意文字信息。 
9. 第一道简单题交给队中最稳的人做，万一遇到麻烦也不要慌，如果有很多队都出了就更

不必着急了，它必定是简单题，必定是可以很快做出来的，晚几分钟也比罚掉20分好。另

外注意不要PE。 
10. 最后一小时是出题高峰，谁松懈，谁落后。最后一小时出一道是正常，出两道更好。

 

以上各条均有出处，每条都包含着以往教训，每条都可能浪费掉你一年的努力，不可小视

。 
以下各条有些来自于其他学校，有些是总结： 

11. 无论是否有人通过，所有题必须全读过，最好每道题都有两人以上读过，尽量杜绝讲

题现象。要完全弄清题意，正确的判断出题目的难易，不要想当然。 
12. 虽然讨论有助于出题，但是以往每赛区第一名基本都是各自为战，但是互相了解，觉

得一道题适合其他人做就转手。 
13. 保持头脑灵活，在正常方法不行时想想歪门邪道，比如换种不常见的特殊的数据结构

，加预处理，限时搜索等。效率是第一位的，如果觉得DP麻烦就用记忆化搜索，总之考虑

清楚后就要在最短时间出题。 
14. 竞赛中更需要比平时稳定，程序出来后要检查重点地方，尽量1Y。对于WA的题，不要

改一处就交，很可能还有错的地方，要稳，要懂得在压力下也要仔细。对WA的题测试时要

完整，必须每个点都测到，但不一定特别复杂。要考虑到测试的各种边界情况，比如矩阵

可能为1*1或1*n或m*1。 
15. 除非做出的人很多，否则最后考虑复杂几何题，精度造成的问题太多了。对double型

操作要小心判断大小、绝对值等情况。一般情况下不要用float型。 
16. 块复制要小心，检查相应的部分是否已经正确修改。 
17. 纸上写程序要尽量完整，每道题上机时间（包括输入、测试和调试）不要超过一小时

。程序出错如果一时无法排除就应该打印出来阅读而把机器让出来。 
18. 提交时注意题号，不要交错题。由于PC^2的界面，这种情况时有发生。 
19. 尽可能想到题目可以用到的数学的东西。 
20. 初始化必不可少。 
21. 数组行列下标不要弄反，位运算或字符串哪头是0和n不要搞反。 
22. 提交时记得把所有的调试信息都关掉。 
23. 实在迫不得已才可换人做题。 
24. 有想法后，写程序之前想好时空效率。比赛中一般不会出现时限30秒以上的题（国外

赛区除外），10秒及以上的一般不会超过3道。 
25. 竞赛机会每年只有一次，训练了很长时间，如果比赛中出现疏失，那么今后一年都会

后悔。对于不准备明年参赛的同学，更是要珍惜最后一次参赛机会。