算法竞赛入门经典（第二版） (算法艺术与信息学竞赛).pdf

刘汝佳，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年出版算法竞赛入门经典，2012年出版算法竞赛入门经典训练指南。多年来在全国二十余个城市进行中学生竞赛培训工作，为北京、上海、吉隆坡等地的著名高校授课与宣讲，并多次与TopCoder、百度和网易有道等知名企业合作举办比赛，让更多的IT人才获得展示自我的平台。内容简介本书是一本算法竞赛的入门与提高教材，把C/C+语言、算法和解题有机地结合在一起，淡化理论，注重学习方法和实践技巧。全书内容分为12章，包括程序设计入门、循环结构程序设计、数组和字符串、函数和递归、C+与STL入门、数据结构基础、暴力求解法、高效算法设计、动态规划初步、数学概念与方法、图论模型与算法、高级专题等内容，覆盖了算法竞赛入门和提高所需的主要知识点，并含有大量例题和习题。书中的代码规范、简洁、易懂，不仅能帮助读者理解算法原理，还能教会读者很多实用的编程技巧；书中包含的各种开发、测试和调试技巧也是传统的语言、算法类书籍中难以见到的。本书可作为全国青少年信息学奥林匹克联赛（NOIP）复赛教材、全国青少年信息学奥林匹克竞赛（NOI）和ACM国际大学生程序设计竞赛（ACM/ICPC）的训练资料，也可作为IT工程师与科研人员的参考用书。本书封面贴有清华大学出版社防伪标签，无标签者不得销售。版权所有，侵权必究。侵权举报电话：010-6278298913701121933图书在版编目（CIP）数据算法竞赛入门经典/刘汝佳编著2版北京：清华大学出版社，2014（算法艺术与信息学竞赛）ISBN 978-7-302-35628-8算刘计算机算法-教材TP301.6中国版本图书馆CIP数据核字（2014）第046697号责任编辑：朱英彪封面设计：刘超版式设计：文森时代责任校对：王云责任印制：出版发行：清华大学出版社网址：http:/，http:/地址：北京清华大学学研大厦A座邮编：100084社 总 机：010-62770175邮购：010-62786544投稿与读者服务：010-62776969，c-质量反馈：010-62772015，印 刷 者：装 订 者：经销：全国新华书店开本：185mm260mm印张：30.5字数：794千字版次：2009年11月第1版2014年6月第2版印次：2014年6月第1次印刷印数：15000定价：49.80元产品编号：055687-01推荐序一算法竞赛入门经典（第2版）要面世了。一方面高兴，一方面也想借题发挥，这是因为近年来我和我的团队致力于研究计算机教育的改革，对于应该如何提升学生的思维能力和行动能力有了新的认识。当然我会把握“不要离题太远”。在我的书案上常年摆着一本蓝皮的书算法艺术与信息学竞赛，这是刘汝佳与黄亮合写的书，2003年12月我怀着喜悦的心情给这本书写了一页纸的序言。今天，时隔十年，我又拿起笔来为汝佳的新书作序，想到信息学奥林匹克的魅力，看到我们的学生能够承担起普及的责任和水平，此时此刻我的欣喜之情难以言表。“青出于蓝更胜于蓝”是我们当老师的最大愿望和期盼。汝佳之所以能写出这种内容和内涵丰富，文字也很难表达的思维艺术之美的好书，在于他对于信息学竞赛的热爱和他在青少年中普及计算机知识的强烈的责任感。汝佳为人低调诚实，做事认真负责，最可贵之处是那种“打破砂锅问到底”的求真务实精神，还有就是愿意和善于与人合作共事，能够真心听取别人的意见。刘汝佳在中学参加信息学奥赛，进入清华大学后作为主力队员参加过ACM/ICPC世界大学生程序设计大赛，在本科和读研期间又长期担任国际信息学奥林匹克中国队的教练。很早以前他就说过：想写一本“从入门开始就能陪伴着读者的书”，意思是书的作用不仅是答疑、解惑，更是像朋友和知己，同读者一起探讨和研究问题。我当然赞成著书者的境界，在我给本科生上“程序设计基础”课时的感悟是：教学相长，发挥学生在学习中的主体作用，激发兴趣和调动积极性，创造条件，使其参与课程内容的研讨，并提出宝贵意见，是成就精品课的必由之路。汝佳说：“书的第12章就像是一个路标，告诉你每条路通往怎样的风景，但是具体还得靠读者自己走过去，在走之前也需要自己选择。”话说得很到位。闪光的东西蕴含在解决问题时的那些思维之美中，精妙的解题思路和策略有时令人拍案叫绝，一路学一路体味赏心悦目的风景，没有不爱学和学不会之理。学会编程是一件相当重要的事，我在清华上课时对学生说“这是你们的看家本事”。一个国家，一个民族，要想不落伍，要想跻身于世界民族之林，关键在于拥有高素质的人才。学习和掌握信息科学与技术，在高水准人才的知识结构中占有重要的地位。讲文化要以科学为基础，讲科学要提高到文化的高度。学习计算机必须了解这一学科的内在规律和特征，“构造性”和“能行性”是计算机学科的两个最根本特征。与构造性相应的构造思维，又称计算思维，指的是通过算法的“构造”和实现来解决一个给定问题的一种“能行”的思维方式。有些问题没有固定的解法，给读者留有广阔的发挥创造力的空间，经过思考构造出的算法能不能高效地解决问题，都得通过上机实践的检验，在这一过程中思维能力和行动能力会同步提升。我认为高手应该是这样炼成的。光说不练，纸上谈兵是绝对学不会的。当前，有识之士已经认识到：大学计算机作为基础课，与数学、物理同样重要。培养计算机的应用能力，掌握使用计算机的思路和方法，必须既动手又动脑，体会和感悟蕴含于其中的计算思维要素，对于现代人是非常重要的。当你拿到这本书时，建议你先看“阅读说明”。其中有两点，一是“本书最好是有人带着学习”，如果这一点做不到的话，建议你求助于网络，开展合作学习，向高人请教，让心得共享，这些都符合现代学习理念；二是“一定要重视书中的提示”，因为其中包含着需要掌握的重要知识点和编程技巧，你会发觉有些内容在一般教科书中是看不到的。这是一本学习竞赛入门的书。我想说的是参加信息学竞赛入门不难，深造也是做得到的，关键是专心、恒心与信心，世上无难事，只要肯攀登！全国信息学奥林匹克（NOI）科学委员会名誉主席国际信息学奥林匹克中国队总教练清华大学计算机科学与技术系吴文虎推荐序二认识刘汝佳已有十多年的时间。2000年3月，我作为NOI（全国信息学奥林匹克）科学委员会委员赴澳门参加NOI2000的竞赛组织工作，正是在那届NOI上，刘汝佳以总分第四名的优异成绩获得NOI2000金牌并进入国家集训队。保送进入清华计算机系后，他又经选拔成为清华大学ACM队的主力队员，先后获得2001年ACM/ICPC（国际大学生程序设计竞赛）亚洲-上海赛区冠军和2002年世界总决赛的银牌（世界第四）。其后的多年时间里，他还同时担任NOI科学委员会的学生委员和IOI（国际信息学奥林匹克）中国国家队的教练。2005-2007年，刘汝佳在清华计算机系读研期间，正逢我为本科生开设数据结构课程，他多次担任这门课程的助教工作。十多年来他几乎每年都受聘参加NOI冬令营的授课，并赢得听课选手的一致好评。可以说，刘汝佳既是一名NOI和ACM/ICPC成绩优异的金牌选手，又是曾多年执教国家集训队的金牌教练，同时还作为在NOI冬令营等竞赛培训第一线参与授课培训最受欢迎的金牌教师。他在信息学奥赛方面的丰富经历与多重身份，特别是近20年来他对信息学奥赛的痴迷与执着，使得他对程序设计语言得心应手，对各种数据结构和算法的理解也颇有心得。这些都为他日后编写算法和编程竞赛的多部专著奠定了坚实的基础。以信息学奥赛的应用为背景，将数据结构和算法的知识点讲解与信息学奥赛的问题求解紧密联系在一起，通过大量鲜活的奥赛解题实例让读者领悟到不同算法和数据结构的精妙，是刘汝佳教材的独到之处与鲜明特色。这也是国内大量单一身份的作者（课程教师）编写的教材所欠缺又无法企及的。我们通常看到的或者是单纯叙述算法与数据结构知识的普通教材，或者是专门针对竞赛题目的题解汇编，但真正既能涵盖算法竞赛的主要知识点，又融入大量比赛技巧和解题经验教训，且将二者融会贯通的教材实在是凤毛麟角。刘汝佳的教材在这方面或者可以说是填补了空白，至少也称得上是独树一帜，这也是许多作者心有余而力不足的。从编排结构和写作特点上来说，刘汝佳的专著充分考虑不同层次的读者阅读需求，在算法竞赛入门经典中分为语言篇、基础篇和竞赛篇，循序渐进，既适合初学者，也适合高手进一步提升研读。特别是书中大量实用的示例代码和丰富的例题与习题，使各种水平的选手都能从他的书中获益并汲取营养，是有志在竞赛中取得佳绩的选手所必备的参考资料。从刘汝佳的第一本专著算法艺术与信息学竞赛问世至今刚好十年时间。其间，在读者好评如潮和高于市场预期的销量面前，刘汝佳并没有就此止步，而是搜集信息学竞赛选手的各种需求，对已出版的教材进行更多有益的尝试。在繁忙的工作之余仍能挤出时间笔耕不辍，这也从一个侧面反映了他的勤奋刻苦、不懈进取以及对信息学奥赛的执着追求。我们为国内信息学奥赛领域有汝佳这样优秀的专家学者感到庆幸。中国计算机学会2009年为他颁发的“特别贡献奖”实至名归。今年正值邓小平同志提出“计算机的普及要从娃娃抓起”和全国信息学奥林匹克创办30周年，刘汝佳的新版专著为这一历史时刻增光添彩。我们期待信息学奥赛领域有更多更好的教材专著问世。让一切与信息学奥赛相关的劳动、知识、技术、管理和资本的活力竞相迸发，让一切与信息学奥赛创新改革的源泉充分涌流。让我们共同努力，谱写全国信息学奥林匹克的新篇章。全国信息学奥林匹克（NOI）科学委员会主席清华大学计算机科学与技术系王宏推荐序三ACM国际大学生程序设计竞赛（简称为ACM-ICPC或ICPC）始于1970年，成形于1977年，并于1996年进入我国大陆。由于该项赛事形式别具一格，竞赛题目既有挑战性又有趣味性，有助于培养参赛选手的抽象思维、逻辑思维、心理素质、团队合作和协同能力，所以深受参赛选手们的喜爱，ACM-ICPC赛事也从不为人所知、从组委会千方百计邀请各个兄弟院校组队参赛捧场，到如今各赛区组委会都遇到了多次扩容仍无法满足大家的参赛愿望。虽然在1996年仅有19所学校的25队参赛，但在2013年已有来自250所高校的4300多队参加了网络赛，170多所学校的840多队获得了参加现场赛的机会。从竞赛中脱颖而出的优秀选手也获得了国内外著名企业的高度认可，可以说ACM-ICPC大赛得到社会各界的广泛认可，这也是对我们这批该项赛事组织者而言最大的鼓励和回报。刘汝佳则是从该项赛事中涌现出的佼佼者之一，他不仅在该项赛事中取得了优异的成绩，获得了2011年ACM-ICPC亚洲区上海赛区冠军和2002年夏威夷全球总决赛银奖第一，而且热心于该项赛事的著书写作和命题等工作。算法竞赛入门经典（第2版）将程序设计语言和算法灵活地结合在一起，形式独特，算法部分讲解细致，内容涵盖了许多经典算法，强调了不少入门时的注意事项，并且在一定程度上回答了“参加ACM-ICPC需要掌握哪些基本的知识点、哪些经典算法、要注意哪些基本的编程技巧、ICPC优秀选手是如何分析问题和优化代码的”等一系列问题。虽然本书不是一本专门为ACM-ICPC而写的教材，但是书中所有例题都来自ACM-ICPC相关竞赛，不仅可作为ACM-ICPC的入门参考书，同时也是一本适合具有一定数学基础但没有接触过程序设计的大学生阅读的算法参考书。ACM国际大学生程序设计竞赛中国区指导委员会秘书长上海大学周维民第2版前言算法竞赛入门经典第1版出版至今已有四个年头。这四年间发生了很多变化，如NOI系列比赛终于对STL“解禁”，如C11和C+11标准出台，g+编译器升级（直接导致本书第1版中官方使用的？运算符无法编译通过），如算法竞赛入门经典训练指南的出版弥补了本书第1版的很多缺憾，再如ACM/ICPC的蓬勃发展，使更多的大学生了解并参与到了算法竞赛中来看来，是时候给本书“升级”了。主要的变化我原本打算只是增加一章专门介绍C+和STL，用符合新语言规范的方式重写部分代码，顺便增加一些例题和习题，没想到一写就是100页几乎让书的篇幅翻了一倍。写作第1版时，220页的篇幅是和诸位一线中学教师商量后定下来的，因为书太厚会让初学者望而生畏。不过这几年的读者反馈让我意识到：由于篇幅限制，太多的东西让读者意犹未尽，还不如多写点。虽然之后出版了算法竞赛入门经典训练指南，但那本书的主要目标是补充知识点，即拓展知识宽度，而我更希望在知识宽度几乎不变的情况下增加深度我眼中的竞赛应该主要比思维和实践能力，而不是主要比见识。索性，我继续加大篇幅，用大量的例子（包括题目和代码）来表现我想向读者传达的信息。一位试读的朋友在收到第一份书稿片段时惊呼：“题目的质量比第1版提高太多了！”这正是我这次改版的主要目的。具体来说，这次改版有以下变化：在前4章中逐步介绍一些更实用的语言技巧，直接使用竞赛题目作为例子。全新的第5章，讲解竞赛中最常用的C+语法，包括STL算法和容器。第67章作为基础篇，加大代码和技巧的比例，并适当增加例题。第811章作为中级篇，增加了各种例题，着重锻炼思维能力。全新的第12章作为高级篇，在算法竞赛入门经典训练指南的基础上补充少量知识点与大量精彩例题。需要特别说明的是第12章出现的原因。这一章的内容很难，而且要求读者熟练掌握算法竞赛入门经典训练指南的主要内容，看起来和“入门”二字是矛盾的。其实本书虽然名为“入门经典”，实际上却不仅只适合入门读者。根据这几年读者反馈的情况来看，有相当数量的有经验的选手也购买了本书。原因在于：很多有经验的选手属于“自学成才”，总觉得自己可能会漏掉点什么基础知识。事实也是如此：本书中提到的很多代码和分析技巧是传统教科书中见不到的，对于很多有经验的选手来说也是“新鲜事物”，并且他们能比初学者更快、更好地把这些知识运用到比赛中去。本书第12章就是为这些读者准备的。如果这样解释还不够直观，就把第12章作为一个游戏里通关后多出来的Hard模式吧！阅读说明既然内容有了较大变化，阅读方式也需要再次说明一下。首先，和本书第1版一样，本书最好是有人带着学习，如老师、教练或者学长。随着网络的发展，这个条件越来越容易满足了就算是没人指导，也可以在别人的博客中留言，或者在贴吧中寻求帮助。一定要重视书中的“提示”。书中有很多“提示”部分都是非常重要的知识点或者技巧，有些提示看似平凡无奇，但如果没有引起重视而导致赛场上丢分，可是会追悔莫及的。接下来是关于新增第5章的。首先声明一点，这一章并不是C+语言速成C+语言是不可能速成的。这一章不是说你从头读到尾然后就掌握C+了，而是提供一个纲要，告诉你哪些东西是算法竞赛中最常用的，以及这些东西应当如何使用。你可以先另外找一本书（或者阅读网上的文章）学习C+，然后再看本书第5章（目的是把那些又容易晕又不那么有用的知识从脑子里删除），也可以直接看本书第5章，每次遇到看不懂或者觉得不够详细的地方，再找其他参考书来学。顺便说一句，就算你已经非常熟悉C+了，也最好浏览一下第5章（特别是代码！）。这不会花费太多时间，但很可能学到有用的东西。忍不住再说点题外话。有时学习算法的最好方法并不是编写程序，而是手算。“手算”这个词听上去有点枯燥，改成“玩游戏”如何？如雷顿教授与不可思议的小镇就是一个不错的选择它包含了过河问题（谜题7、93）、找砝码（谜题6、131）、一笔画（谜题30、39）、n皇后（谜题8083，130）、倒水问题（谜题23、24、78）、幻方（谜题95）、华容道（谜题97、132、135）等诸多经典问题。最后，需要特别指出的是，本书前11章中全部155道例题的代码都可以在代码仓库中下载：https:/ Hasan、Shahriar Manzoor、Derek Kisman、Per Austrin、Luis Garcia、顾昱洲、陈立杰、张培超等。第2版的习题全部（这次不仅仅是“主要”了）来自UVa在线评测系统，感谢Miguel Revilla教授、他的儿子Miguel Jr.和Carlos M.Casas Cuadrado对本书的大力支持。最后，再次感谢清华大学出版社的朱英彪编辑在这个恰当的时机提出改版事宜，并容忍我把交稿时间一拖再拖。希望这次改版不会让你失望。刘汝佳前言“听说你最近在写一本关于算法竞赛入门的书？”朋友问我。“是的。”我微笑道。“这是怎样的一本书呢？”朋友很好奇。“C语言、算法和题解。”我回答。“什么？几样东西混着吗？”朋友很吃惊。“对。”我笑了，“这是我思考许久后做出的决定。”大学之前的我12年前，当我翻开Sam A.Abolrous所著的C语言三日通的第一页时，我不会想到自己会有机会编写一本讲解C语言的书籍。当时，我真的只用了3天就学完了这本书，并且自信满满：“我学会C语言啦！我要用它写出各种有趣、有用的程序！”但渐渐地，我认识到了：虽然浅显易懂，但书中的内容只是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部分是语言篇（第14章），纯粹介绍语言，几乎不涉及算法，但逐步引入一些工程性的东西，如测试、断言、伪代码和迭代开发等。第2部分是算法篇（第58章），在介绍算法的同时继续强化语言，补充了第1部分没有涉及的语言特性，如位运算、动态内存管理等，并延续第一部分的风格，在需要时引入更多的思想和技巧。学习完前两部分的读者应当可以完成相当数量的练习题。第3部分是竞赛篇（第911章），涉及竞赛中常用的其他知识点和技巧。和前两部分相比，第3部分涉及的内容更加广泛，其中还包括一些难以理解的“学术内容”，但其实这些才是算法的精髓。本书最后有一个附录，介绍开发环境和开发方法，虽然它们和语言、算法的关系都不大，却往往能极大地影响选手的成绩。另外，本书讲解过程中所涉及的程序源代码可登录网站http:/ Revilla教授和Carlos M.CasasCuadrado的大力支持。最后，要特别感谢清华大学出版社的朱英彪编辑，与他的合作非常轻松、愉快。没有他的建议和鼓励，或许我无法鼓起勇气把“算法艺术与信息学竞赛”以丛书的全新面貌展现给读者。刘汝佳目录推荐序一推荐序二推荐序三第2版前言前言第1部分语言篇第1章程序设计入门1.1算术表达式1.2变量及其输入1.3顺序结构程序设计1.4分支结构程序设计1.5注解与习题1.5.1C语言、C99、C11及其他1.5.2数据类型与输入格式1.5.3习题1.5.4小结第2章循环结构程序设计2.1for循环2.2while循环和do-while循环2.3循环的代价2.4算法竞赛中的输入输出框架2.5注解与习题2.5.1习题2.5.2小结第3章数组和字符串3.1数组3.2字符数组3.3竞赛题目选讲3.4注解与习题3.4.1进位制与整数表示3.4.2思考题3.4.3黑盒测试和在线评测系统3.4.4例题一览与习题3.4.5小结第4章函数和递归4.1自定义函数和结构体4.2函数调用与参数传递4.2.1形参与实参4.2.2调用栈4.2.3用指针作参数4.2.4初学者易犯的错误4.2.5数组作为参数和返回值4.2.6把函数作为函数的参数4.3递归4.3.1递归定义4.3.2递归函数4.3.3C语言对递归的支持4.3.4段错误与栈溢出4.4竞赛题目选讲4.5注解与习题4.5.1头文件、副作用及其他4.5.2例题一览和习题4.5.3小结第5章C与STL入门5.1从C到C5.1.1C版框架5.1.2引用5.1.3字符串5.1.4再谈结构体5.1.5模板5.2STL初步5.2.1排序与检索5.2.2不定长数组：vector5.2.3集合：set5.2.4映射：map5.2.5栈、队列与优先队列5.2.6测试STL5.3应用：大整数类5.3.1大整数类BigInteger5.3.2四则运算5.3.3比较运算符5.4竞赛题目举例5.5习题第2部分基础篇第6章数据结构基础6.1再谈栈和队列6.2链表6.3树和二叉树6.3.1二叉树的编号6.3.2二叉树的层次遍历6.3.3二叉树的递归遍历6.3.4非二叉树6.4图6.4.1用DFS求连通块6.4.2用BFS求最短路6.4.3拓扑排序6.4.4欧拉回路6.5竞赛题目选讲6.6训练参考第7章暴力求解法7.1简单枚举7.2枚举排列7.2.1生成1n的排列7.2.2生成可重集的排列7.2.3解答树7.2.4下一个排列7.3子集生成7.3.1增量构造法7.3.2位向量法7.3.3二进制法7.4回溯法7.4.1八皇后问题7.4.2其他应用举例7.5路径寻找问题7.6迭代加深搜索7.7竞赛题目选讲7.8训练参考第3部分竞赛篇第8章高效算法设计8.1算法分析初步8.1.1渐进时间复杂度8.1.2上界分析8.1.3分治法8.1.4正确对待算法分析结果8.2再谈排序与检索8.2.1归并排序8.2.2快速排序8.2.3二分查找8.3递归与分治8.4贪心法8.4.1背包相关问题8.4.2区间相关问题8.4.3Huffman编码8.5算法设计与优化策略8.6竞赛题目选讲8.7训练参考第9章动态规划初步9.1数字三角形9.1.1问题描述与状态定义9.1.2记忆化搜索与递推9.2DAG上的动态规划9.2.1DAG模型9.2.2最长路及其字典序9.2.3固定终点的最长路和最短路9.2.4小结与应用举例9.3多阶段决策问题9.3.1多段图的最短路9.3.20-1背包问题9.4更多经典模型9.4.1线性结构上的动态规划9.4.2树上的动态规划9.4.3复杂状态的动态规划9.5竞赛题目选讲9.6训练参考第10章数学概念与方法10.1数论初步10.1.1欧几里德算法和唯一分解定理10.1.2Eratosthenes筛法10.1.3扩展欧几里德算法10.1.4同余与模算术10.1.5应用举例10.2计数与概率基础10.2.1杨辉三角与二项式定理10.2.2数论中的计数问题10.2.3编码与解码10.2.4离散概率初步10.3其他数学专题10.3.1递推10.3.2数学期望10.3.3连续概率10.4竞赛题目选讲10.5训练参考第11章图论模型与算法11.1再谈树11.1.1无根树转有根树11.1.2表达式树11.2最小生成树11.2.1Kruskal算法11.2.2竞赛题目选解11.3最短路问题11.3.1Dijkstra算法11.3.2Bellman-Ford算法11.3.3Floyd算法11.3.4竞赛题目选讲11.4网络流初步11.4.1最大流问题11.4.2增广路算法11.4.3最小割最大流定理11.4.4最小费用最大流问题11.4.5应用举例11.5竞赛题目选讲11.6训练参考11.7总结与展望第12章高级专题12.1知识点选讲12.1.1自动机12.1.2树的经典问题和方法12.1.3可持久化数据结构12.1.4多边形的布尔运算12.2难题选解12.2.1数据结构12.2.2网络流12.2.3数学12.2.4几何12.2.5非完美算法12.2.6杂题选讲12.3小结与习题附录A开发环境与方法A.1命令行A.1.1文件系统A.1.2进程A.1.3程序的执行A.1.4重定向和管道A.1.5常见命令A.2操作系统脚本编程入门A.2.1Windows下的批处理A.2.2Linux下的Bash脚本A.2.3再谈随机数A.3编译器和调试器A.3.1gcc的安装和测试A.3.2常见编译选项A.3.3gdb简介A.3.4gdb的高级功能A.4浅谈IDE主要参考书目第1部分语言篇第1章程序设计入门学习目标熟悉C语言程序的编译和运行学会编程计算并输出常见的算术表达式的结果掌握整数和浮点数的含义和输出方法掌握数学函数的使用方法初步了解变量的含义掌握整数和浮点数变量的声明方法掌握整数和浮点数变量的读入方法掌握变量交换的三变量法理解算法竞赛中的程序三步曲：输入、计算、输出记住算法竞赛的目标及其对程序的要求计算机速度快，很适合做计算和逻辑判断工作。本章首先介绍顺序结构程序设计，其基本思路是：把需要计算机完成的工作分成若干个步骤，然后依次让计算机执行。注意这里的“依次”二字步骤之间是有先后顺序的。这部分的重点在于计算。接下来介绍分支结构程序设计，用到了逻辑判断，根据不同情况执行不同语句。本章内容不复杂，但是不容忽视。注意：编程不是看会的，也不是听会的，而是练会的，所以应尽量在计算机旁阅读本书，以便把书中的程序输入到计算机中进行调试，顺便再做做上机练习。千万不要图快如果没有足够的时间用来实践，那么学得快，忘得也快。1.1算术表达式计算机的“本职”工作是计算，因此下面先从算术运算入手，看看如何用计算机进行复杂的计算。程序1-1计算并输出1+2的值#includeint main()printf(%dn,1+2);return 0;这是一段简单的程序，用于计算1+2的值，并把结果输出到屏幕。如果不知道如何编译并运行这段程序，可阅读附录A或向指导教师求助。即使读者不明白上述程序除了“1+2”之外的其他代码，仍然可以进行以下探索：试着把“1+2”改成其他内容，而不要修改那些并不明白的代码它们看上去工作情况良好。下面做4个实验。实验1：修改程序1-1，输出3-4的结果。实验2：修改程序1-1，输出56的结果。实验3：修改程序1-1，输出84的结果。实验4：修改程序1-1，输出85的结果。直接把“1+2”替换成“3-4”即可顺利解决实验1，但读者很快就会发现：无法在键盘上找到乘号和除号。解决方法是：用星号“*”代替乘号，而用正斜线“/”代替除号。这样，4个实验都顺利完成了。等一下！实验4的输出结果居然是1，而不是正确答案1.6。这是怎么回事？计算机出问题了吗？计算机没有出问题，问题出在程序上：这段程序的实际含义并非和我们所想的一致。在C语言中，8/5的确切含义是8除以5所得商值的整数部分。同样地，（-8）/5的值是-1。那么，如果非要得到85=1.6的结果怎么办？下面是完整的程序。程序1-2计算并输出8/5的值，保留小数点后1位#includeint main()printf(%.1fn,8.0/5.0);return 0;注意：百分号后面是一个小数点，然后是数字1，最后是小写字母f，千万不能输入错，包括大小写在C语言中，大写和小写字母代表的含义是不同的。再来做3个实验。实验5：把%.1f中的数字1改成2，结果如何？能猜想出“1”的确切意思吗？如果把小数点和1都删除，%f的含义是什么？实验6：字符串%.1f不变，把8.0/5.0改成原来的8/5，结果如何？实验7：字符串%.1f改成原来的%d，8.0/5.0不变，结果如何？实验5并不难解决，但实验6和实验7的答案就很难简单解释了真正原因涉及整数和浮点数编码，相信多数初学者对此都不感兴趣。原因并不重要，重要的是规范：根据规范做事情，则一切尽在掌握中。提示1-1：整数值用%d输出，实数用%f输出。这里的“整数值”指的是1+2、8/5这样“整数之间的运算”。只要运算符的两边都是整数，则运算结果也会是整数。正因为这样，8/5的值才是1，而不是1.6。8.0和5.0被看作是“实数”，或者说得更专业一点，叫“浮点数”。浮点数之间的运算结果是浮点数，因此8.0/5.0=1.6也是浮点数。注意，这里的运算符“/”其实是“多面手”，它既可以做整数除法，又可以做浮点数除法(1)。提示1-2：整数/整数=整数，浮点数/浮点数=浮点数。这条规则同样适用于加法、减法和乘法，不过没有除法这么容易出错毕竟整数乘以整数的结果本来就是整数。算术表达式可以和数学表达式一样复杂，例如：程序1-3复杂的表达式计算#include#includeint main()printf(%.8fn,1+2*sqrt(3)/(5-0.1);return 0;相信读者不难把它翻译成数学表达式。尽管如此，读者可能还是有一些疑惑：5-0.1的值是什么？“整数-浮点数”是整数还是浮点数？另外，多出来的#include有什么作用？第