下面为准备参加程序设计竞赛的本书读者们提供一些建议。 尽可能多解题 参加程序设计竞赛需要学习的内容非常多。以本书为例,全书有32章之多,但其内容还不能完全涵盖竞赛的所有主题。海量的学习内容很容易让参赛者陷入“尽可能多读教科书和其他资料来补充基础知识”的误区。其实,多了解一个算法,还不如提高利用已掌握的知识来解题的能力。因为,程序设计竞赛最终也只是通过每个参赛者编写出来的代码进行评判,而不管参赛者掌握多少知识,写不出解题的代码就等于没有解题的能力。经验和能力只能通过解答实际题目来慢慢培养,所以初学者最好先按照表1-1学习最重要的内容后,尽可能多解题以积累自己的经验并提高解题能力。 使用在线评分网站 参加程序设计竞赛的准备工作中还有一个重要环节,那就是评判自己编写的代码。在不知自己代码准确性的前提下,编写再多也无法提高能力。幸好互联网上有许多评分网站,这些网站收录了大量的竞赛真题和评分数据。只要提交解题源代码,网站会自动编译并执行,然后反馈执行的结果。下面是值得推荐的一些网站。 USACO Training Program(适合初级、中级人员,http://train.usaco.org/usacogate):为训练美国计算机奥林匹克大赛USACO参赛者而开设的网站,也对公众开放。收录的题目按照难易度进行排序后,与讲座内容一起提供给用户。评分系统被设计成非常友好的交互模式,例如会告知用户哪些输入使程序产生了错误等。这对于首次准备参加程序设计竞赛的人群非常有用。 TopCoder(适合中级人员,http://www.topcoder.com/tc):TopCoder网站的竞技台(competition arena)有一个练习往届真题并可评分的练习平台。不仅收录了大部分历届真题的讲座,还能查阅所有人提交的源代码。因只能在竞技台中编写程序,且调试相对困难,所以适用于中级人员。 ACM-ICPC Live Archive(适合中级人员,http://livearchve.onlinejudge.org/):收录了世界各国的ACM-ICPC地区赛题目和世界总决赛题目,并且为这些题目提供评分。可以在参加ACM-ICPC竞赛前利用往届真题测试一下自己的实力。 Project Euler(适合中级人员,http://projecteuler.net):收录了有关数学和算法的题目。有趣之处在于,参赛者在自己的电脑上执行程序后,仅提交结果就可获得评分。因此,解题者可以使用自己喜欢的任意一种程序设计语言来解决问题。 SPOJ Online Judge(适合高级人员,http://spoj.pl):波兰的在线评分网站,其特点是支持多种程序语言 ,而且收录了大量高水平题目。 尽可能多参加程序设计竞赛 比起独自练习,参加程序设计竞赛、与别人相互竞争更能提高自己的能力。即便参加的只是模拟考试,也会对提高自身实力有更大帮助。因此,建议各位尽可能多参加程序设计竞赛及模拟考试。请参阅1.2节的竞赛目录。 对团队练习的建议 ACM-ICPC与其他竞赛的不同之处在于,赛制为3人一组。个人赛中不曾费心的一些部分在团队形式的竞赛中变得重要起来,所以最好事先练习以下内容。 在纸上打草稿:三人同用一台计算机,所以不可能总由一个人控制键盘。先把答案的重要部分在纸上打草稿,然后迅速编写其解决代码,这样做会给整个比赛节约时间。因此,为便于快速编写代码,把要使用的数据结构、定义的函数名及功能、重要部分的伪代码 等事先打好草稿。 周密的任务安排:很多团队会让每个成员各自承担一个专门的部分,还有一些团队会让两个成员负责编写代码,另外一个人负责观察整个题目,并决定先解决问题的哪个部分、用什么方法解决。当然,这一点会根据成员的喜好以及相对实力而有所不同。 练习结对编程:遇到实现起来非常棘手的题目时,最好两人一起边浏览边编写解题代码。轮到自己操作计算机时,编写程序代码的同时介绍自己的想法,在一旁的人要帮其检查一下数组的大小等容易犯错的地方。 无调试器的调试:毕竟只有一台计算机,打开调试器会影响整个团队的速度。必须练就靠眼睛调试的本领。 利用屏幕分割减少打印等待时间:在ICPC打印源代码后,执行官员会传递到参赛者手中,这个时间可能会很长。多打印几次的话有时还会发生混淆情况。为了节约时间,可利用Vim之类的编辑器在屏幕一侧编写程序代码,在另一侧显示调试中的源代码。 准备团队记事本 ACM-ICPC与其他竞赛不同,允许携带参考资料进场。此时不是什么书都能带进去,而是只允许各队准备20页左右的打印资料,这些资料就称为团队记事本。因此,准备好团队记事本也是参赛所需的重要课题之一。这一项请参考下面几点建议。 提前准备:看起来是理所当然的事情,但最无法保证的就是提前准备。最理想的状态应该是边准备竞赛,边在解决问题时整理以后可能会用到的代码,并添加到团队记事本上。刚解完题的那一刻,不仅编写的代码通过了验证,而且对算法的理解也最深刻,所以这段时间最易于做整理工作。假如临近比赛才准备团队记事本,就会为该记录什么样的内容、怎样编写代码、怎样验证正确性等问题而变得手忙脚乱。 简单注释:对源代码的功能、执行前条件、执行后条件进行简单注释,这会对竞赛有很大帮助。如明确标注各函数的执行前条件和执行后条件 ,可以防止在比赛中出现重大失误。 按类的形态准备:使用源代码非常复杂的数据结构时,建议把数据按类定义。分类作业虽然录入时间长而繁琐,但可将代码模块化。即使制作团队记事本的和实际使用的并非同一人,也不用考虑初始化等繁琐的部分。 选择合适的字体:选择不适当的字体打印源代码,可能会跟特定字符产生混淆。例如,大写的英文O与数字0、小写的英文l与数字1、管道符|与大写英文I等等。查阅记事本再抄写源代码时,这种小失误会酿成致命的后果。因此,建议大家打印源代码时使用程序设计专用字体。