前    言

“听说你最近在写一本关于算法竞赛入门的书？”朋友问我。

“是的。”我微笑道。

“这是怎样的一本书呢？”朋友很好奇。

“C语言、算法和题解。”我回答。

“什么？几样东西混着吗？”朋友很吃惊。

“对。”我笑了，“这是我思考许久后做出的决定。”

大学之前的我

12年前，当我翻开Sam A.Abolrous所著《C语言三日通》的第一页时，我不会想到自己会有机会编写一本讲解C语言的书籍。当时，我真的只花了3天就学完了这本书，并且自信满满：“我学会C语言啦！我要用它写出各种有趣、有用的程序！”但渐渐地，我认识到了：虽然浅显易懂，但书中的内容只是语言入门，离实际应用还有较大差距，就好比小学生学会造句以后还要下很大功夫才能写出像样的作文。

第二本对我影响很大的书是Sun公司的Peter van der Linden（PvdL）所著的《C程序设计奥秘》。作者称该书应该是每一个程序员“在C语言方面的第二本书”，因为“书中绝大部分内容、技巧和技术在其他任何书中都找不到”。原先我只是把自己当成是程序员，但在阅读的过程中，我开始渐渐了解到硬件设计者、编译程序开发者、操作系统编写者和标准制定者是怎么想的。继续的阅读增强了我的领悟：要学好C语言，绝非熟悉语法和语义这么简单。

后来，我自学了数据结构，懂得了编程处理数据的基本原则和方法，然后又学习了8086汇编语言，甚至曾没日没夜地用SoftICE调试《仙剑奇侠传》，并把学到的技巧运用到自己开发的游戏引擎中。再后来，我通过《电脑爱好者》杂志上的一则不起眼的广告了解到了全国信息学奥林匹克联赛（当时称为分区联赛，NOIP是后来的称谓）。“学了这么久编程，要不参加个比赛试试？”想到这里，我拉着学校里另外一个自学编程的同学，找老师带我们参加了1997年的联赛——在这之前，学校并不知道有这个比赛。凭借自己的数学功底和对计算机的认识，我在初赛（笔试）中获得全市第二的成绩，进入了复赛（上机）。可我的上机编程比赛的结果是“惨烈”的：第一题有一个测试点超过了整数的表示范围；第二题看漏了一个条件，一分都没得；第三题使用了穷举法，全部超时。考完之后我原以为能得满分的，结果却只得了100分中的20多分，名落孙山。

痛定思痛，我开始反思这个比赛。一个偶然的机会，我拿到了一本联赛培训教材。书上说，比赛的核心是算法（Algorithm），并且推荐使用Pascal语言，因为它适合描述算法。我从别人那里复制来了Turbo Pascal 7.0（那时网络并不发达），开始研究起来。由于先学的是C语言，所以我刚开始学习Pascal时感到有些不习惯：赋值不是“=”而是“:=”，简洁的花括号变成了累赘的begin和end，if之后要加个then，而且和else之间不允许写分号……但很快我就发现，这些都不是本质问题。在编写竞赛题的程序时，我并不会用到太多的高级语法。Pascal的语法虽然稍微啰嗦一点，但总体来说是很清晰的。就这样，我只花了不到一天时间就把语法习惯从C转到了Pascal，剩下的知识就是在不断编程中慢慢地学习和熟练——学习C语言的过程是痛苦的，但收益也是巨大的，“轻松转到Pascal”只是其中一个小小的例子。

我学习计算机，从一开始就不是为了参加竞赛，因此，在编写算法程序之余，我几乎总是使用熟悉的C语言，有时还会用点汇编，并没有觉得有何不妥。随着编写应用程序的经验逐渐丰富，我开始庆幸自己先学的是C语言——在我购买的各类技术书籍中，几乎全部使用的是C语言而不是Pascal语言，尽管偶尔有用Delphi的文章，但这种语言似乎除了构建漂亮的界面比较方便之外，并没有太多的“技术含量”。我始终保持着对C语言的熟悉，而事实证明这对我的职业生涯发挥了巨大的作用。

中学竞赛和教学

在大学里参加完ACM/ICPC世界总决赛之后（当时ACM/ICPC还可以用Pascal，现在已经不能用了），我再也没有用Pascal语言做过一件“正经事”（只是偶尔用它给一些只懂Pascal的孩子讲课）。后来我才知道，国际信息学奥林匹克系列竞赛是为数不多的几个允许使用Pascal语言的比赛之一。IT公司举办的商业比赛往往只允许用C/C++或Java、C#、Python等该公司使用较为频繁的语言（顺便说一句，C语言学好以后，读者便有了坚实的基础去学习上述其他语言），而在做一些以算法为核心的项目时，一般来说也不能用Pascal语言——你的算法程序必须和已有的系统集成，而这个“现有系统”很少是用Pascal写成的。为什么还有那么多中学生非要用这个“以后几乎再也用不着”的语言呢？

于是，我开始在中学竞赛中推广C语言。这并不是说我希望废除Pascal语言（事实上，我希望保留它），而是希望学生多一个选择，毕竟并不是每个参加信息学竞赛的学生都将走入IT界。但如果简单地因为“C语言难学难用，竞赛中还容易碰到诸多问题”就放弃学习C语言，我想是很遗憾的。

然而，推广的道路是曲折的。作为五大学科竞赛（数学、物理、化学、生物、信息学）中唯一一门高考中没有的“特殊竞赛”，学生、教师、家长所走的道路要比其他竞赛要艰辛得多。

第一，数理化竞赛中所学的知识，多是大学本科要学习的，只不过是提前灌输给高中生，但信息学竞赛中所涉及的很多东西甚至连本科都不会学到，即使学到了，也只是“简单了解即可”，和“满足竞赛的要求”有着天壤之别，这极大地增加了中学生学习算法和编程的难度。

第二，学科发展速度快。辅导信息学竞赛的教师常常有这样的感觉：必须不停地学习学习再学习，否则很容易跟不上“潮流”。事实上，学术上的研究成果常常在短短几年之内就体现在竞赛中。

第三，质量要求高。想法再伟大，如果无法在比赛时间之内把它变成实际可运行的程序，那么所有的心血都将是白费。数学竞赛中有可能在比赛结束前15分钟找到突破口并在交卷前一瞬间把解法写完——就算有漏洞，还有部分分数呢；但在信息学竞赛中，想到正确解法却5个小时都写不完程序的现象并不罕见。连程序都写不完当然就是0分，即使程序写完了，如果存在关键漏洞，往往还是0分。这不难理解——如果用这个程序控制人造卫星发射，难道当卫星爆炸之后你还可以向人炫耀说：“除了有一个加号被我粗心写成减号从而引起爆炸之外，这个卫星的发射程序几乎是完美的。”

在这样的情况下，让学生和教师放弃自己熟悉的Pascal语言，转向既难学又容易出错的C语言确实难为他们了——尤其是在C语言资料如此缺乏的情况下。等一下！C语言资料缺乏？难道市面上不是遍地都是C语言教材吗？对，C语言教材多，但和算法竞赛相结合的却几乎没有。不要以为语言入门以后就能轻易地写出算法程序（这甚至是很多IT工程师的误区），多数初学者都需要详细的代码才能透彻地理解算法，只了解算法原理和步骤是远远不够的。

大家都知道，编程需要大量的练习，只看只听是不够的。反过来，如果只是盲目练习，不看不听也是不明智的。本书的目标很明确——提供算法竞赛入门所必需的一切“看”的蓝本。有效的“听”要靠教师的辛勤劳动，而有效的“练”则要靠学生自己。当然，就算是最简单的“看”，也是大有学问的。不同的读者，往往能看到不同的深度。请把本书理解为“蓝本”。没有一本教材能不加修改而适用于各种年龄层次、不同学习习惯和悟性的学生，本书也不例外。我喜欢以人为本，因材施教，不推荐按照本书的内容和顺序填鸭式地教给学生。

内容安排

前面花了大量篇幅讨论了语言，但语言毕竟只是算法竞赛的工具——尽管这个工具非常重要，却不是核心。正如前面所讲，算法竞赛的核心是算法。我曾考虑过把C语言和算法分开讲解，一本书讲语言，另一本书讲基础算法。但后来我发现，其实二者难以分开。

首先，语言部分的内容选择很难。如果把C语言的方方面面全部讲到，篇幅肯定不短，而且和市面上已有的C语言教材基本上不存在区别；如果只是提纲挈领地讲解核心语法，并只举一些最为初级的例子，看完后读者将会处于我当初3天看完《C语言三日通》后的状态——以为自己都懂了，慢慢才发现自己学的都是“玩具”，真正关键、实用的东西全都不懂。

其次，算法的实现常常要求程序员对语言熟练掌握，而算法书往往对程序实现避而不谈。即使少数书籍给出了详细代码，但代码往往十分冗长，不适合用在算法竞赛中。更重要的是，这些书籍对算法实现中的小技巧和常见错误少有涉及，所有的经验教训都需要读者自己从头积累。换句话说，传统的语言书和算法之间存在着不小的鸿沟。

基于上述问题，本书采取一种语言和算法结合的方法，把内容分为如下3部分：

? 第1部分是语言篇（第1～4章），纯粹介绍语言，几乎不涉及算法，但逐步引入一些工程性的东西，如测试、断言、伪代码和迭代开发等。

? 第2部分是算法篇（第5～8章），在介绍算法的同时继续强化语言，补充了第1部分没有涉及的语言特性，如位运算、动态内存管理等，并延续第一部分的风格，在需要时引入更多的思想和技巧。学习完前两部分的读者应当可以完成相当数量的练习题。

? 第3部分是竞赛篇（第9～11章），涉及竞赛中常用的其他知识点和技巧。和前两部分相比，第3部分涉及的内容更加广泛，其中还包括一些难以理解的“学术内容”，但其实这些才是算法的精髓。

本书最后有一个附录，介绍开发环境和开发方法，虽然它们和语言、算法的关系都不大，却往往能极大地影响选手的成绩。另外，本书讲解过程中所涉及的程序源代码可登录网站http://www.tup.tsinghua.edu.cn/下载。

致谢

在真正动笔之前，我邀请了一些对本书有兴趣的朋友一起探讨本书的框架和内容，并请他们撰写了一定数量的文字，他们是赖笠源（语言技巧、字符串）、曹正（数学）、邓凯宁（递归、状态空间搜索）、汪堃（数据结构基础）、王文一（算法设计）、胡昊（动态规划）。尽管这些文字本身并没有在最终的书稿中出现，但我从他们的努力中获得了很多启发。北京大学的杨斐瞳完成了本书中大部分插图的绘制，清华大学的杨锐和林芝恒对本书进行了文字校对、题目整理等工作，在此一并感谢。

在本书构思和初稿写作阶段，很多在一线教学的老师给我提出了有益的意见和建议，他们是绵阳南山中学的叶诗富老师、绵阳中学的曾贵胜老师、成都七中的张君亮老师、成都石室中学的文仲友老师、成都大弯中学的李植武老师、温州中学的舒春平老师，以及我的母校——重庆外国语学校的官兵老师等。

本书的习题主要来自UVa在线评测系统，感谢Miguel Revilla教授和Carlos M. Casas Cuadrado的大力支持。

最后，要特别感谢清华大学出版社的朱英彪编辑，与他的合作非常轻松、愉快。没有他的建议和鼓励，或许我无法鼓起勇气把“算法艺术与信息学竞赛系列”以丛书的全新面貌展现给读者。

刘汝佳