（已有9条评价）基本信息
编辑推荐
世界顶级程序设计高手的经验总结
【ACM-ICPC全球总冠军】巫泽俊主译
日本ACM-ICPC参赛者人手一册
相关推荐:
<a href="http://product.china-pub.com/3768007" target="_blank"><img border="0" src="http://images.china-pub.com/ebook3765001-3770000/3768007/zcover.jpg" width="79" height="100"/>《算法设计编程实验：大学程序设计课程与竞赛训练教材》</a>
<a href="http://product.china-pub.com/305919" target="_blank"><img border="0" src="http://images.china-pub.com/ebook305001-310000/305919/zcover.jpg" width="79" height="100"/>《ACM国际大学生程序设计竞赛：算法与实现》</a>
<a href="http://product.china-pub.com/223252" target="_blank"><img border="0" src="http://images.china-pub.com/ebook195001-200000/199153/zcover.jpg" width="79" height="100"/>《(特价书)数据结构编程实验:大学程序设计课程与竞赛训练教材》</a>
内容简介
作译者
秋叶拓哉，Google Code Jam 2010 第9名；ACM-ICPC World Finals 2012 第11名；TopCoder Open 2012 Algorithm 第4名，昵称iwi
岩田阳一，Google Code Jam 2009 第3名；TopCoder Open 2010 Marathon 冠军；IPSC 2010 个人组 冠军，昵称wata
北川宜稔，ACM-ICPC World Finals 2010第16名，昵称kita_masa
巫泽俊，ACM-ICPC World Finals 2009 第6名；ACM-ICPC World Finals 2011 冠军；Google Code Jam 2012 第7名，昵称watashi和rejudge
庄俊元，ACM-ICPC Asia Phuket Regional 2011 冠军；2012年跻身ACM-ICPC World Finals以及百度Astar总决赛，昵称navi和navimoe
李津羽，浙江大学2011级计算机系博士生，在浙大CAD&CG实验室从事科研工作
岩田阳一，Google Code Jam 2009 第3名；TopCoder Open 2010 Marathon 冠军；IPSC 2010 个人组 冠军，昵称wata
北川宜稔，ACM-ICPC World Finals 2010第16名，昵称kita_masa
巫泽俊，ACM-ICPC World Finals 2009 第6名；ACM-ICPC World Finals 2011 冠军；Google Code Jam 2012 第7名，昵称watashi和rejudge
庄俊元，ACM-ICPC Asia Phuket Regional 2011 冠军；2012年跻身ACM-ICPC World Finals以及百度Astar总决赛，昵称navi和navimoe
李津羽，浙江大学2011级计算机系博士生，在浙大CAD&CG实验室从事科研工作
目录
《挑战程序设计竞赛(第2版)》
第1章 蓄势待发——准备篇 1
1.1 何谓程序设计竞赛 2
1.2 最负盛名的程序设计竞赛 5
1.2.1 世界规模的大赛——Google Code Jam（GCJ） 5
1.2.2 向高排名看齐！——TopCoder 5
1.2.3 历史最悠久的竞赛—— ACM-ICPC 6
1.2.4 面向中学生的信息学奥林匹克竞赛——JOI-IOI 6
1.2.5 通过网络自动评测——Online Judge（OJ） 6
1.3 本书的使用方法 7
1.3.1 本书所涉及的内容 7
1.3.2 所用的编程语言 7
1.3.3 题目描述的处理 7
1.3.4 程序结构 7
1.3.5 练习题 8
1.3.6 读透本书后更上一层楼的练习方法 8
1.4 如何提交解答 9
1.4.1 POJ的提交方法 9
1.4.2 GCJ的提交方法 11
1.5 以高效的算法为目标 15
第1章 蓄势待发——准备篇 1
1.1 何谓程序设计竞赛 2
1.2 最负盛名的程序设计竞赛 5
1.2.1 世界规模的大赛——Google Code Jam（GCJ） 5
1.2.2 向高排名看齐！——TopCoder 5
1.2.3 历史最悠久的竞赛—— ACM-ICPC 6
1.2.4 面向中学生的信息学奥林匹克竞赛——JOI-IOI 6
1.2.5 通过网络自动评测——Online Judge（OJ） 6
1.3 本书的使用方法 7
1.3.1 本书所涉及的内容 7
1.3.2 所用的编程语言 7
1.3.3 题目描述的处理 7
1.3.4 程序结构 7
1.3.5 练习题 8
1.3.6 读透本书后更上一层楼的练习方法 8
1.4 如何提交解答 9
1.4.1 POJ的提交方法 9
1.4.2 GCJ的提交方法 11
1.5 以高效的算法为目标 15
译者序
程序设计竞赛因其涉及的知识面广，比赛形式激烈有趣，吸引了越来越多的学生参与其中。参赛者不但可以从中锻炼算法设计能力，还能够提高代码编写能力。其中的佼佼者也受到了越来越多国际知名公司的重视和欢迎。
本书的几位作者是世界公认的顶尖选手，在竞赛和学术领域都取得了令人瞩目的成就。他们结合自己的专业知识和比赛经验，将自己的心得和技巧集结成书。
全书将不同的算法和例题按专题编排成小节，再将不同的小节由易到难分成四章，这样即便是初出茅庐的新手也不会有太大的阅读障碍。书中涵盖了在程序设计竞赛中会用到的大多数算法和技巧，并在附录中补充了书中未介绍但也比较有用的算法。在题材的安排上，作者取舍得当，主次分明，循序渐进，不以华而不实的奇技淫巧误导读者，又具有一定深度，相信即便是经验丰富的老将同样能从书中有所斩获。本书在结合例题进行讲解时，不是简单地堆砌问题和代码，而是注重引导读者更好地理解和运用算法来分析解决问题。对于正在学习数据结构与算法的读者而言，把它作为一本练习和拓展的参考书也是很好的选择。
本书在日本广受好评，还先后在台湾地区和韩国出版。近年来程序设计竞赛在亚洲发展很快，在中国大陆也出版了不少相关书籍，但鲜见高质量的佳作。所以，在读到此书时，我们非常惊喜，迫切希望中国大陆也能引进这样的好书。2012年初，我们通过作者的推特了解到了本书第二版的出版，一些前辈们踊跃翻译计算机专业书籍的经历也鼓舞了我们，让我们萌生了亲自翻译此书的念头并联系了图灵教育。非常幸运的是，图灵教育也正考虑引进此书，于是有了今天呈现在各位读者面前的简体中文版。
在翻译上，我们力求做到既尊重国内选手的习惯，又符合计算机专业的表述。在修正原书中的一些笔误的同时，加入了一些译者注，以方便国内读者理解。但由于译者水平有限，不足之处在所难免，还望读者多多包涵，并不吝提出意见和建议。
在翻译过程中，秋叶拓哉、岩田阳一和北川宜稔三位作者耐心地对我们的一些疑问和笔误给予了一一解答和确认。浙江大学的陈越、王灿和翁恺三位老师不但将我们领进了“快乐”竞赛的大门，还拨冗审阅了译稿并提出了宝贵的意见。网上不少同好也对本书的出版给予了关切和支持。在此谨对他们表示感谢。
巫泽俊 庄俊元 李津羽
2013年5月6日于浙江大学
本书的几位作者是世界公认的顶尖选手，在竞赛和学术领域都取得了令人瞩目的成就。他们结合自己的专业知识和比赛经验，将自己的心得和技巧集结成书。
全书将不同的算法和例题按专题编排成小节，再将不同的小节由易到难分成四章，这样即便是初出茅庐的新手也不会有太大的阅读障碍。书中涵盖了在程序设计竞赛中会用到的大多数算法和技巧，并在附录中补充了书中未介绍但也比较有用的算法。在题材的安排上，作者取舍得当，主次分明，循序渐进，不以华而不实的奇技淫巧误导读者，又具有一定深度，相信即便是经验丰富的老将同样能从书中有所斩获。本书在结合例题进行讲解时，不是简单地堆砌问题和代码，而是注重引导读者更好地理解和运用算法来分析解决问题。对于正在学习数据结构与算法的读者而言，把它作为一本练习和拓展的参考书也是很好的选择。
本书在日本广受好评，还先后在台湾地区和韩国出版。近年来程序设计竞赛在亚洲发展很快，在中国大陆也出版了不少相关书籍，但鲜见高质量的佳作。所以，在读到此书时，我们非常惊喜，迫切希望中国大陆也能引进这样的好书。2012年初，我们通过作者的推特了解到了本书第二版的出版，一些前辈们踊跃翻译计算机专业书籍的经历也鼓舞了我们，让我们萌生了亲自翻译此书的念头并联系了图灵教育。非常幸运的是，图灵教育也正考虑引进此书，于是有了今天呈现在各位读者面前的简体中文版。
在翻译上，我们力求做到既尊重国内选手的习惯，又符合计算机专业的表述。在修正原书中的一些笔误的同时，加入了一些译者注，以方便国内读者理解。但由于译者水平有限，不足之处在所难免，还望读者多多包涵，并不吝提出意见和建议。
在翻译过程中，秋叶拓哉、岩田阳一和北川宜稔三位作者耐心地对我们的一些疑问和笔误给予了一一解答和确认。浙江大学的陈越、王灿和翁恺三位老师不但将我们领进了“快乐”竞赛的大门，还拨冗审阅了译稿并提出了宝贵的意见。网上不少同好也对本书的出版给予了关切和支持。在此谨对他们表示感谢。
巫泽俊 庄俊元 李津羽
2013年5月6日于浙江大学
前言
如今，形形色色的程序设计竞赛层出不穷，听说过Google Code Jam、TopCoder、ACM-ICPC的读者恐怕不在少数。本书要介绍的正是这类以在规定时间内、又快又准地解决尽可能多的题目为目标的程序设计竞赛。
程序设计竞赛内涵丰富，即便是经验老道的程序员，要想在比赛中取得好成绩也绝非易事。要在程序设计竞赛中取胜，不仅需要运用灵活的想象和丰富的知识得出正确的算法，还需要一气呵成地实现并调试通过。
另一方面，程序设计竞赛对新手而言亦非遥不可及。为了让更多的参赛选手体会到比赛的乐趣，大多数比赛都会准备若干面向初学者的题目。另外，即便未能在比赛中取得好成绩，通过比赛，也能够使自己的能力得到有效的锻炼。最重要的是，大家能够享受到激烈的比赛带来的乐趣。
本书的作者们参加过众多程序设计竞赛，在平时的练习和学习中，也获得了各种各样的知识与技巧，本书将这些知识技巧总结成册，主要介绍算法及其在相关问题中的应用。本书依照由易及难的顺序对问题进行讲解，章节的编排也参考了主题的难易程度及其相互的联系，内容较多的主题则按难易程度划分为多个子主题分别介绍。各个主题由算法介绍和例题讲解穿插而成。
只要是具有编程基础知识的读者，均适合阅读本书。书中的源代码均用C++实现，不过只用到了其基本功能，所以即便读者不熟悉C++也不影响阅读。
关于再版
令人惊喜的是，本书的第1版受到了广大读者的高度评价，在此表示感谢。特别是一些并不热衷于程序设计竞赛的读者也购买了本书。这是因为通过本书不仅可以学到算法，更能学到其设计和运用的思想。这正是本书划时代的亮点。
本书第2版追加了计算几何、搜索减枝、分治法和字符串相关算法4个主题。此外还追加了方便读者加深理解的练习题，并为学有余力的读者列出了书中未涉及的拓展主题，进一步丰富了本书内容。
程序设计竞赛内涵丰富，即便是经验老道的程序员，要想在比赛中取得好成绩也绝非易事。要在程序设计竞赛中取胜，不仅需要运用灵活的想象和丰富的知识得出正确的算法，还需要一气呵成地实现并调试通过。
另一方面，程序设计竞赛对新手而言亦非遥不可及。为了让更多的参赛选手体会到比赛的乐趣，大多数比赛都会准备若干面向初学者的题目。另外，即便未能在比赛中取得好成绩，通过比赛，也能够使自己的能力得到有效的锻炼。最重要的是，大家能够享受到激烈的比赛带来的乐趣。
本书的作者们参加过众多程序设计竞赛，在平时的练习和学习中，也获得了各种各样的知识与技巧，本书将这些知识技巧总结成册，主要介绍算法及其在相关问题中的应用。本书依照由易及难的顺序对问题进行讲解，章节的编排也参考了主题的难易程度及其相互的联系，内容较多的主题则按难易程度划分为多个子主题分别介绍。各个主题由算法介绍和例题讲解穿插而成。
只要是具有编程基础知识的读者，均适合阅读本书。书中的源代码均用C++实现，不过只用到了其基本功能，所以即便读者不熟悉C++也不影响阅读。
关于再版
令人惊喜的是，本书的第1版受到了广大读者的高度评价，在此表示感谢。特别是一些并不热衷于程序设计竞赛的读者也购买了本书。这是因为通过本书不仅可以学到算法，更能学到其设计和运用的思想。这正是本书划时代的亮点。
本书第2版追加了计算几何、搜索减枝、分治法和字符串相关算法4个主题。此外还追加了方便读者加深理解的练习题，并为学有余力的读者列出了书中未涉及的拓展主题，进一步丰富了本书内容。
媒体评论
2.5.5 最小生成树
给定一个无向图，如果它的某个子图中任意两个顶点都互相连通并且是一棵树，那么这棵树就叫做生成树（Spanning Tree）。如果边上有权值，那么使得边权和最小的生成树叫做最小生成树（MST，Minimum Spanning Tree）。
例如我们假设有这样一个图：把顶点看作村庄，边看作计划要修建的道路。为了在所有的村庄间通行，恰好修建村庄数目—1条道路时的情形就对应了一棵生成树。修建道路需要投入建设费，那么求解使得道路建设费用最小的生成树就是最小生成树问题。
常见的求解最小生成树的算法有Kruskal算法和Prim算法。很显然，生成树是否存在和图是否连通是等价的，因此我们假定图是连通的。
1.最小生成树问题1（PrIm算法）
首先我们介绍Prim算法。Prim算法和Dijkstra算法十分相似，都是从某个顶点出发，不断添加边的算法。
首先，我们假设有一棵只包含一个顶点v的树T。然后贪心地选取T和其他顶点之间相连的最小权值的边，并把它加到T中。不断进行这个操作，就可以得到一棵生成树了。接下来我们来证明通过这个方法得到的生成树就是最小生成树。
给定一个无向图，如果它的某个子图中任意两个顶点都互相连通并且是一棵树，那么这棵树就叫做生成树（Spanning Tree）。如果边上有权值，那么使得边权和最小的生成树叫做最小生成树（MST，Minimum Spanning Tree）。
例如我们假设有这样一个图：把顶点看作村庄，边看作计划要修建的道路。为了在所有的村庄间通行，恰好修建村庄数目—1条道路时的情形就对应了一棵生成树。修建道路需要投入建设费，那么求解使得道路建设费用最小的生成树就是最小生成树问题。
常见的求解最小生成树的算法有Kruskal算法和Prim算法。很显然，生成树是否存在和图是否连通是等价的，因此我们假定图是连通的。
1.最小生成树问题1（PrIm算法）
首先我们介绍Prim算法。Prim算法和Dijkstra算法十分相似，都是从某个顶点出发，不断添加边的算法。
首先，我们假设有一棵只包含一个顶点v的树T。然后贪心地选取T和其他顶点之间相连的最小权值的边，并把它加到T中。不断进行这个操作，就可以得到一棵生成树了。接下来我们来证明通过这个方法得到的生成树就是最小生成树。
书摘
2.5.5 最小生成树
给定一个无向图，如果它的某个子图中任意两个顶点都互相连通并且是一棵树，那么这棵树就叫做生成树（Spanning Tree）。如果边上有权值，那么使得边权和最小的生成树叫做最小生成树（MST，Minimum Spanning Tree）。
例如我们假设有这样一个图：把顶点看作村庄，边看作计划要修建的道路。为了在所有的村庄间通行，恰好修建村庄数目—1条道路时的情形就对应了一棵生成树。修建道路需要投入建设费，那么求解使得道路建设费用最小的生成树就是最小生成树问题。
常见的求解最小生成树的算法有Kruskal算法和Prim算法。很显然，生成树是否存在和图是否连通是等价的，因此我们假定图是连通的。
1.最小生成树问题1（PrIm算法）
首先我们介绍Prim算法。Prim算法和Dijkstra算法十分相似，都是从某个顶点出发，不断添加边的算法。
首先，我们假设有一棵只包含一个顶点v的树T。然后贪心地选取T和其他顶点之间相连的最小权值的边，并把它加到T中。不断进行这个操作，就可以得到一棵生成树了。接下来我们来证明通过这个方法得到的生成树就是最小生成树。
给定一个无向图，如果它的某个子图中任意两个顶点都互相连通并且是一棵树，那么这棵树就叫做生成树（Spanning Tree）。如果边上有权值，那么使得边权和最小的生成树叫做最小生成树（MST，Minimum Spanning Tree）。
例如我们假设有这样一个图：把顶点看作村庄，边看作计划要修建的道路。为了在所有的村庄间通行，恰好修建村庄数目—1条道路时的情形就对应了一棵生成树。修建道路需要投入建设费，那么求解使得道路建设费用最小的生成树就是最小生成树问题。
常见的求解最小生成树的算法有Kruskal算法和Prim算法。很显然，生成树是否存在和图是否连通是等价的，因此我们假定图是连通的。
1.最小生成树问题1（PrIm算法）
首先我们介绍Prim算法。Prim算法和Dijkstra算法十分相似，都是从某个顶点出发，不断添加边的算法。
首先，我们假设有一棵只包含一个顶点v的树T。然后贪心地选取T和其他顶点之间相连的最小权值的边，并把它加到T中。不断进行这个操作，就可以得到一棵生成树了。接下来我们来证明通过这个方法得到的生成树就是最小生成树。
