新的blog站点Qhttp://liulixiang.info (与IT有关Q主要内容不是关于ACM/ICPC)
如果有很重要的事情一定要与我交流Q请联系 liulixiang {AT}liulixiang{DOT} info?/p>
注:(x)最q低潮一D,加上本h处于高原期——水qx(chng)待提高的阶D,所以一直郁P做题相当,贴休息时看到的好文章充数……
在ICPC比赛中,个h 能力斚wQ如果粗略地分的话,大致可以分ؓ(f)法能力、代码能力和查错 能力。那些大学才开始参加比赛的选手Q写代码的基本功一般会(x)比较扎实Q主要瓶颈应该是法能力。而对于OI转ICPC的选手来说Q代码能力往往是最大的~? 陗随着OI转ICPC的选手逐渐增多Q代码能力的问题愈发暴露?jin)出来?/p>
一、如何定义代码能?/p>
Comars曄l?span style="background-color: yellow;">代码能力作过一个比较准的定义?004q暑假时QComars曄? q:(x)他认?50行以内的题目Q他?Y率非帔RQƈ且保持稳定;而当代码长度过150行以后,1Y率就开始急速下降了(jin)。如果我们画Z?Y率的曲线 的话Q?50行就是一个{折点。我们不妨认为,150行就是Comars当时的代码能力。一q以后,l过努力QComars把代码能力提高到?50行? 不过Q这已经是后话了(jin)?/p>
二、如何提高(sh)码能?/p>
我一直觉得写E序和写文章是一个对很好的类比?/p>
写文章需要先从宏观入手,构思文章的l构。写E序同样需要。一?span style="color: red;">好的l构Q就是一个好的开始。一个好的开始,是成功的一半?/p>
一好的文章需要各U句式和词藻的合理组合。体现到写程序上来,是一些单句以?qing)三五行的小l构的熟l?/span>。这些都是需要^时ȝ和积累的?/p>
但凡文章写得好的人,一定看q很多别人写的文章。同L(fng)道理Q?span style="color: red;">多看别h的程?/span>Q用?j)地ȝQ也可以提高自己的代码能力?/p>
我鼓励队员去看别人写的程序,特别是像Comarsq样的选手写的E序。从优秀的程序中Q我
们可以体?x)别好的E序l构Q同时也可以学到很多写程序的技巧——三五行的小技巧。在和Comars做队友的两年旉里,我通过看Comars的程序,
学会(x)?jin)很多小技巧。逐渐圎ͼ我觉得我写的某些E序已经和Comars有点相像?jin)?/p>
那么Q如果nҎ(gu)有Comarsq样优秀的选手可以借鉴Q该怎么办呢Q其实没关系。Q何一个程序都是可以看的。一个程序,q写得再差Q总还?sh)(x)有一两个闪光点,要想办法把它们找出来。另外,E序里写得不好的地方Q也要一一扑և来?/p>
ȝ序,从某U角度来看,像d?/span>好的历史是用来借鉴的;不好的历史则应该引以为戒。读E序也是一P择其善者而从之,其不善者而改之?/p>
三、}慎地对待STL和SCL STL - Standard Template Library。在ICPC的选手中,STL是相当受Ƣ迎的。的,如果STL用得好,E序可以_很多。既提高?sh)(jin)编E的速度Q也提高?sh)(jin)编E的准确性?/p>
SCL - Standard Code LibraryQ就是标准程序库。对很多选手来说QSCL可是命根子啊 :) 我觉得STL和SCL都不是坏东西Q但是需要}慎地使用?/p>
我向来不d队员?sh)q队开始用STLQ虽然这U现象普遍存?
:(Q。我认ؓ(f)Q?span style="color: red;">STL的作用是锦上添花 学会(x)用STL是g很爽的事情。但是须知有所得必有所失。如果过早地接触STLQ会(x)让你失去很多ȝ代码能力的机?x)?/p>
至于SCLQ我的主张是量不用?/span> 不可否认Q队里确实有一些hSCL用得很好。但是,我至今仍然没有见q一个SCL用得很好Q同时有拥有很强的代码能力的人。同h有所得必有所失,你^时习(fn)惯了(jin)LE序Q必然少?jin)很多自己构思程序的Z(x)Q从而媄(jing)响代码能力的提高?/p>
当然Q我也不是完全反对去使用SCLQ偶?dng)用一下也是可以的Q例如在比赛中。但是,需要注?
的是Q?span style="color: red;">一定要用自己整理的SCL
我们学校的计机学院从去qv开始组l学生参加世界上最h威性的大学生程序设计竞赛——ACM/ICPC。从q学期开始,学院计划有组l地q行训练和讲 座,以帮助大家在有限的时间内可能多地提高自q能力Q这Ҏ(gu)兴趣投入数据l构与算法研I的同学来说无疑是一件好事。但是,刚刚接触信息学领域的同学往 往存在很多困惑Q不知道从何入手学习(fn)Q在q篇文章里,我希望能自׃多的l验与大家分享,希望对各位有所帮助?/font>
一、语a是最重要的基本功
无论侧重于什么方面,只要是通过计算机程序去最l实现的竞赛Q语a都是大家要过的第一道关。亚z赛区的比赛支持的语a包括C/C ++与JAVA。笔者首先说说JAVAQ众所周知Q作为面向对象的王牌语言QJAVA在大型工E的l织与安全性方面有着自己独特的优势,但是对于信息学比 赛的具体场合QJAVA则显得不那么合适,它对于输入输出流的操作相比于C++要繁杂很多,更ؓ(f)重要的是JAVAE序的运行速度要比C++?0倍以上, 而竞赛中对于JAVAE序的运行时限却往往得不到同{比例的攑֮Q这无疑对算法设计提Z(jin)更高的要求,是相当不利的。其实,W者ƈ不主张大家在q种场合q? 多地q用面向对象的程序设计思维Q因为对于小E序来说q不旦需要花Ҏ(gu)多的旉ȝ写代码,也会(x)降低E序的执行效率?/strong>
接着说C和C++。许多现在参加讲座的同学q在上大一QC的基知识刚刚学完Q还没有接触qC++Q其实在赛场上用纯C的选手 q是大有人在的,它们主要是看重了(jin)UC在效率上的优势,所以这部分同学如果旉有限Qƈ不需要急着d?fn)新的语aQ只要提高(sh)(jin)自己在算法设计上的造诣Q纯 C一栯发挥巨大的威力?/strong>
而C++相对于CQ在输入输出上的封装大大方便了(jin)我们的操作,同时降低?jin)出错的可能性,q且能够很好地实现标准流与文件流的切换,方便?jin)调试的工作。如果有些同学比较在意这点,可以试C和C++的~,毕竟仅仅学习(fn)C++的流操作q是不花什么时间的?/strong>
C++? 另一个支持来源于标准模版库(STLQ,库中提供的对于基本数据结构的l一接口操作和基本算法的实现可以~减我们~写代码的长度,q可以节省一些时间。但 是,与此相对的,使用STL要在效率上做Z些牺Ԍ对于输入规模很大的题目,有时候必L弃STLQ这意味着我们不能存在“有了(jin)STL可以不ȝ基本 法的实?#8221;的想法;另外Q熟l和恰当C用STL必须l过一定时间的U篏Q准地?jin)解各种操作的时间复杂度Q切忌对STL中不熟?zhn)的部分滥用,因?f)q其 中蕴늝许多初学者不易发现的陷阱?/strong>
通过以上的分析,我们可以看出仅就信息学竞赛而言Q对语言的掌握ƈ不要求十分全面,但是对于l常用到的部分,必须十分熟练Q不允许有半点不清楚的地方,下面我D个真实的例子来说明这个道理——即使是一点很l微的语a障碍Q都有可能酿成错误:(x)
在去q清华的赛区上,有一个队在做F题的时候用了(jin)cout和printf的合输出,׃一个带~冲一个不带,所以输Z长就混ؕ?jin)。只是因为当时judge team中负责F题的人眼睛尖Q看出答案没错只是顺序不对({案有一多Q是所有题目中最长的一个输出)(j)Q又看了(jin)看程序发现只是输出问题就l了(jin)个Presentation errorQ格式错Q。如果审题的Z是这栯(g)是直接l一?/strong> Wrong AnswerQ相信这个队是很难查到自己错在什么地方的?/strong>
现在我们转入W二个方面的讨论Q基学科知识的积累?/strong>
二、以数学Z的基知识十分重要
? 然被定性ؓ(f)E序设计竞赛Q但是参赛选手所遇到的问题更多的是没有解决问题的思\Q而不是有?jin)思\却死zM能实玎ͼq就是^时积累的基础知识不够。今q? World Final的d军是波兰华沙大学Q其成员?gu)于数学系而非计算机系Q这是一个鲜zȝ例子。竞赛中对于基础学科的涉?qing)主要集中于数学Q此外对于物理、电(sh) 路等{也可能有一定应用,但是不多。因此,大一的同学也不必p没学数据l构而感C知从何入手提高,把数学捡h吧!下面我来谈谈在竞赛中应用的数 学的主要分支?/strong>
1、离散数?/strong>——作机学科的基Q离散数学是竞赛中涉?qing)最多的数学分支Q其重中之重又在于图论和l合数学Q尤其是图论?/strong>
? Z所以运用最多是因ؓ(f)它的变化最多,而且可以L地结合基本数据结构和许多法的基本思想Q较多用到的知识包括q通性判断、DFS和BFSQ关节点和关 键\径、欧拉回路、最生成树(wi)、最短\径、二部图匚w和网l流{等。虽然这部分的比重很大,但是往往也是竞赛中的N所在,如果有初学者对于这部分的某? 具体内容暂时感到力不从心(j)Q也不必着急,可以慢慢U篏?/strong>
? 赛中设计的组合计数问题大都需要用l合数学来解冻Il合数学中的知识相比于图单一些,很多知识对于学上过奥校的同学来说已l十分熟(zhn),但是也有一 些部分需要先对代数结构中的群论有初步?jin)解才能q行学习(fn)。组合数学在竞赛中很以N的Ş式出玎ͼ但是如果U篏不够QQ何一道这斚w的题目却都有可能成ؓ(f) N?/strong>
2、数?/strong>—? 以素数判断和同余为模型构造出来的题目往往需要较多的数论知识来解冻Iq部分在竞赛中的比重q不大,但只要来上一道,也以知识不的h冥思苦想上一? 旉。素数判断和同余最常见的是在以密码学ؓ(f)背景的题目中出现Q在q用密码学常识确定大概的q程之后Q核?j)算法往往要涉?qing)数论的内容?/strong>
3、计几?/strong>——计几何相比于其它部分来说是比较独立的Q就是说它和其它的知识点很少有过多的l合Q较常用到的部分包括——线D늛交的判断、多边Ş面积的计、内点外点的判断、凸包等{。计几何的题目隑ֺ不会(x)很大Q但也永q不?x)成为最q题?/strong>
4、线性代?/strong>——对U性代数的应用都是围绕矩阵展开的,一些表面上是模拟的题目往往可以借助于矩阉|扑ֈ更好的算法?/strong>
5、概率论——竞赛是以黑来判卷的,q就是说你几乎不能动使用概率法的念_(d)但这也ƈ不是说概率就没有用。关于这一点,只有通过一定的l习(fn)才能体会(x)?/strong>
6、初{数学与解析几何——这主要是中学的知识了(jin)Q用的不多,但是臛_比高{数学多Q我觉得熟?zhn)一下数学手册上的相兛_容,臛_要知道在哪儿能查刎ͼq是必要的?/strong>
7、高{数?/strong>——纯_运用高{数学来解决的题目我接触的只有一道,但是一些题目的叙述背景往往需要和q部分有一定联p,掌握得牢Z些d没有坏处?/strong>
以上是竞赛所涉及(qing)的数学领域,可以说范围是相当q的。我认识的许多hL信息学的竞赛是Z(jin)逼着自己多学一Ҏ(gu)学,因ؓ(f)数学是一切一切的基础?/strong>
三、数据结构与法是真正的核心(j)
虽然数学十分十分重要Q但是如果让三个只会(x)数学的h参加比赛Q我怿多数情况下会(x)比三个只?x)数据结构与法的h得到更ؓ(f)(zhn)惨的结局?/strong>
? 说说数据l构。掌握队列、堆栈和囄基本表达与操作是必需的,至于?wi),我个得需要徏?wi)的问题有但是ƈ不多。(但是?wi)往往是很重要的分析工P(j)除此? 外,排序和查扑ƈ不需要对所有方式都能很熟练的掌握,但你必须保证自己对于各种情况都有一个在旉复杂度上满最低要求的解决Ҏ(gu)。说到时间复杂度Q就? 该说说哈希表?jin),竞赛时对旉的限制远q多于对I间的限Ӟq要求大家尽快掌?#8220;以空间换旉”的原则策略,能用哈希表来存储的数据一定不要到时候再L 找,如果实在不能建哈希表Q再看看能否Z叉查找树(wi){等——这都是争取旉的策略,掌握q些技巧需要大家对数据l构其是算法复杂度有比较全面的理性和? 性认识?/strong>
? 着说说法。算法中最基本和常用的是搜索,主要是回溯和分支限界法的使用。这里要说的是,有些初学者在学习(fn)q些搜烦(ch)基本法是不太注意剪枝,q是十分不可 取的Q因为所有搜索的题目l你的测试用例都不会(x)有很大的规模Q你往往察觉不出E序q行的时间问题,但是真正的测试数据一定能qo(h)出那些没有剪枝的法。实 际上参赛选手基本上都?x)用常用的搜?ch)法Q题目的区分度往往是建立在诸如剪枝之cȝ优化上了(jin)?/strong>
? 用算法中的另一cL?#8220;怼或相同子问题”为核?j)的Q包括递推、递归、贪?j)法和动态规划。这其中比较难于掌握的就是动态规划,如何抽象出重复的子问题是? 多题目的隄所在,W者徏议初学者仔l理解图Z一些以动态规划ؓ(f)基本思想所建立h的基本算法(比如Floyd-Warshall法Q,q且多阅M 些定理的证明Q这虽然不能有什么直接的帮助Q但是长期坚持就?x)对思维很有帮助?/strong>
四、团队配?/font>
通过以上的介l大家也可以看出Q信息学竞赛对于知识面覆盖的非常q,惛_一׃力全部消化这些东西实在是相当困难的,q就要求我们可能地发挥团队协作的精。同l成员(sh)间的熟练配合和默契的形成需要时_(d)具体的情况因成员的组成不同而不同,q里我就不再多说?jin)?/strong>
五、练?fn)、练?fn)、再l习(fn)
? 识的U篏固然重要Q但是信息学l究不是看出来的Q而是l出来的Q这是多前人最q一点体?x),只有通过具体题目的分析和实践Q才能真正掌握数学的使用和算 法的应用Qƈ在不断的l习(fn)中增加编E经验和技巧,提高Ҏ(gu)间复杂度的感性认识,优化旉的分配,加强团队的配合。MQ在q里光有U怸谈兵是绝对不行的Q? 必须要通过实战来锻D己?/strong>
? 家一定要问,我们d里找题做Q又如何(g)验程序是否正呢Q这大可不必担心(j)Q现在已l有?jin)很多网上做题的站点Q这些站Ҏ(gu)供了(jin)大量的题库ƈ支持在线判卷Q? 你只需要把E序源码提交上去Q马上就可以知道自己的程序是否正,q行所使用的时间以?qing)消耗的内存{等状况。下面我l大家推荐几个站点,W者不大家? 所有这些站点上做题Q选择一个就可以?jin),因?f)每个站点的题都有一定的难易比例Q系l地做一套题库可以你对各种隑ֺ、各U类型的题都有所认识?/strong>
1、UralQ?/strong>
Ural是中国学生对俄罗斯的Ural州立大学的简Uͼ那里讄?jin)一?/strong>Ural Online Problem SetQƈ且支持Online Judge。Ural的不题目算法性和闻性都很强Q得C(jin)国内q大学生的厚爱。根?#8220;信息学初学者之?#8221;|站的统计,Ural的题目类型大概呈如下的分布:(x)
题型 |
搜烦(ch) |
动?/font> 规划 |
贪心(j) |
构?/font> |
图论 |
计算 几何 |
U数?/font> 问题 |
数据 l构 |
其它 |
所?/font> 比例 |
U?0% |
U?5% |
U?% |
U?% |
U?0% |
U?% |
U?0% |
U?% |
U?5% |
2、UVAQ?/strong>
UVA代表西班牙Valladolid大学(University de Valladolid)。该大学有一个那里设立了(jin)一?/strong>PROBLEM SET ARCHIVE with ONLINE JUDGE Qƈ且支持ONLINE JUDGEQŞ式和Ural大学的题库类伹{不q和Ural不同的是QUVA题目多的多,而且比较杂,而且有些题目的测试数据比较刁钅R这使得刚到那里做题的朋友往往感觉到无所适从Q要么难以找到合适的题目Q要么Wrong Answer?jin)很多次以后仍然不知道错在那里。如果说做Ural题目主要是ؓ(f)?jin)训l算法,那么UVA题目可以训练全方位的基本功和一些必要的~程素质。UVA和许多世界知名大学联合办有同步网上比赛,因此那里Zh无数Q不q你先要使自己具有听懂他们在说什么的素质Q)(j)
3、ZOJQ?/strong>
ZOJ是浙江大学徏立的ONLINE JUDGEQ? 是中国大学徏立的W一个同cȝ点,也是最好和人气最高的一个,W者和许多班里的同学就是在q里l习(fn)。ZOJ虽然也定位ؓ(f)一个英文网站,但是q里的中国学? 比较多,因此让h觉得很亲切。这里目前有500多道题目Q难易分配适中Q且늛?jin)各大洲的题目类型ƈ配有索引Q除此之外,ZOJ的JUDGEpȝ是几个网 站中表现得比较好的一个,很少出现Wrong Answer和Presentation errorh的情c(din)这里每月也办有一ơ网上比赛,只要是注册的用户都可以参加?/strong>
后天校赛Q赛前给自己做一下比赛培?#8230;…
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
? ? 比赛l验
发信? 天大求实BBS (Sun Sep 4 21:08:12 2005), 本站(bbs.tju.edu.cn)
在天大,偶参加的比赛可以是最多的?jin),说说比赛l验?
可能现在说早?jin)点Q需要大家在正式比赛之前再看一遍?
推荐此篇文章打印Q与模板攑֜一赗?
1. 比赛中评会(x)有些慢,偶尔q(sh)(x)到?0分钟以上才返回结果的情况Q这D|间不能等
l果Q?span style="color: red;">必须开工其他题Q如果WAQ两道题同时做?span style="color: red;">交完每道题都要先打印?
2. 比赛时发?span style="color: red;">饭不是让你当时就吃的Q那是给你赛后吃的。基本上比赛中前几名的队都没
人吃Q除非领先很多?
3. 很多选手Q尤其是W一ơ参加比赛的Q到一个新环境Q全当旅怺(jin)Q参观的参观Q找?br>
学的扑学,玩玩乐乐把正事抛到脑后?jin),l果比赛自然没什么好成WQ这L(fng)例子?br>
多了(jin)。所以到参赛地后要时M忘自己是来比赛的Q好好休息、备战?
4. 参赛前一天要?0个小时以?/span>Q非常有助于保持比赛中的_֊Q很多时候比赛到3个多
时队员没劲了(jin)是q个原因?span style="color: red;">前一天晚饭与当天早饭要吃?/span>Q理由同上,要知道下?br>
饭得下午3点赛后才能吃?
5. 到新环境Q时L意远ȝ病,感冒肠炎病不大,却是成W的天敌?
6. p不好Q看不懂的,要勤查词?/span>Q懒一ơ就一道题Q远d牌?
7. 可以紧张Q?span style="color: red;">杜绝慌张Q慌张是出题的敌人,M时候,如果发现自己或者队友出现慌?/span>
的情况,提醒深呼吸?
8. 照着U敲代码和sample数据时不要敲错,特别注意文字信息?
9. W一道简单题?sh)给队中最E的人做Q万一遇到ȝ(ch)也不要慌Q如果有很多队都Z(jin)更
不必着急了(jin)Q它必定是简单题Q必定是可以很快做出来的Q?span style="color: red;">晚几分钟也比|掉20分好?/span>?br>
外注意不要PE?
10. 最后一时是出题高峎ͼ谁松懈,谁落后。最后一时Z道是正常Q出两道更好?br>
以上各条均有出处Q每条都包含着以往教训Q每条都可能费掉你一q的努力Q不可小?br>
?
以下各条有些来自于其他学校,有些是ȝQ?
11. 无论是否有h通过Q?span style="color: red;">所有题必须全读q,最好每道题都有两h以上读过Q?/span>量杜绝?br>
题现象。要完全弄清题意Q正的判断出题目的难易Q不要想当然?
12. 虽然讨论有助于出题,但是以往每赛区第一名基本都是各自ؓ(f)战,但是互相?jin)解Q觉
得一道题适合其他人做p{手?
13. 保持头脑灉|Q在正常Ҏ(gu)不行时想x(chng)门邪道,比如换种不常见的Ҏ(gu)的数据结?br>
Q加预处理,限时搜烦(ch){?/span>效率是第一位的Q如果觉得DPȝ(ch)q记忆化搜索,M考虑
清楚后就要在最短时间出题?
14. 竞赛中更需要比qx(chng)E_Q程序出来后要检查重点地方,量1Y?/span>对于WA的题Q不?br>
改一处就交,很可能还有错的地方,要稳Q要懂得在压力下也要仔细?/span>对WA的题?gu)试时?br>
完整Q必L个点都测刎ͼ但不一定特别复杂。要考虑到测试的各种边界情况Q比如矩?br>
可能?*1?*n或m*1?
15. 除非做出的h很多Q否则最后考虑复杂几何题,_ֺ造成的问题太多了(jin)。对double?br>
操作要小?j)判断大、绝对值等情况。一般情况下不要用float型?
16. 块复制要心(j)Q检查相应的部分是否已经正确修改?
17. U怸写程序要量完整Q每道题?sh)机旉Q包括输入、测试和调试Q不要超q一时
?span style="color: red;">E序出错如果一时无法排除就应该打印出来阅读而把机器让出来?/span>
18. 提交时注意题P不要交错题?/span>׃PC^2的界面,q种情况时有发生?
19. 可能想到题目可以用到的数学的东ѝ?
20. 初始化必不可?/span>
21. 数组行列下标不要弄反Q位q算或字W串哪头?和n不要搞反?
22. 提交时记得把所有的调试信息都关掉?
23. 实在q不得已才可换h做题?/span>
24. 有想法后Q?span style="color: red;">写程序之前想好时I效?/span>。比赛中一般不?x)出现时?0U以上的题(国外
赛区除外Q,10U及(qing)以上的一般不?x)超q?道?
25. 竞赛Z(x)每年只有一ơ,训练?jin)很长时_(d)如果比赛中出现疏失,那么今后一q都?br>
后?zhn)。对于不准备明年参赛的同学,更是要珍惜最后一ơ参赛机?x)?br>