算法竞赛入门经典——训练指南(大量经典算法的详细讲解与完整代码)

    书籍
    计算机书籍
《算法竞赛入门经典——训练指南》是《算法竞赛入门经典》的重要补充，旨在补充原书中没有涉及或者讲解得不够详细的内容，从而构建一个较完整的知识体系，并且用大量有针对性的题目，让抽象复杂的算法和数学具体化、实用化。

《算法竞赛入门经典——训练指南》共6章，分别为算法设计基础、数学基础、实用数据结构、几何问题、图论算法与模型和更多算法专题，全书通过近200道例题深入浅出地介绍了上述领域的各个知识点、经典思维方式以及程序实现的常见方法和技巧，并在章末和附录中给出了丰富的分类习题，供读者查漏补缺和强化学习效果。

《算法竞赛入门经典——训练指南》题目多选自近年来ACM/ICPC区域赛和总决赛真题，内容全面，信息量大，覆盖了常见算法竞赛中的大多数细分知识点。书中还给出了所有重要的经典算法的完整程序，以及重要例题的核心代码，既适合选手自学，也方便教练组织学习和训练。

刘汝佳，1982年12月生，高中毕业于重庆市外国语学校。 2000年3月获得NOI2000全国青少年信息学奥林匹克竞赛一等奖第四名，进入国家集训队，并因此保送到清华大学计算机科学与技术系。大一时获2001年ACM/ICPC国际大学生程序设计竞赛亚洲-上海赛区冠军和2002年世界总决赛银牌（世界第四），2005年获学士学位，2008年获硕士学位。 学生时代曾为中国计算机学会NOI科学委员会学生委员，担任IOI2002-2008中国国家队教练，并为NOI系列比赛命题十余道。现为NOI竞赛委员会委员，并在NOI 25周年时获得中国计算机学会颁发的“特别贡献奖”。2004年至今共为ACM/ICPC亚洲赛区命题二十余道，担任6次裁判和2次命题总监，并应邀参加IOI和ACM/ICPC相关国际研讨会，发表论文两篇。 2004年初作为第一作者出版专著《算法艺术与信息学竞赛》，2009年出版译著《编程挑战》，2009年出版《算法竞赛入门经典》。
多年来在全国二十余个城市进行中学生竞赛培训工作，为北京、上海、吉隆坡等地的著名高校授课与宣讲，并多次与TopCoder、百度和网易有道等知名企业合作举办比赛，让更多的IT人才获得展示自我的平台。
陈锋，1982年9月生。毕业于华北水利水电学院机械设计专业。曾就职于微软全球技术支持中心，负责.net虚拟机以及Visual Studio开发技术支持。后进入金融IT行业，专注于银行网点平台的产品研发，曾分别负责基于.net和Eclipse的两代网点平台产品的开发以及架构设计。现就职于北京宇信易诚科技，任前端产品技术经理及架构师。

《算法竞赛入门经典——训练指南》
第1章 算法设计基础 1
1.1 思维的体操 1
1.2 问题求解常见策略 15
1.3 高效算法设计举例 39
1.4 动态规划专题 60
1.5 小结与习题 77
第2章 数学基础 103
2.1 基本计数方法 103
2.2 递推关系 109
2.3 数论 119
2.3.1 基本概念 119
2.3.2 模方程 126
2.4 组合游戏 132
2.5 概率与数学期望 139
2.6 置换及其应用 144
2.7 矩阵和线性方程组 151
2.8 数值方法简介 163
2.9 小结与习题 170
第3章 实用数据结构 186

　　“请问新书《算法实践手册》什么时候出版？望眼欲穿啊……”
　　自《算法竞赛入门经典》（以下简称《入门经典》）出版以来，我收到的这样的来信已经不计其数。
　　不过，我心里有着自己的打算。《入门经典》的出版固然为广大算法爱好者提供了一些帮助，但其中的缺憾也是很明显的，如例题太少，习题没有中文翻译，而且限于篇幅，基础知识还没讲完……这样看来，《算法实践手册》的出版时机尚未成熟，还需要一本书来铺垫，弥补上述缺憾。可惜的是，由于创业的繁忙，这个想法一直未能实现。
　　2010年8月底，我收到了一封读者的E-mail，和我探讨《入门经典》中的一些问题，从此和本书的第二位作者陈锋相识。我万万没有想到，这位来自银行业的软件工程师、产品架构师学习编程的时间只有两三年，他对算法的热爱、严谨求实的态度和认真刻苦的专业精神绝不亚于有着多年算法和软件工程经验的行家。在与陈锋的交流过程中，我重新开始了对这本新书的构思。
　　事实上，在《入门经典》的写作过程中，完成的书稿远远不止印刷出来的220多页，只是因为篇幅和内容限制没有用到该书中。如果好好地把这些书稿加以整理，再算上笔者多年来外出讲课时制作的课件、题目翻译，那么本书的轮廓已经呼之欲出。这些东西对我来说已经是老生常谈，但接触算法不久的陈锋却觉得很新鲜。这样，我萌生出了一个有趣的念头：和陈锋一起合著一本书，我提供资料和总揽全局，而陈锋一边学习以前没有接触过的新知识，一边把这些东西按照适合初学者的方式重新进行组织和细化，并以“没参加过算法竞赛的软件工程师”这样一个独特的视角提出各种意见和建议。
　　细水长流了一年多之后，这个构想终于成为了现实。虽然大量的业余时间都奉献给了这本书，但我相信这是值得的。
　　参与本书编写和校对工作的还有中国人民大学的陈卓华和陈怡、北京大学的鲍由之（绘制了书中的几乎全部插图）等；一位不愿透露姓名的台湾朋友阅读了几乎全部书稿并给出了非常详细的修改意见。为了更好地配合本书，我在UVa上举办了3场专题比赛（数据结构、几何、实用程序），并将其中的典型题目收录在了正文例题或者习题当中。由于题目难度颇大，如果没有李益明、梁盾、沈业基、李耀、周而进、陈卓华、陈怡、唐迪、李晔晨、肖刘明镜、鲍由之等朋友的鼎力相助，这些比赛几乎不可能取得圆满成功。
　　另外，我还要感谢CCF（中国计算机学会）的杜子德秘书长、吴文虎教授、王宏教授等，还有NOI科学委员会及竞赛委员会的专家们，以及ACM/ICPC亚洲区主席黄金雄教授和中国指导委员会秘书长周维民教授。他们都是我的良师益友，在我接触NOI和ACM/ICPC以来的十多年里让我学到了很多东西。
　　感谢清华大学出版社辛勤劳动的编辑们，尤其是与我合作多年的朱英彪老师，在本丛书的编写、出版和推广方面都做了大量的工作，是一位真心实意为读者着想的好编辑。
　　最后，感谢我的爸爸妈妈。不管我做什么，不管别人怎么说怎么看，你们总是那样的支持我，让我可以全身心的投入自己喜爱的事业，没有半点后顾之忧。你们教给我的善良、感恩和奉献，正是我多年来坚持写书的源动力。
　　刘汝佳
　　许多计算机相关专业的人在毕业之后除了为应付面试外基本都很少再去碰算法，而在实际的产品或者项目开发过程中，大多数人也没有必要亲自去实现复杂的算法。因此，算法渐渐淡出程序员的日常生活。同时，在现实生活中有另外一种声音：程序员的生活太纠结，coding的速度永远跟不上需求变化的速度，提需求的客户似乎成了程序员的“天敌”，成了他们“苦逼”生活的罪魁祸首。
　　那么，一本讲算法比赛的书跟这又有多少关系？就从我自身的经历说起吧。我不是计算机科班出身，但因种种原因进入了这个行业，而且是从一个很低的起点进入。于是我像所有人一样，平时很难静下心来学习算法，有的面试就去临时抱本书突击一下。终于有一天我受不了这种循环，问自己难道一定是为了一个急功近利的目的才去付出自己的时间吗？佛家有句话叫“凡夫求果，菩萨求因”，我就想，既然成不了圣人，就学一回圣人吧。
　　因缘际会，我接触到了《入门经典》及其作者刘汝佳，于是一发不可收拾，写这本书的过程也变成了修行与学习的过程。慢慢地，我发现算法对于实际工作的人而言，有着比应付面试更大的价值。所谓的算法、组件、模式，就像是一些基础的原材料，对于优秀的建筑师来说，需要透彻的理解（不一定写得很熟练）它们的关键性。因为一个错误的设计，对于系统来说，所要付出的代价远比一般的程序bug要高得多。更进一步说，现在做软件的为啥苦，为啥抱怨需求变化快？因为解决问题的思维有偏差。需求分析绝对不是简单地拿着需求，直接翻译成代码——这是最低层次的。算法分析的意义，更多地不在于性能，不在于那些脑筋急转弯，而在于发现纷繁复杂的问题背后的不变式，而这正是本书要着力与大家分享的。
　　没有大家的支持和帮助，这本书几乎是不可能写好的。尤其要感谢我的家人和朋友，为了这本书的写作，他们投入了大量的时间和精力。这里尤其是在我工作非常繁忙的情况下，写作占用了大量跟家人在一起的时间，没有妻子梁明珠和女儿婉之的支持，我几乎不可能集中精力参与本书的写作过程。
　　另外，也感谢我的同事徐海波、张大用、周洲、王洪桥、朱宗耀、朱洁晨等，他们不仅在工作上给了我非常大的支持和帮助，也对我参与写作的章节提出了很多非常好的建议。
　　陈锋
　　声明：书中用到了大量的例题和习题，感谢这些命题者和竞赛组织方的辛勤劳动。笔者已经尽可能地找到他们并征求了题目的使用权，但如果你认为本书侵犯了你的权益，请与出版社和作者取得联系。在UVa网站上可以找到本书大多数例题/习题的作者。
　　

　　【输入格式】
　　输入包含多组数据。每组数据的第一行为学生个数n（1≤n≤500000）；以下每行包含两个不同的非负整数A和B，表示该学生想从A学校换到B学校。输入结束标志为n=0。
　　【输出格式】
　　对于每组数据，输出YES或者NU。
　　复合词（Compound Words，UVa 10391）
　　给定一个词典，要求找出其中所有的复合词，即恰好由两个单词连接而成的单词。
　　【输入格式】
　　输入只有一组数据，其中每行都是一个由小写字母组成的单词。输入已按照字典序排序，且不超过120000个单词。
　　【输出格式】
　　输出所有复合词，按照字典序排列。
　　Gergovia的酒交易（Wire trading in Gergovia，UVa 11054）
　　直线上有n个等距的村庄，每个村庄要么买酒，要么卖酒。把k个单位的酒从一个村庄运到相邻村庄需要k个单位的劳动力。问最少需要多少劳动力才能满足所有村庄的需求。
　　【输入格式】
　　输入包含多组数据。每组数据的第一行为村庄个数n（2≤n≤100000）；第二行从左到右给出各个村庄对酒的需求ai（—1000≤a≤1000），其中ai>0表示买酒，ai 【输出格式】
　　输出劳动力总和的最小值。输出保证在64位带符号整数的范围内。
　　平均值（Average，Seoul 2009，LA 4726）
　　给定一个长度为n的01序列，选一个长度至少为L的连续子序列，使得子序列中数字的平均值最大。如果有多解，子序列长度应尽量小；如果仍有多解，起点编号应尽量小。序列中的字符编号为1～n，因此[I，n]就是指完整的序列。
　　例如，对于长度为17的序列00101011011011010，如果L=7，子序YU[7，14]的平均值最大，为6／8（它的长度为8）；如果L=5，子序列[7，11]的平均值最大，为4／5。
　　【输入格式】
　　输入的第一行为数据组数T。每组数据的第一行为两个整数胛和L（1≤n≤100000，1≤L≤1000），第二行为一个长度为n的01序列。

　　篇章节选
　　第4章 几 何 问 题
　　几何问题是高水平算法竞赛中不可或缺的题型。由于背景知识多，内容杂乱，因此《算法竞赛入门经典》几乎没有涉及真正意义上的几何问题。本章通过介绍一些几何中的常见问题和算法，力图让读者具备一定的几何解题能力，并感受到几何的美。
　　4.1 二维几何基础
　　简单地说，向量（vector）就是有大小和方向的量，如速度、位移等物理量都是向量。向量最基本的运算是加法，满足平行四边形法则，如图4-1所示。
　　在平面坐标系下，向量和点一样，也用两个数x、y表示。它等于向量的起点到终点的位移，也相当于把起点平移到坐标原点后，终点的坐标。尽管如此，请读者不要在概念上把点和向量弄混。比如，点-点=向量，向量+向量=向量，点+向量=点，而点+点是没有意义的。在第6章中，我们会介绍齐次坐标的概念，从而在程序上区分开点和向量，但在本章中，点和向量都用两个数x、y表示。
　　下面是它们的常用定义。
　　
　　struct Point {
　　 double x, y;
　　 Point(double x=0, double y=0):x(x),y(y) { } //构造函数，方便代码编写
　　};
　　
　　typedef Point Vector; //从程序实现上，Vector只是Point的别名
　　
　　//向量+向量=向量，点+向量=点
　　Vector operator + (Vector A, Vector B) { return Vector(A.x+B.x, A.y+B.y); }
　　//点-点=向量
　　Vector operator - (Point A, Point B) { return Vector(A.x-B.x, A.y-B.y); }
　　//向量*数=向量