作者：刘汝佳,陈锋
出版社：清华大学出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
算法竞赛入门经典——训练指南试读：
版权信息书名：算法竞赛入门经典——训练指南作者：刘汝佳,陈锋排版：aw出版社：清华大学出版社出版时间：2012-10-01ISBN：9787302291077本书由清华大学出版社有限公司授权北京当当科文电子商务有限公司制作与发行。— · 版权所有 侵权必究 · —作者简介刘汝佳，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年出版译著《编程挑战》。
多年来在全国二十余个城市进行中学生竞赛培训工作，为北京、上海、吉隆坡等地的著名高校授课与宣讲，并多次与TopCoder、百度和网易有道等知名企业合作举办比赛，让更多的IT人才获得展示自我的平台。
陈锋，1982年9月生。毕业于华北水利水电学院机械设计专业。曾就职于微软全球技术支持中心，负责.net虚拟机以及Visual Studio开发技术支持。后进入金融IT行业，专注于银行网点平台的产品研发，曾分别负责基于.net和Eclipse的两代网点平台产品的开发以及架构设计。现就职于北京宇信易诚科技，任前端产品技术经理及架构师。序
翻了翻UVa（Valladolid大学）在线评测系统的数据库，关于汝佳的第一条记录是在2000年11月15日，UTC时间是13点58分00秒——他在那时刚刚注册。这个时间在中国已经不算早了，但对于汝佳来说这完全不是问题，因为据我所知他随时都在工作。在那个即将结束的一天中，他提交了10道题目的22份C++代码，其中第一份代码是在注册后的短短数分钟之内提交的，并且获得了AC（正确），通过了题目264（Count on Cantor）。
当然，他也会犯一些错，不过当天结束时他已经搞定了3道题目，并且第二天就解决了剩下的全部题目。在年底之前（其实只有45天），汝佳提交了90道题目的307份代码，其中通过了59道。那个时候他还很年轻（差不多就是个孩子，就像他现在的模样），但他的思路已经很清晰了——那就是勤加练习的结果。
尽管上面讲的这些已经是陈年旧事了，但从中我可以断定：你们手中的这本书是一个非比寻常的伴侣，将带领你们走进计算机编程世界，尤其是编程竞赛世界。遗憾的是，书是用中文写成的，因此唯有懂中文的人才能享受到汝佳创造的这份魔法。幸运的是，他用UVa在线评测系统作为书中题目的来源，这使得我们这些不懂中文的人也可以透过题目了解到本书的知识体系和教学计划。他的这一举措是我们的荣幸，因为这本书给UVa网站增加了一份特殊的价值。汝佳很爱学习，也很乐意把自身所学倾囊相授。有了这本书，我们的工作有了更大的意义。
对我们来说，这也是一项挑战，因为我们必须更加努力地完善评测系统和网站，以回馈那些因为本书而对UVa网站产生兴趣的读者。我们也乐于接受这个挑战，因为我们很高兴看到UVa网站除了可以用来备战竞赛之外，还可以用来帮助人们学习算法。事实上，我们已经开始着手开发一个新的评测系统，挖掘学生群体中新的需求。我们希望能有更多的人参与，比如你。
最后，我想向所有的中国读者表达一份特殊的欢迎——欢迎你们通过本书认识和了解UVa在线评测系统（如果能顺便了解一下Valladolid这座城市就更好了），同时感谢汝佳邀请我用这些平凡的文字为这本不平凡的书作序。Miguel A. RevillaUVa在线评测系统创始人ACM-ICPC国际指导委员会成员、题目归档专家Valladolid大学／西班牙http://uva.onlinejudge.orghttp://livearchive.onlinejudge.org前 言“请问新书《算法实践手册》什么时候出版？望眼欲穿啊……”
自《算法竞赛入门经典》（以下简称《入门经典》）出版以来，我收到的这样的来信已经不计其数。
不过，我心里有着自己的打算。《入门经典》的出版固然为广大算法爱好者提供了一些帮助，但其中的缺憾也是很明显的，如例题太少，习题没有中文翻译，而且限于篇幅，基础知识还没讲完……这样看来，《算法实践手册》的出版时机尚未成熟，还需要一本书来铺垫，弥补上述缺憾。可惜的是，由于创业的繁忙，这个想法一直未能实现。
2010年8月底，我收到了一封读者的E-mail，和我探讨《入门经典》中的一些问题，从此和本书的第二位作者陈锋相识。我万万没有想到，这位来自银行业的软件工程师、产品架构师学习编程的时间只有两三年，他对算法的热爱、严谨求实的态度和认真刻苦的专业精神绝不亚于有着多年算法和软件工程经验的行家。在与陈锋的交流过程中，我重新开始了对这本新书的构思。
事实上，在《入门经典》的写作过程中，完成的书稿远远不止印刷出来的220多页，只是因为篇幅和内容限制没有用到该书中。如果好好地把这些书稿加以整理，再算上笔者多年来外出讲课时制作的课件、题目翻译，那么本书的轮廓已经呼之欲出。这些东西对我来说已经是老生常谈，但接触算法不久的陈锋却觉得很新鲜。这样，我萌生出了一个有趣的念头：和陈锋一起合著一本书，我提供资料和总揽全局，而陈锋一边学习以前没有接触过的新知识，一边把这些东西按照适合初学者的方式重新进行组织和细化，并以“没参加过算法竞赛的软件工程师”这样一个独特的视角提出各种意见和建议。
细水长流了一年多之后，这个构想终于成为了现实。虽然大量的业余时间都奉献给了这本书，但我相信这是值得的。
参与本书编写和校对工作的还有中国人民大学的陈卓华和陈怡、北京大学的鲍由之（绘制了书中的几乎全部插图）等；一位不愿透露姓名的台湾朋友阅读了几乎全部书稿并给出了非常详细的修改意见。为了更好地配合本书，我在UVa上举办了3场专题比赛（数据结构、几何、实用程序），并将其中的典型题目收录在了正文例题或者习题当中。由于题目难度颇大，如果没有李益明、梁盾、沈业基、李耀、周而进、陈卓华、陈怡、唐迪、李晔晨、肖刘明镜、鲍由之等朋友的鼎力相助，这些比赛几乎不可能取得圆满成功。
另外，我还要感谢CCF（中国计算机学会）的杜子德秘书长、吴文虎教授、王宏教授等，还有NOI科学委员会及竞赛委员会的专家们，以及ACM/ICPC亚洲区主席黄金雄教授和中国指导委员会秘书长周维民教授。他们都是我的良师益友，在我接触NOI和ACM/ICPC以来的十多年里让我学到了很多东西。
感谢清华大学出版社辛勤劳动的编辑们，尤其是与我合作多年的朱英彪老师，在本丛书的编写、出版和推广方面都做了大量的工作，是一位真心实意为读者着想的好编辑。
最后，感谢我的爸爸妈妈。不管我做什么，不管别人怎么说怎么看，你们总是那样的支持我，让我可以全身心的投入自己喜爱的事业，没有半点后顾之忧。你们教给我的善良、感恩和奉献，正是我多年来坚持写书的源动力。刘汝佳
许多计算机相关专业的人在毕业之后除了为应付面试外基本都很少再去碰算法，而在实际的产品或者项目开发过程中，大多数人也没有必要亲自去实现复杂的算法。因此，算法渐渐淡出程序员的日常生活。同时，在现实生活中有另外一种声音：程序员的生活太纠结，coding的速度永远跟不上需求变化的速度，提需求的客户似乎成了程序员的“天敌”，成了他们“苦逼”生活的罪魁祸首。
那么，一本讲算法比赛的书跟这又有多少关系？就从我自身的经历说起吧。我不是计算机科班出身，但因种种原因进入了这个行业，而且是从一个很低的起点进入。于是我像所有人一样，平时很难静下心来学习算法，有的面试就去临时抱本书突击一下。终于有一天我受不了这种循环，问自己难道一定是为了一个急功近利的目的才去付出自己的时间吗？佛家有句话叫“凡夫求果，菩萨求因”，我就想，既然成不了圣人，就学一回圣人吧。
因缘际会，我接触到了《入门经典》及其作者刘汝佳，于是一发不可收拾，写这本书的过程也变成了修行与学习的过程。慢慢地，我发现算法对于实际工作的人而言，有着比应付面试更大的价值。所谓的算法、组件、模式，就像是一些基础的原材料，对于优秀的建筑师来说，需要透彻的理解（不一定写得很熟练）它们的关键性。因为一个错误的设计，对于系统来说，所要付出的代价远比一般的程序bug要高得多。更进一步说，现在做软件的为啥苦，为啥抱怨需求变化快？因为解决问题的思维有偏差。需求分析绝对不是简单地拿着需求，直接翻译成代码——这是最低层次的。算法分析的意义，更多地不在于性能，不在于那些脑筋急转弯，而在于发现纷繁复杂的问题背后的不变式，而这正是本书要着力与大家分享的。
没有大家的支持和帮助，这本书几乎是不可能写好的。尤其要感谢我的家人和朋友，为了这本书的写作，他们投入了大量的时间和精力。这里尤其是在我工作非常繁忙的情况下，写作占用了大量跟家人在一起的时间，没有妻子梁明珠和女儿婉之的支持，我几乎不可能集中精力参与本书的写作过程。
另外，也感谢我的同事徐海波、张大用、周洲、王洪桥、朱宗耀、朱洁晨等，他们不仅在工作上给了我非常大的支持和帮助，也对我参与写作的章节提出了很多非常好的建议。陈锋
声明：书中用到了大量的例题和习题，感谢这些命题者和竞赛组织方的辛勤劳动。笔者已经尽可能地找到他们并征求了题目的使用权，但如果你认为本书侵犯了你的权益，请与出版社和作者取得联系。在UVa网站上可以找到本书大多数例题／习题的作者。阅读说明如何阅读本书
欢迎大家阅读本书！为了最大限度地发挥本书的作用，强烈建议您在阅读正文之前仔细地读完《阅读说明》，还要时不时地在学习过程中重读这些文字，以确保自己不会因为纠缠于书中的一些细节而变得舍本逐末，甚至偏离了预定的学习航线。切记！“覆盖面广，点到为止，注重代码”是本书的最大特点，而这3个特点都是为了向业界靠拢，注重广度而非深度。为了方便练习，书中所有题目来自于UVa在线评测系统和ACM/ICPC真题库（Live Archive, LA）。虽然这两个题库的题目不能包罗万象，但对于“点到为止”来说绰绰有余。书中的代码更多是为了提供一个容易理解、适合比赛的参考实例，并不推荐读者直接使用甚至背诵它们（关于这一点，在稍后还会有详细叙述）。关于知识点
本书不是一本算法竞赛入门类图书，因此并不从程序设计语言、算法的概念、基础数据结构、渐进时间复杂度分析这些内容讲起。如果你是一个新手，建议先阅读《算法竞赛入门经典》（和本书搭配着阅读也可以）。
聪明的选手都是善于利用网络资源的，如在网上交流讨论、阅读牛人的博客，寻找解题报告和测试数据等。这些方法也是阅读本书的重要辅助手段。由于算法竞赛涉及的知识点非常广，并且读者所具备[1]的知识水平参差不齐，因此，不同读者在阅读本书时会遇到不同的困难。这些困难有时并不是读者的问题，而且也无法靠修改书稿来避[2]免，因此，最好的办法就是上网搜索！
本书是完全的题目导向，掌握了书中的所有例题，也就掌握了书中的主要知识点和方法、技巧。在习题中也有少量相对不那么重要、例题没有涉及的东西，在每章的小结部分会明确指出。换句话说，对于每个知识点，最好的方法是结合例题分析和代码去理解，上机实践，最终达到能独立解决同类问题的目的。
本书的学习顺序不是单一的，但最好先阅读第1章，因为其中不少思想和编码技巧适用于全书。接下来，数学（第2章）、数据结构（第3章）、几何（第4章）、图论（第5章）等内容可以根据读者需要按任意顺序进行学习。事实上，笔者建议大家先学习这些章节的重要内容，等对全书有了一个整体认识之后再精读精练，千万不要过早地陷入难懂的细节（每章都有一些相对难懂的内容）。第6章主要是一些零散的知识点和技巧、方法，可以与其他章节穿插阅读。
请重视每章后面的小结与习题部分。虽然每章前面的文字一视同仁地对所有内容进行了逐一讲解，但在算法竞赛中，这些内容并不是同等重要的，思维训练和编程训练的内容和比重也不尽相同。当你不知道接下来应该学些什么、练些什么时，这些内容会是你最好的帮手。比如，如果关于某个知识点的习题特别少，这通常意味着该知识点很[3]少在竞赛中出现，或者只需要很少的练习就能掌握到其精髓。如何做题
书中的重要题目（包括例题和习题）均配有完整代码（限于篇幅，这些代码不一定会在书中出现）和测试数据，以方便读者学习，而其他题目也大都附有中文翻译，并且指明了题号、提交人数和通过比例等统计数据，以供读者训练参考。
书中题目数量不少，因此做题时必然要有一个先后顺序，建议初学者优先解决那些通过人数较多的题目，而已经开始专项训练的读者则可以根据需要选择难一些的题目。
考虑到很多读者并不是“久经沙场”的老手，这里以“蚂蚁”例题为例介绍做题的一般步骤。
蚂蚁（Piotr's Ants, UVa 10881）
一根长度为L厘米的木棍上有n只蚂蚁，每只蚂蚁要么朝左爬，要么朝右爬，速度为1厘米／秒。当两只蚂蚁相撞时，二者同时掉头（掉头时间忽略不计）。给出每只蚂蚁的初始位置和朝向，计算T秒之后每只蚂蚁的位置。【输入格式】
输入第一行为数据组数。每组数据的第一行为3个正整数L，T，n（0≤n≤10000），以下n行每行描述一只蚂蚁的初始位置。其中，整数x为它距离木棍左端的距离（单位：厘米），字母表示初始朝向（L表示朝左，R表示朝右）。【输出格式】
对于每组数据，输出n行，按输入顺序给出每只蚂蚁的位置和朝向（Turning表示正在碰撞）。在第T秒之前已经掉下木棍的蚂蚁（正好爬到木棍边缘的不算）输出Fell off。【样例输入】
2
10 1 4
1 R
5 R
3 L
10 R
10 2 3
4 R
5 L
8 R【样例输出】
Case #1:
2 Turning
6 R
2 Turning
Fell off
Case #2:
3 L
6 R
10 R
这是第1章中的例题5，是一道很有意思的题目。题目正文只有3句话，并不难理解，但正文并不是题目的全部。可以看到，一道完整的题目至少包含3个部分：题目描述、输入输出格式和样例输入输出，[4]缺一不可。
题目描述可以让你了解到你需要解决一个什么样的问题，但有些细节可能不会涉及。在第一次阅读时可以忽略掉不明白的地方，直接看输入输出格式，以了解具体的输入输出方法。对照输入输出格式和题目描述，可以更清楚地知道这道题目已知什么，要求什么。
输入输出格式往往有规律可循。例如，本书的题目全部采用ACM/ICPC比赛题目的格式，采用多数据输入输出。最常见的格式有以下两种。
格式一：输入第一行包含数据组数T。每组数据的第一行包含……主程序通常这样编写：
格式二：输入包含多组数据。每组数据的第一行包含一个整数n，输入结束标志为n＝0。主程序通常这样编写：
注意，上述代码用到了scanf的返回值，它返回的是成功读取的元素数目。换句话说，即使真实数据的最后并没有n＝0的“标志”，上述程序也会在文件结束后退出主循环。当然，正常情况下命题者不会忘记在数据末尾加上这个“标志”。但人非圣贤，孰能无过，即使在ACM/ICPC世界总决赛这样的重量级比赛中，也曾出现过数据不符合题目描述的情况。因此，作为选手来说，最好的方法是编写一个尽[5]量鲁棒的程序，即使在数据有瑕疵的情况下仍然能够通过数据。
输入输出格式的另一个作用是告知数据范围和约束。比如上述题2目中，“n≤10000”这个约束实际上是在警告选手：O（n）时间复杂[6]度的算法也许会超时。另一些重要的约束包括“输出保证不超过64位无符号整数的范围”、“输入文件大小不超过8MB”。前者通常意味[7]着我们不必使用高精度整数，而后者通常意味着我们需要注意输入数据的时间，不要采用太慢的输入方法（这个问题会在第1章中详细讨论）。
在很多题目中，正确的输出并不是唯一的。在这种情况下，题目要么会明确指出多解时任意输出一个解即可（此时会有一个称为special judge的程序来判断你的解是否正确），要么会告诉你输出哪一组解，以确保输出的唯一性。多数情况都是输出字典序最小或者最大的解。
看完题目描述和输入输出格式之后，还有一件重要的事要做，那就是阅读样例。很多题目的样例都是“可读”的，即至少包含一个简单到能够手算出来的例子。在这种情况下，强烈建议读者手算一下这个样例，因为这不仅可以帮助你理解题意、消除潜在的歧义，还能启发你的思路，使你从手算的过程中概括整理出本题的通用解法。如果[8]有疑问，还可以很方便地向主办方提出。
接下来，就可以设计算法并编写程序了。如何设计算法？如何编写程序？这正是本书的主题，所以在这里不再赘述，假定你已经顺利地写完程序。
接下来应当测试，看看你的程序是不是正确。编程的一大特点是“失之毫厘，谬以千里”，因此，哪怕只是写错了一个运算符，程序的结果也可能完全不对。所以，在提交程序之前应当好好测试一下。测试什么数据呢？最现成的当然就是样例了，但即使这样也远远不够。很多时候，样例并不具有典型性，通过样例也许只是碰巧；如果题目很难，就算样例很典型，也未必能覆盖到所有情况。也许你的程序几乎是完美的，但在一些特殊情况下也会出错，而样例并不包含这些特殊情况。因此，进行全面的测试是很有必要的。
一旦测试出错，就需要调试（debug）你的程序。调试的方法有很多种，如跟踪调试，即利用IDE的单步、断点、watch等功能，动态地检查程序的执行过程是否和预想中的一样。这样的技巧固然有用，但在算法竞赛中更常见的还是“断言＋输出中间结果”的方法，这在《算法竞赛入门经典》中已有详细叙述。需要特别注意的是，修改程序后最好测试一下以前测过的数据，以免“拆东墙补西墙”，修改了老bug的同时又引入了新bug。[9]
不管是参加什么样的比赛，都有一个“提交代码”的过程。为了尽可能地避免一些“非正常因素”的干扰，进行一些提交前的检查还是很有必要的。主要包括检查输入输出渠道是否正确（比如，文件输入还是标准输入，有没有忘记关闭文件）、调试用的中间结果是否已被屏蔽、数组有没有开得足够大、输出中的常量字符串有没有打错（一般来说，Yes打成yes将被判错）等。
本书的题目风格均为ACM/ICPC式的，因此每个程序只有“对”和“不对”两种结果（当然，还会告知“不对”的原因，详见《算法竞赛入门经典》），而没有“半对半错”之说。好在本书的所有题目均选自UVa在线评测系统和ACM/ICPC真题库（Live Archive，简称LA），这两个在线题库的操作几乎一样，都可以很方便地提交题目（只需要知道题号，通过网站左下方菜单中的“Quick Submit”命令即可提交）。在完成书后习题时，常常需要参考原题（如看样例或者输入输出格式），这里介绍两个“快捷方式”（以题目12345和2345为例）：
UVa题目链接：http://uva.onlinejudge.org/external/123/12345.html
LA题目链接：http://livearchive.onlinejudge.org/external/23/2345.html
当然，还可以直接用搜索引擎搜索“UVa 12345”或者“livearchive 2345”。
为了方便读者，书中给出了所有例题和习题的提交统计信息，比如511/80％是指有511个用户提交，其中约80％的用户通过。
请注意，题号越大，说明加入题库的时间越晚。新加入题库的题目，其提交量不会很大，因此统计数据并不一定能客观反映其真实难度。
很多选手都有过“一道题折腾了一个星期，交了100次才过”的经历，可见，在算法竞赛中，坚韧不拔的精神是多么地重要。当然了，笔者并不建议读者每道题目都错上100次以后才罢手，因此提供了重要题目的数据和代码。毕竟，在初学阶段，学习他人的代码以及“对着评测数据调试”都是重要的学习方法。但在达到一定水平之后，最好是独立编写程序，并且不借助评测数据——要知道，在真实比赛时，你能拿到的所有数据仅仅是样例。关于范例代码
本书中有很多代码，如果善加利用，这些代码可以帮你很大的忙；但如果滥用，非但不能发挥它们的最大好处，还可能会起到不好的作用。
关于书中的范例代码，笔者的建议只有一点：不要直接使用。理由有如下3点。
第一，不理解的代码不好用。所有代码都有它自身的适用范围，如果不理解其中的原理，不但有可能错误地使用这些代码，而且一旦需要对这些代码进行一定的修改才能符合题目要求时，你就会束手无策。解决方法很简单：想用的代码，事先重写一遍。这样不仅能加深你的理解，用的时候也更放心。
第二，代码习惯因人而异。书中的代码符合笔者的思维习惯和编码风格，却不一定适合你。比如，书中的代码把某个东西从0开始编号，而你习惯把任何东西从1开始编号，则当你混用自己的代码和书中的代码时，不仅编程时必须小心翼翼，而且很容易出现一些难以找到的bug。
第三，代码风格与传统的工程代码有冲突。作为从事软件开发工作多年的工程师，笔者深知算法竞赛代码和工程代码的差异。在算法竞赛中，由于时间紧迫，很多东西都“从简”了，很多“规矩”也都被无视了。比如，算法竞赛中经常使用全局变量、内存往往是事先分配一大堆而不是按需分配、很少使用OO特性（顶多用几个带有成员函数的struct，所有成员都是public的，并且很少用继承）、单个函数通常比工程代码长，但代码总长度通常更短，标识符通常也更短……如果本书采用传统的工程风格来编写代码，不仅会让书的厚度成倍增加，还会让读者在阅读了大量“无关紧要”的代码之后仍然不得要领，找不到最关键、最核心的地方。因此，笔者宁可让代码紧凑些，一方面让读者很容易抓住问题的核心，另一方面也锻炼了读者对程序整体逻辑（而非表达方式）的“感觉”——这恰恰是很多程序员所[10]缺乏的。一旦真正理解了这些“紧凑代码”，将其改成工程代码并不是难事。如前所述，这些代码会更好用，更符合你的需要。
不过，笔者有一点需要澄清：虽然和传统的工程代码有如此多的差异，但这并不是说本书的代码风格完全不适合工程项目。相反，本书的写作目的之一是希望读者能把两种风格有机地结合起来。比如，算法竞赛的选手写出来的代码通常比较简洁，这使程序具有更好的可读性和易维护性。笔者不主张把可读性肤浅地理解成“变量名取得长且有意义”、“注释足够多”、“每个函数都不超过10行”以及“拥有一个看上去很棒的类层次结构”，而应该更加看重程序的逻辑关系和执行流程。例如，对于下面这一段代码：任何一个具备一定算法基础的程序员都能够毫不犹豫地说出它的作用，不需要任何注释，也不需要给任何变量改一个“更有意义”的名字；相反，很多工整、干净甚至看起来很优美的“工程型”的算法代[11]码，却用了1000行来完成100行就能搞定的功能。随着代码长度的增加，潜在的bug数量、配套的单元测试数量以及人力成本等都会随之增长，而且增速通常快于线性函数。在这样的情况下，采用竞赛式的风格编写工程项目中的算法代码不仅是可行的，也是值得提倡的[12]。如果认真体会本书中的代码，你会发现它们比传统工程代码短的主要原因并不是变量名短、函数分得不细，而是因为逻辑更简单、清楚、直接。
考虑到参赛语言限制（ACM/ICPC只能使用C、C++和Java，NOI支持Pascal，但不支持Java），本书的正文选择了两种竞赛都支持的C++。但由于笔者在工作中还使用了大量的非C++语言（包括Java、C#、Python、JavaScript/CoffeeScript、ActionScript、Erlang、Scala等），因此，我们特别编写了一个附录来简单介绍其他3种语言——Java、C#和Python。强烈建议读者反复阅读这个特别的附录，它不仅能开阔你的眼界，还能帮你在竞赛和真实的软件开发之间架起一座桥梁。算法是软件开发的基石，但不是全部。注释[1] 笔者认为，本书的读者至少会覆盖从小学高年级学生到从事IT工作多年的工程师。[2] 比如，有些术语在学术界并没有统一的叫法，或者在不同文献中的叫法不同，如果本书采用的名称和你所熟知的不同，反而会产生误导。[3] 这两个原因并不是孤立的。一般来说，竞赛会偏爱那些精巧、灵活的内容，而非那些很难变形、扩展的死板东西。[4] 有的题目还包含其他部分，比如背景介绍、样例解释，甚至解题提示，但这些都不是必需的。[5] 书中多次强调的“把数组开大一些”也是基于这个考虑。2[6] 多数情况如此，但如果常数特别小，O（n）时间算法也有可能通过n＝10000的数据。[7] 但如果算法糟糕或者实现不好的话，中间结果有可能溢出！[8] 如果你问：“这题是什么意思？”，通常不会有人回答你；如果你问“这个样例为什么输出1”，常常都能得到满意的回答。[9] 有的比赛是上机结束后由机器自动收取，没有明显的“提交”过程，在此情况下，请把“提交”理解成“比赛结束”。[10] 如果你是在进行逆向工程，面对的是大量二进制的机器码，不仅没有注释，连变量名都没了，所能把握的就只有逻辑了。[11] 笔者一点都没有夸张。经验表明，10倍的比例是很正常的。[12] 也许最大的问题是：如果仍然以LOC（代码行数）来衡量工作量，习惯于编写紧凑代码的程序员往往很吃亏。第1章 算法设计基础
在《算法竞赛入门经典》一书中，已经讨论过算法分析、渐进时间复杂度等基本概念，以及分治、贪心、动态规划等常见的算法设计方法。本章是《算法竞赛入门经典》的延伸，通过例题介绍更多的算法设计方法和技巧。1.1 思维的体操例题1 勇者斗恶龙（The Dragon of Loowater, UVa 11292）
你的王国里有一条n个头的恶龙，你希望雇一些骑士把它杀死（即砍掉所有头）。村里有m个骑士可以雇佣，一个能力值为x的骑士可以砍掉恶龙一个直径不超过x的头，且需要支付x个金币。如何雇佣骑士才能砍掉恶龙的所有头，且需要支付的金币最少？注意，一个骑士只能砍一个头（且不能被雇佣两次）。【输入格式】
输入包含多组数据。每组数据的第一行为正整数n和m（1≤n，m≤20000）；以下n行每行为一个整数，即恶龙每个头的直径；以下m行每行为一个整数，即每个骑士的能力。输入结束标志为n＝m＝0。【输出格式】
对于每组数据，输出最少花费。如果无解，输出“Loowater is doomed!”。【样例输入】
2 3
5
4
7
8
4
2 1
5
5
10
0 0【样例输出】
11
Loowater is doomed!【分析】
能力强的骑士开价高是合理的，但如果被你派去砍一个很弱的头，就是浪费人才了。因此，可以把雇佣来的骑士按照能力从小到大排序，所有头按照直径从小到大排序，一个一个砍就可以了。当然，不能砍掉“当前需要砍的头”的骑士就不要雇佣了。代码如下。例题2 突击战（Commando War, UVa 11729）
你有n个部下，每个部下需要完成一项任务。第i个部下需要你花B分钟交待任务，然后他会立刻独立地、无间断地执行J分钟后完成ii任务。你需要选择交待任务的顺序，使得所有任务尽早执行完毕（即最后一个执行完的任务应尽早结束）。注意，不能同时给两个部下交待任务，但部下们可以同时执行他们各自的任务。【输入格式】
输入包含多组数据，每组数据的第一行为部下的个数N（1≤N≤1000）；以下N行每行两个正整数B和J（1≤B≤10000，1≤J≤10000），即交待任务的时间和执行任务的时间。输入结束标志为N＝0。【输出格式】
对于每组数据，输出所有任务完成的最短时间。【样例输入】
3
2 5
3 2
2 1
3
3 3
4 4
5 5
0【样例输出】
Case 1: 8
Case 2: 15【分析】
直觉告诉我们，执行时间较长的任务应该先交待。于是我们想到这样一个贪心算法：按照J从大到小的顺序给各个任务排序，然后依次交待。代码如下。
上述代码直接交上去就可以通过测试了。
可是为什么这样做是对的呢？假设我们交换两个相邻的任务X和Y（交换前X在Y之前，交换后Y在X之前），不难发现其他任务的完成时间没有影响，那么这两个任务呢？
情况一：交换之前，任务Y比X先结束，如图1-1（a）所示。不难发现，交换之后X的结束时间延后，Y的结束时间提前，最终答案不会变好。
情况二：交换之前，X比Y先结束，因此交换后答案变好的充要条件是：交换后X的结束时间比交换前Y的结束时间早（交换后Y的结束时间肯定变早了），如图1-1（b）所示。这个条件可以写成B[Y]＋B[X]＋J[X]＜B[X]＋B[Y]＋J[Y]，化简得J[X]＜J[Y]。这就是我们贪心的依据。图 1-1例题3 分金币（Spreading the Wealth, UVa 11300）
圆桌旁坐着n个人，每人有一定数量的金币，金币总数能被n整除。每个人可以给他左右相邻的人一些金币，最终使得每个人的金币数目相等。你的任务是求出被转手的金币数量的最小值。比如，n＝4，且4个人的金币数量分别为1，2，5，4时，只需转移4枚金币（第3个人给第2个人两枚金币，第2个人和第4个人分别给第1个人1枚金币）即可实现每人手中的金币数目相等。【输入格式】
输入包含多组数据。每组数据第一行为整数n（n≤1000000），以下n行每行为一个整数，按逆时针顺序给出每个人拥有的金币数。输入结束标志为文件结束符（EOF）。【输出格式】
对于每组数据，输出被转手金币数量的最小值。输入保证这个值在64位无符号整数范围内。【样例输入】
3
100
100
100
4
1
2
5
4【样例输出】
0
4【分析】
这道题目看起来很复杂，让我们慢慢分析。首先，最终每个人的金币数量可以计算出来，它等于金币总数除以人数n。接下来我们用M来表示每人最终拥有的金币数。
假设有4个人，按顺序编号为1，2，3，4。假设1号给2号3枚金币，然后2号又给1号5枚金币，这实际上等价于2号给1号2枚金币，而1号什么也没给2号。这样，可以设x表示2号给了1号多少个金币。2如果x＜0，说明实际上是1号给了2号-x枚金币。x，x和x的含义22134类似。注意，由于是环形，x指的是1号给4号多少金币。1
现在假设编号为i的人初始有A枚金币。对于1号来说，他给了4i号x枚金币，还剩A－x枚；但因为2号给了他x枚金币，所以最后还1i12剩A－x＋x枚金币。根据题设，该金币数等于M。换句话说，我们112得到了一个方程：A－x＋x＝M。112
同理，对于第2个人，有A－x＋x＝M。最终，我们可以得到n223个方程，一共有n个变量，是不是可以直接解方程组了呢？很可惜，还不行。因为从前n－1个方程可以推导出最后一个方程（想一想，为什么）。所以，实际上只有n－1个方程是有用的。
尽管无法直接解出答案，我们还是可以尝试着用x表示出其他的1x，则本题就变成了单变量的极值问题。i
对于第1个人，A－x＋x＝M→x＝M－A＋x＝x－C（规定11221111C＝A－M，下面类似）11
对于第2个人，A－x＋x＝M→x＝M－A＋x＝2M－A－A＋22332212x＝x－C112
对于第3个人，A－x＋x＝M→x＝M－A＋x＝3M－A－A－33443312A＋x＝x－C3113
…
对于第n个人，A－x＋x＝M。这是一个多余的等式，并不能给nn1我们更多的信息（想一想，为什么）。
我们希望所有x的绝对值之和尽量小，即｜x｜＋｜x－C｜＋i111｜x－C｜＋…＋｜x－C｜要最小。注意到｜x－C｜的几何意121n－11i义是数轴上点x到C的距离，所以问题变成了：给定数轴上的n个1i点，找出一个到它们的距离之和尽量小的点。
下一步可能有些跳跃。不难猜到，这个最优的x就是这些数的1“中位数”（即排序以后位于中间的数），因此只需要排个序就可以了。性急的读者可能又想跳过证明了，但是笔者希望您这次能好好读一读，因为它实在是太优美、太巧妙了，而且不少其他题目也能用上（我们很快就会再见到一例）。
注意，我们要证明的是：给定数轴上的n个点，在数轴上的所有点中，中位数离所有顶点的距离之和最小。凡是能转化为这个模型的题目都可以用中位数求解，并不只适用于本题。
让我们把数轴和上面的点画出来，如图1-2所示。图 1-2
任意找一个点，比如图1-2中的灰点。它左边有4个输入点，右边有2个输入点。把它往左移动一点，不要移得太多，以免碰到输入点。假设移动了d单位距离，则灰点左边4个点到它的距离各减少了d，右边的两个点到它的距离各增加了d，但总的来说，距离之和减少了2d。
如果灰点的左边有2个点，右边有4个点，道理类似，不过应该向右移动。换句话说，只要灰点左右的输入点不一样多，就不是最优解。什么情况下左右的输入点一样多呢？如果输入点一共有奇数个，则灰点必须和中间的那个点重合（中位数）；如果有偶数个，则灰点可以位于最中间的两个点之间的任意位置（还是中位数）。代码如下。
程序本身并没有太多技巧可言，但需要注意的是long long的输入输出。在《入门经典》中我们已经解释过了，％lld这个占位符并不是跨平台的，比如，Windows下的mingw需要用％I64d而不是％lld。虽然cin/cout没有这个问题，但是本题输入量比较大，cin/cout会很慢。有两个解决方案。一是自己编写输入输出函数（前面已经给过范例），二是使用ios::sync_ with_stdio（false），通过关闭ios和stdio之间的同步来加速，有兴趣的读者可以自行搜索详细信息。
中位数可以在线性时间内求出，但不是本例题的重点（代数分析才是重点），有兴趣的读者可以自行搜索“快速选择”算法的资料。另外，这个程序里的A数组实际上是不必保存的，你能去掉它吗？例题4 墓地雕塑（Graveyard, NEERC 2006, LA 3708）
在一个周长为10000的圆上等距分布着n个雕塑。现在又有m个新雕塑加入（位置可以随意放），希望所有n＋m个雕塑在圆周上均匀分布。这就需要移动其中一些原有的雕塑。要求n个雕塑移动的总距离尽量小。【输入格式】
输入包含若干组数据。每组数据仅一行，包含两个整数n和m（2≤n≤1000，1≤m ≤1000），即原始的雕塑数量和新加的雕塑数量。输入结束标志为文件结束符（EOF）。【输出格式】-4
输入仅一行，为最小总距离，精确到10。【样例输入】
2 1
2 3
3 1
10 10【样例输出】
1666.6667
1000.0
1666.6667
0.0【样例解释】
前3个样例如图1-3所示。白色空心点表示等距点，黑色线段表示已有雕塑。图 1-3【分析】
请仔细看看样例。3个样例具有一个共同的特点：有一个雕塑没有移动。如果该特点在所有情况下都成立，则所有雕塑的最终位置（称为“目标点”）实际上已经确定。为了简单起见，我们把没动的那个雕塑作为坐标原点，其他雕塑按照逆时针顺序标上到原点的距离标号，如图1-4所示。图 1-4
注意，这里的距离并不是真实距离，而是按比例缩小以后的距离。接下来，我们把每个雕塑移动到离它最近的位置。如果没有两个雕像移到相同的位置，那么这样的移动一定是最优的。代码如下。
注意在代码中，坐标为pos的雕塑移动到的目标位置是floor（pos＋0.5），也就是pos四舍五入后的结果。这就是坐标缩小的好处。
这个代码很神奇地通过了测试，但其实这个算法有两个小小的“漏洞”：首先，我们不知道是不是一定有一个雕塑没有移动；其次，我们不知道会不会有两个雕塑会移动到相同的位置。如果你对证明不感兴趣，或者已经想到了证明，再或者迫不及待地想阅读更有趣的问题，请直接跳到下一个例题。否则，请继续阅读。
第一个“漏洞”的修补需要证明我们的猜想。证明思路在例题3中我们已经展示过了，具体的细节留给读者思考。
第二个“漏洞”有两种修补方法。第一种方法相对较容易实施：由于题目中规定了n，m≤1000，我们只需要在程序里加入一个功能——记录每座雕塑移到的目标位置，就可以用程序判断是否会出现“人多坑少”的情况。这段程序的编写留给读者，这里可以明确地告诉大家：这样的情况确实不会出现。这样，即使无法从理论上证明，也可以确保在题目规定的范围内，我们的算法是严密的。
第二种方法就是直接证明。在我们的程序中，当坐标系缩放之后，坐标为x的雕塑被移到了x四舍五入后的位置。如果有两个坐标分别为x和y的雕塑被移到了同一个位置，说明x和y四舍五入后的结果相同，换句话说，即x和y“很接近”。至于有多接近呢？差距最大的情况不外乎类似于x＝0.5，y＝1.499999…。即便是这样的情况，y－x仍然小于1（尽管很接近1），但这是不可能的，因为新增雕塑之后，相邻雕塑的距离才等于1，之前的雕塑数目更少，距离应当更大才对。例题5 蚂蚁（Piotr's Ants, UVa 10881）
一根长度为L厘米的木棍上有n只蚂蚁，每只蚂蚁要么朝左爬，要么朝右爬，速度为1厘米／秒。当两只蚂蚁相撞时，二者同时掉头（掉头时间忽略不计）。给出每只蚂蚁的初始位置和朝向，计算T秒之后每只蚂蚁的位置。【输入格式】
输入的第一行为数据组数。每组数据的第一行为3个正整数L，T，n（0≤n≤10000）；以下n行每行描述一只蚂蚁的初始位置，其中，整数x为蚂蚁距离木棍左端的距离（单位：厘米），字母表示初始朝向（L表示朝左，R表示朝右）。【输出格式】
对于每组数据，输出n行，按输入顺序输出每只蚂蚁的位置和朝向（Turning表示正在碰撞）。在第T秒之前已经掉下木棍的蚂蚁（正好爬到木棍边缘的不算）输出Fell off。【样例输入】
2
10 1 4
1 R
5 R
3 L
10 R
10 2 3
4 R
5 L
8 R【样例输出】
Case #1:
2 Turning
6 R
2 Turning
Fell off
Case #2:
3 L
6 R
10 R【分析】
假设你在远处观察这些蚂蚁的运动，会看到什么？一群密密麻麻的小黑点在移动。由于黑点太小，所以当蚂蚁因碰撞而掉头时，看上去和两个点“对穿而过”没有任何区别，换句话说，如果把蚂蚁看成是没有区别的小点，那么只需独立计算出每只蚂蚁在T时刻的位置即可。比如，有3只蚂蚁，蚂蚁1＝（1，R），蚂蚁2＝（3，L），蚂蚁3＝（4，L），则两秒钟之后，3只蚂蚁分别为（3，R）、（1，L）和（2，L）。
注意，虽然从整体上讲，“掉头”等价于“对穿而过”，但对于每只蚂蚁而言并不是这样。蚂蚁1的初始状态为（1，R），因此一定有一只蚂蚁在两秒钟之后处于（3，R）的状态，但这只蚂蚁却不一定是蚂蚁1。换句话说，我们需要搞清楚目标状态中“谁是谁”。
也许读者已经发现了其中的奥妙：所有蚂蚁的相对顺序是保持不变的，因此把所有目标位置从小到大排序，则从左到右的每个位置对应于初始状态下从左到右的每只蚂蚁。由于原题中蚂蚁不一定按照从左到右的顺序输入，还需要预处理计算出输入中的第i只蚂蚁的序号order[i]。完整代码如下。例题6 立方体成像（Image Is Everything, World Finals 2004, LA 2995）
有一个n×n×n立方体，其中一些单位立方体已经缺失（剩下部分不一定连通）。每个单位立方体重量为1克，且被涂上单一的颜色（即6个面的颜色相同）。给出前、左、后、右、顶、底6个视图，你的任务是判断这个物体剩下的最大重量。【输入格式】
输入包含多组数据。每组数据的第一行为一个整数n（1≤n≤10）；以下n行每行从左到右依次为前、左、后、右、顶、底6个视图，每个视图占n列，相邻视图中间以一个空格隔开。顶视图的下边界对应于前视图的上边界；底视图的上边界对应于前视图的下边界。在视图中，大写字母表示颜色（不同字母表示不同颜色），句号（.）表示该位置可以看穿（即没有任何立方体）。输入结束标志为n＝0。【输出格式】
对于每组数据，输出一行，即物体的最大重量（单位：克）。【样例输入】【样例输出】【分析】
这个问题看上去有点棘手，不过仍然可以找到突破口。比如，能“看穿”的位置所对应的所有单位立方体一定都不存在。再比如，如果前视图的右上角颜色A和顶视图的右下角颜色B不同，那么对应的格子一定不存在。如图1-5所示。图 1-5
在删除这个立方体之后，我们可能会有新发现：C和D的颜色不同。这样，我们又能删除一个新的立方体，并暴露出新的表面。当无法继续删除的时候，剩下的立方体就是重量最大的物体。
可能有读者会对上述算法心存疑惑。解释如下：首先不难证明第一次删除是必要的（即被删除的那个立方体不可能存在于任意可行解中），因为只要不删除这个立方体，对应两个视图的“矛盾”将一直存在；接下来，我们用数学归纳法，假设算法的前k次删除都是必要的，那么第k＋1次删除是否也是必要的呢？由刚才的推理，我们不能通过继续删除立方体来消除矛盾，而由归纳假设，已经删除的立方体也不能恢复，因此矛盾无法消除。
下面给出完整代码。
程序用了一个get函数来表示第k个视图中，第i行j列、深度为len的单位立方体在原立方体中的坐标（x，y，z），另外还使用了宏REP精简程序。尽管用宏缩短代码在很多时候会降低程序可读性，但本题却不会（如果到处都是for循环，反而容易令人犯晕）。1.2 问题求解常见策略例题7 偶数矩阵（Even Parity, UVa 11464）
给你一个n×n的01矩阵（每个元素非0即1），你的任务是把尽量少的0变成1，使得每个元素的上、下、左、右的元素（如果存在的话）之和均为偶数。比如，如图1-6（a）所示的矩阵至少要把3个0变成1，最终如图1-6（b）所示，才能保证其为偶数矩阵。图 1-6【输入格式】
输入的第一行为数据组数T（T≤30）。每组数据的第一行为正整数n（1≤n≤15）；接下来的n行每行包含n个非0即1的整数，相邻整数间用一个空格隔开。【输出格式】
对于每组数据，输出被改变的元素的最小个数。如果无解，应输出-1。【分析】
也许最容易想到的方法就是枚举每个数字“变”还是“不变”，最后判断整个矩阵是否满足条件。遗憾的是，这样做最多需要枚举255672≈5×10种情况，实在难以承受。15
注意到n只有15，第一行只有不超过2＝32768种可能，所以第一行的情况是可以枚举的。接下来根据第一行可以完全计算出第二行，根据第二行又能计算出第三行（想一想，如何计算），以此类推，这n2样，总时间复杂度即可降为O（2×n）。代码如下。例题8 彩色立方体（Colored Cubes, Tokyo 2005, LA 3401）
有n个带颜色的立方体，每个面都涂有一种颜色。要求重新涂尽量少的面，使得所有立方体完全相同。两个立方体相同的含义是：存在一种旋转方式，使得两个立方体对应面的颜色相同。【输入格式】
输入包含多组数据。每组数据的第一行为正整数n（1≤n≤4）；以下n行每行6个字符串，分别为立方体编号为1～6的面的颜色（由小写字母和减号组成，不超过24个字符）。输入结束标志为n＝0。立方体的6个面的编号如图1-7所示。图 1-7【输出格式】
对于每组数据，输出重新涂色的面数的最小值。【分析】
立方体只有4个，暴力法应该可行。不过不管怎样“暴力”，首先得搞清楚一个立方体究竟有几种不同的旋转方式。
为了清晰起见，我们借用机器人学中的术语，用姿态（pose）来代替口语中的旋转方法。假设6个面的编号为1～6，从中选一个面作为“顶面”，然后在剩下的4个面中选一个作为“正面”，则其他面都可以唯一确定，因此有6×4＝24种姿态。
在代码中，每种姿态对应一个全排列P。其中，P[i]表示编号i所在的位置（1表示正面，2表示右面，3表示顶面等，如图1-8所示）。如图1-9所示的姿态称为标准姿态，用排列｛1，2，3，4，5，6｝表示，因为1在正面，2在右面，3在顶面等。图 1-8图 1-9
图1-10是标准姿态向左旋转后得到的。对应的排列是｛5，1，3，4，6，2｝。图 1-10
接下来有两种方法。一种方法是手工找出24种姿态对应的排列，编写到代码中。显然，这种方法比较耗时，且容易出错，不推荐使用。下面的方法可以用程序找出这24种排列，而且不容易出错。除了刚才写出的标准姿态向左翻之外，我们再写出标准姿态向上翻所对应的排列：｛3，2，6，1，5，4｝，如图1-11所示。图 1-11
注意到旋转是可以组合的，比如，图1-11标准姿态先向左转再向上翻就是5→5，1→3，3→6，4→1，6→4，2→2，即｛5，3，6，1，4，2｝。因此，有了这两种旋转方式，我们就可以构造出所有24种姿态了（均为从标准姿态开始旋转）。
1在顶面的姿态：向上翻1次（此时1在顶面），然后向左转0～3次。
2在顶面的姿态：向左转1次（此时2在顶面），向上翻1次，然后向左转0～3次。
3在顶面的姿态：（3本来就在顶面）向左转0～3次。
4在顶面的姿态：向上翻2次（此时4在顶面），然后向左转0～3次。
5在顶面的姿态：向左转2次，向上翻一次（此时5在顶面），然后向左转0～3次。
6在顶面的姿态：向左转3次，向上翻一次（此时6在顶面），然后向左转0～3次。
这段代码应该写在哪里呢？一种方法是直接手写在最终的程序中，但是一旦这部分代码出错，非常难调；另一种方法是写到一个独立程序中，用它生成24种姿态对应的排列，而在最终程序中直接使用常量表。生成排列表的程序如下（注意，在代码中编号为0～5，而非1～6）。
试读结束[说明：试读内容隐藏了图片]