前 言

“请问《算法竞赛入门经典（第2版）》有没有配套题解啊？很多练习题好难，真希望能有一本简单、易懂的参考解答！”经常有读者追问类似的问题。笔者在进行训练学习时，也经常会有这样的想法。虽然很多题目可以在网上搜到对应题解，但这些题解多数是解题者为方便自己做题而随手记录的，解答过程未必严密、系统，语言表达上也比较随意，初学者理解起来就有一定的难度。

多年之前，笔者曾有幸参与了《算法竞赛入门经典—训练指南》一书的编写工作，收获颇大。也正是那次，我深刻感受到了自己在算法领域的不足，以及思维能力的亟待提升。私下里，我曾和刘汝佳老师商量，就以《算法竞赛入门经典（第2版）》的习题为训练题目，强迫自己在解出每道题之后，再对自己的思路进行严密、仔细的剖析，通过大量的训练，使自己得到一次系统的训练和提升。这次训练，使我记了厚厚一大本的笔记，而这本笔记就是本书的缘起。

希望本书能帮助更多跟我一样迫切需要提升算法思维能力的初学者！

算法有什么用

我大学学的是机械专业，但由于对数学非常热爱，加之毕业后发现软件行业貌似比较好“混”，且工资待遇比其他行业高些，所以就进入了开发领域。经过一段时间的工作后，我发现自己经常会遇到以下一些问题： 

? 程序稍微复杂一些，代码就会写的很乱。 

? 程序出了问题，不知道该如何调试，只会到处修改，然后再看效果。 

? 用户需求稍作改变，就想骂街。 

? 特别重要的一点是，如果你想跳到外企去工作，面试时肯定会让你编一些很难的算法程序。

后来，我进入到了微软上海全球技术支持中心做外包技术支持，接触到了许多严谨、求是、好学的工程师前辈。从他们身上，我学到了一些非常有效的解决问题的思路，以及那种“活到老学到老”的人生态度。

我逐渐明白：程序是要设计的。为了设计得清晰，需要学习数据结构、操作系统原理等非常多的基础知识，而这些体系本质上是前辈人思维方法的结晶。

另外，令很多程序员头疼的调试过程，给我印象最深的是一句话：调试的本质实际上就是在定位。大多数时候，调试的过程（并发程序的调试可能就更复杂些）其实就是一个二分查找：假如有 100行程序结果不对，就可以在第50行看看结果是否符合预期，如果OK，说明问题出在后50行，否则前50行一定有问题。如此递归下去，很快就能精准定位到有问题的代码。了解二分查找的朋友都知道，这个算法复杂度是O(logn)。

用C#开发服务端程序时，我经常会遇到内存问题，需要对垃圾收集（GC）的过程进行分析调试。深入学习之后我发现，其实GC模型的本质就是有向图。抱着这个思路再来分析解决内存问题，思路瞬间清晰了很多。

这样的例子还有很多。

在不断解决各类问题的过程中，我逐渐明白了—算法在本质上是诸多计算机学术以及实践领域积累下来的分析解决各种问题的思维方法。它不是象牙塔内的纯学术研究，更不是一堆仅能用来解决特定领域性能问题的高精尖技术。这个行业的技术人员，本质上正是以这些思维方法为武器，高效解决着不同行业领域不断涌现出的各类纷繁问题和挑战。

说到这里，我想到其他很多行业：京剧艺人每天早上要练嗓子，相声演员每天要练贯口，军人在战斗之余要进行大量训练，中医在繁忙之余要天天钻研《伤寒论》《黄帝内经》等经典……类似这样，需要认真对待并把基本功训练作为生活一部分的行业还有很多。对于笔者来说，算法思维就是IT相关行业的技术人员需要用同样态度持续不断进行训练的一项基本功。

所以，就有了这些年的学习过程，以及以本书作为省察的一个小小总结。

内容安排

本书内容分为以下5章。

第1章是各种编程训练技巧以及C++11语法特性的简单介绍。

第2章精选了一部分《算法竞赛入门经典（第2版）》的习题进行分析、解答，主要是读者反映较多的第3~11章的课后习题部分。

第3章是ACM/ICPC比赛真题分类选解，挑选了近些年ACM/ICPC比赛中较有价值的题目进行分析并解答。

第4章是比赛真题选译，整理并翻译了近几年来各大区域比赛中笔者认为值得学习训练的比赛真题。

第5章是比赛难题选译，内容类似于第4章，只是题目难度更上一个台阶。

关于C++语言的使用

本书在解答各类算法题目时，使用C++作为主要的编程语言，尽量使用STL中提供的现成数据结构，同时也尽量使用C++11的新特性。因为笔者认为，算法训练最关键的是训练解决问题的思维能力，包括抽象能力、分析能力、调试能力等，应该充分利用语言提供的语法特性使得程序更加简洁清晰，从而使解题者更专注于问题的抽象和分析本身。

关于题目代码

本书中的所有题目，笔者都是先完成代码并在线提交AC（Accepted），然后才开始编写对应的分析题解。有些需要附上代码的题目，笔者会尽可能把代码的主要部分（去掉模板代码以及C++的namespace导入部分）附在题目后面，但由于篇幅原因，实在无法全部放入书中。还有些题目，虽然已经在线提交AC，但由于无法严格证明题目的正确性，也没有在书中提供题解。

书中的所有代码，读者朋友们如有需要，可以通过如下网站进行下载：https://github.com/sukhoeing/aoapc-bac2nd-keys。

勘误和支持

虽然笔者已竭尽全力，力求减少纰漏，但由于水平有限，书中难免仍存在错漏之处，恳请广大读者朋友们批评指正。欢迎您将学习过程中遇到的各类问题、您对本书的想法以及宝贵意见，通过本书网站的issues部分一起交流。

致谢

首先要感谢刘汝佳老师，是他把我带进了算法艺术的大门，并且在工作极其繁忙的情况下一直耐心地指导着我的算法学习。

从小父亲就告诉我，对的事情一定要坚持。这句话支撑着我渡过了很多艰难的日子。同时，也要感谢我的太太梁明珠和女儿陈婉之。这三年来，我牺牲了大量本该陪伴他们的时间，投入到了本书的创作中。没有你们的支持和包容，我不可能完成这本书。

还要感谢微软工作期间经常指导我的老师张羿，从他那里，我第一次知道了世界上还有ACM/ICPC这回事。在如何做好一个程序员这件事上，他给了我非常多有价值的指导和帮助。

本书初稿完成之后，许多同学和朋友踊跃参与到了本书的试读中，并且提出了许多有价值的意见和反馈，他们的名字（排名不分先后）是陈飞、崔晨、杨恒杰、林永康、陈坤泽、孙博昊等。另外，书中的部分题目也参考了许多网友的在线题解，在此一并表示感谢。

最后要感谢清华大学出版社的贾小红编辑，用极大的耐心容忍着我把交稿时间一拖再拖，希望本书不会让您失望。

陈锋