编辑推荐
                                         世界程序设计高手的经验总结
  【ACM-ICPC全球总冠军】巫泽俊主译
  日本ACM-ICPC参赛者人手一册
      内容简介
     《挑战程序设计竞赛(第2版)》对程序设计竞赛中的基础算法和经典问题进行了汇总,分为准备篇、初级篇、中级篇与高级篇4章。作者结合自己丰富的参赛经验,对严格筛选的110 多道各类试题进行了由浅入深、由易及难的细致讲解,并介绍了许多实用技巧。每章后附有习题,供读者练习,巩固所学。      
作者简介
     ★秋叶拓哉 
  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;实验室从事科研工作     
内页插图
          目录
   第1章 蓄势待发--准备篇   
1.1  何谓程序设计竞赛   
1.2  最负盛名的程序设计竞赛   
1.2.1  世界规模的大赛--Google Code Jam(GCJ)   
1.2.2  向高排名看齐!--TopCoder   
1.2.3  历史最悠久的竞赛-- ACM-ICPC   
1.2.4  面向中学生的信息学奥林匹克竞赛--JOI-IOI   
1.2.5  通过网络自动评测--Online Judge(OJ)   
1.3  本书的使用方法   
1.3.1  本书所涉及的内容   
1.3.2  所用的编程语言   
1.3.3  题目描述的处理   
1.3.4  程序结构   
1.3.5  练习题   
1.3.6  读透本书后更上一层楼的练习方法   
1.4  如何提交解答   
1.4.1  POJ的提交方法   
1.4.2  GCJ的提交方法   
1.5  以高效的算法为目标   
1.5.1  什么是复杂度   
1.5.2  关于运行时间   
1.6  轻松热身   
1.6.1  先从简单题开始   
1.6.2  POJ的题目Ants   
1.6.3  难度增加的抽签问题    
第2章 初出茅庐--初级篇   
2.1  最基础的“穷竭搜索”   
2.1.1  递归函数   
2.1.2  栈   
2.1.3  队列   
2.1.4  深度优先搜索   
2.1.5  宽度优先搜索   
2.1.6  特殊状态的枚举   
2.1.7  剪枝   
2.2  一往直前!贪心法   
2.2.1  硬币问题   
2.2.2  区间问题   
2.2.3  字典序最小问题   
2.2.4  其他例题   
2.3  记录结果再利用的“动态规划”   
2.3.1  记忆化搜索与动态规划   
2.3.2  进一步探讨递推关系   
2.3.3  有关计数问题的DP   
2.4  加工并存储数据的数据结构   
2.4.1  树和二叉树   
2.4.2  优先队列和堆   
2.4.3  二叉搜索树   
2.4.4  并查集   
2.5  它们其实都是“图”   
2.5.1  图是什么   
2.5.2  图的表示   
2.5.3  图的搜索   
2.5.4  最短路问题   
2.5.5  最小生成树   
2.5.6  应用问题   
2.6  数学问题的解题窍门   
2.6.1  辗转相除法   
2.6.2  有关素数的基础算法   
2.6.3  模运算   
2.6.4  快速幂运算   
2.7  一起来挑战GCJ的题目(1)   
2.7.1  Minimum Scalar Product   
2.7.2  Crazy Rows   
2.7.3  Bribe the Prisoners   
2.7.4  Millionaire    
第3章 出类拔萃--中级篇   
3.1  不光是查找值!“二分搜索”   
3.1.1  从有序数组中查找某个值   
3.1.2  假定一个解并判断是否可行   
3.1.3  最大化最小值   
3.1.4  最大化平均值   
3.2  常用技巧精选(一)   
3.2.1  尺取法   
3.2.2  反转(开关问题)   
3.2.3  弹性碰撞   
3.2.4  折半枚举(双向搜索)   
3.2.5  坐标离散化   
3.3  活用各种数据结构   
3.3.1  线段树   
3.3.2  Binary Indexed Tree   
3.3.3  分桶法和平方分割   
3.4  熟练掌握动态规划   
3.4.1  状态压缩DP   
3.4.2  矩阵的幂   
3.4.3  利用数据结构高效求解   
3.5  借助水流解决问题的网络流   
3.5.1  最大流   
3.5.2  最小割   
3.5.3  二分图匹配   
3.5.4  一般图匹配   
3.5.5  匹配、边覆盖、独立集和顶点覆盖   
3.5.6  最小费用流   
3.5.7  应用问题   
3.6  与平面和空间打交道的计算几何   
3.6.1  计算几何基础   
3.6.2  极限情况   
3.6.3  平面扫描   
3.6.4  凸包   
3.6.5  数值积分   
3.7  一起来挑战GCJ的题目(2)   
3.7.1  Numbers   
3.7.2  No Cheating   
3.7.3  Stock Charts   
3.7.4  Watering Plants   
3.7.5  Number Sets   
3.7.6  Wi-fi Towers    
第4章 登峰造极--高级篇   
4.1  更加复杂的数学问题   
4.1.1  矩阵   
4.1.2  模运算的世界   
4.1.3  计数   
4.1.4  具有对称性的计数   
4.2  找出游戏的必胜策略   
4.2.1  游戏与必胜策略   
4.2.2  Nim   
4.2.3  Grundy数   
4.3  成为图论大师之路   
4.3.1  强连通分量分解   
4.3.2  2-SAT   
4.3.3  LCA   
4.4  常用技巧精选(二)   
4.4.1  栈的运用   
4.4.2  双端队列的运用   
4.4.3  倍增法   
4.5  开动脑筋智慧搜索   
4.5.1  剪枝   
4.5.2  A*与IDA*   
4.6  划分、解决、合并:分治法   
4.6.1  数列上的分治法   
4.6.2  树上的分治法   
4.6.3  平面上的分治法   
4.7  华丽地处理字符串   
4.7.1  字符串上的动态规划算法   
4.7.2  字符串匹配   
4.7.3  后缀数组   
4.8  一起来挑战GCJ的题目(3)   
4.8.1  Mine Layer   
4.8.2  Year of More Code Jam   
4.8.3  Football Team   
4.8.4  Endless Knight   
4.8.5  The Year of Code Jam   
本书中未涉及的拓展主题   
书中例题列表   
参考文献      
精彩书摘
       2.5.5 最小生成树 
    给定一个无向图,如果它的某个子图中任意两个顶点都互相连通并且是一棵树,那么这棵树就叫做生成树(Spanning Tree)。如果边上有权值,那么使得边权和最小的生成树叫做最小生成树(MST,Minimum Spanning Tree)。 
    例如我们假设有这样一个图:把顶点看作村庄,边看作计划要修建的道路。为了在所有的村庄间通行,恰好修建村庄数目—1条道路时的情形就对应了一棵生成树。修建道路需要投入建设费,那么求解使得道路建设费用最小的生成树就是最小生成树问题。 
    常见的求解最小生成树的算法有Kruskal算法和Prim算法。很显然,生成树是否存在和图是否连通是等价的,因此我们假定图是连通的。 
    1.最小生成树问题1(PrIm算法) 
    首先我们介绍Prim算法。Prim算法和Dijkstra算法十分相似,都是从某个顶点出发,不断添加边的算法。 
    首先,我们假设有一棵只包含一个顶点v的树T。然后贪心地选取T和其他顶点之间相连的最小权值的边,并把它加到T中。不断进行这个操作,就可以得到一棵生成树了。接下来我们来证明通过这个方法得到的生成树就是最小生成树。       
前言/序言
     如今,形形色色的程序设计竞赛层出不穷,听说过Google Code Jam、TopCoder、ACM-ICPC的读者恐怕不在少数。本书要介绍的正是这类以在规定时间内、又快又准地解决尽可能多的题目为目标的程序设计竞赛。 
  程序设计竞赛内涵丰富,即便是经验老道的程序员,要想在比赛中取得好成绩也绝非易事。要在程序设计竞赛中取胜,不仅需要运用灵活的想象和丰富的知识得出正确的算法,还需要一气呵成地实现并调试通过。 
  另一方面,程序设计竞赛对新手而言亦非遥不可及。为了让更多的参赛选手体会到比赛的乐趣,大多数比赛都会准备若干面向初学者的题目。另外,即便未能在比赛中取得好成绩,通过比赛,也能够使自己的能力得到有效的锻炼。最重要的是,大家能够享受到激烈的比赛带来的乐趣。 
  本书的作者们参加过众多程序设计竞赛,在平时的练习和学习中,也获得了各种各样的知识与技巧,本书将这些知识技巧总结成册,主要介绍算法及其在相关问题中的应用。本书依照由易及难的顺序对问题进行讲解,章节的编排也参考了主题的难易程度及其相互的联系,内容较多的主题则按难易程度划分为多个子主题分别介绍。各个主题由算法介绍和例题讲解穿插而成。 
  只要是具有编程基础知识的读者,均适合阅读本书。书中的源代码均用C++实现,不过只用到了其基本功能,所以即便读者不熟悉C++也不影响阅读。 
  【关于再版】 
  令人惊喜的是,本书的第1版受到了广大读者的高度评价,在此表示感谢。特别是一些并不热衷于程序设计竞赛的读者也购买了本书。这是因为通过本书不仅可以学到算法,更能学到其设计和运用的思想。这正是本书划时代的亮点。 
  本书第2版追加了计算几何、搜索减枝、分治法和字符串相关算法4个主题。此外还追加了方便读者加深理解的练习题,并为学有余力的读者列出了书中未涉及的拓展主题,进一步丰富了本书内容。     
				
 
				
				
					《代码的艺术:从像素到算法的奇妙旅程》  在数字世界的光影交织中,隐藏着无数由逻辑与创意构筑的奇迹。它们驱动着我们日常使用的应用程序,支撑着我们畅游的互联网,甚至塑造着我们探索未知宇宙的科学前沿。《代码的艺术:从像素到算法的奇妙旅程》并非一本教授具体编程语言语法的教科书,也不是一本枯燥的算法理论大全。相反,它是一扇通往理解计算机思维方式的窗口,一次深入探索“如何让计算机思考”的旅程,一次揭示那些看似“聪明”的软件背后深层原理的深度剖析。  这本书旨在激发你对计算机科学的兴趣,引导你超越表面的“调用函数”和“编写脚本”,去感受代码背后的思想深度和解决问题的巧妙智慧。我们将从最基础的“指令”开始,如同孩童学习字母,但这里的字母并非咿呀学语,而是二进制的0和1,它们组合起来,构成了计算机能够理解的语言。我们将一同探索,这些看似简单的指令,是如何层层叠加,最终演变成我们今天所见的复杂而强大的软件系统。  第一部分:思维的基石——指令的构建与逻辑的舞蹈  在这一部分,我们将一同深入了解计算机如何执行指令。这并非关于汇编语言的晦涩难懂,而是关于指令集架构(ISA)的根本思想:计算机的核心是如何理解和响应我们赋予它的任务的?我们将探讨指令的类型,如数据传输、算术运算、逻辑判断和流程控制,理解它们在程序执行中的作用。例如,一个简单的“加法”指令,在计算机内部是如何实现的?它涉及到哪些逻辑门电路的协同工作?我们将从宏观层面理解指令的抽象,然后逐步深入到微观的执行过程,帮助读者建立起计算机执行任务的直观感受。  接着,我们将聚焦于“逻辑”——这正是计算机思维的核心。我们将探讨布尔逻辑,理解AND、OR、NOT等基本逻辑运算如何构成复杂的决策机制。但更重要的是,我们将看到这些逻辑如何通过“条件语句”(if-then-else)和“循环语句”(for, while)等程序结构,被编织成能够处理现实世界复杂问题的“算法”。我们会用生动的例子,比如如何设计一个简单的扑克牌洗牌算法,或者一个自动分类邮件的逻辑,来展现逻辑在程序设计中的强大力量。这不是关于死记硬背算法的定义,而是关于如何运用逻辑思维去分析问题,并将其转化为计算机可执行的步骤。  第二部分:数据的世界——存储、组织与高效利用  程序的核心在于处理数据。本部分将带你领略数据在计算机中的奇妙旅程。我们将从最基础的数据类型(整数、浮点数、字符等)出发,理解它们在内存中是如何被表示和存储的。随后,我们将进入数据结构的殿堂,学习如何有效地组织和管理数据,使其能够被快速访问和修改。  你将了解到,为何一个简单的数组(Array)在某些场景下表现出色,而在另一些场景下却显得力不从心。我们将探索链表(Linked List),理解它在动态数据管理中的灵活性。你还会接触到栈(Stack)和队列(Queue)这些具有特定访问规则的数据结构,并看到它们在解决实际问题(如函数调用栈、任务调度)中的应用。  更深入地,我们将探讨树(Tree)和图(Graph)这些更复杂但功能强大的数据结构。我们会用形象的比喻,比如家族树来解释树结构的层级关系,用社交网络来描绘图结构的节点和连接。理解这些数据结构的内在联系,将使你能够以更高效的方式存储和检索信息,为解决更复杂的问题奠定基础。例如,在一个大型电商网站中,如何用图结构来存储商品之间的关联,以便进行“猜你喜欢”的推荐?这些都是我们将要探索的内容。  第三部分:算法的智慧——优化、设计与问题求解的艺术  一旦数据被合理组织,算法就成为了发挥其价值的关键。本部分将深入探讨算法的设计与优化,让你领略解决问题时的“优雅”与“高效”。我们将不拘泥于具体的算法名称,而是专注于算法的思想和策略。  你将了解到,为何有些算法在处理大量数据时速度惊人,而有些则会变得不堪重负。我们会探讨“分治”(Divide and Conquer)的思想,比如如何将一个巨大的问题分解成若干个小的、易于解决的子问题,然后将它们的解组合起来。你还会看到“贪心算法”(Greedy Algorithms)的魅力,它们在每一步都做出局部最优的选择,有时也能导向全局最优解。  搜索算法(Search Algorithms)和排序算法(Sorting Algorithms)是算法世界的基石。我们将从最直观的线性搜索和冒泡排序开始,逐步介绍二分搜索、快速排序、归并排序等更高效的方法。但关键在于理解它们背后的原理:为什么二分搜索需要有序的数据?为什么快速排序在大多数情况下比冒泡排序快得多?我们将通过可视化的讲解和实际的类比,让你深刻理解算法的时间复杂度和空间复杂度,从而学会如何根据问题规模选择最合适的算法。  我们还将触及图算法的强大之处,例如最短路径算法(如Dijkstra算法)如何帮助我们找到两个城市之间的最短驾车路线,最小生成树算法(如Prim算法或Kruskal算法)如何在构建网络时达到成本最小化。这些算法不仅仅是理论的堆砌,而是解决现实世界问题的强大工具。  第四部分:软件的架构——组织、协作与可维护性  代码的艺术不仅仅在于解决单个问题,更在于构建一个能够长期运行、易于理解和扩展的软件系统。本部分将引导你思考软件的整体架构和组织方式。  我们将探讨模块化(Modularity)的思想,理解为何将庞大的程序分解成独立、可复用的模块是如此重要。你将学习到“接口”(Interface)和“抽象”(Abstraction)的概念,它们是如何帮助我们隐藏实现的细节,专注于功能的实现。  我们将讨论面向对象编程(Object-Oriented Programming, OOP)的基本原则,比如封装(Encapsulation)、继承(Inheritance)和多态(Polymorphism)。这些概念并非为了学习一门特定的编程范式,而是为了理解如何通过更具结构化的方式来组织代码,使其更易于管理和维护。例如,为何在设计一个游戏时,将“角色”、“道具”、“场景”等概念抽象成类(Class)会比杂乱无章的代码更有效?  我们还会触及一些软件工程的基本原则,例如代码的可读性、文档的重要性以及版本控制(Version Control)的必要性。理解这些,能够帮助你更好地参与到团队协作中,构建出健壮、可扩展的软件。  第五部分:代码的未来——并行、并发与智能的可能性  随着计算能力的飞速发展,我们正进入一个多核处理器和分布式系统的时代。本部分将展望代码的未来,探索如何利用并行和并发来提升程序的性能。  你将了解到,为何在多核处理器上,简单地复制代码并不能带来成倍的性能提升。我们将介绍线程(Thread)和进程(Process)的概念,理解它们在执行并行任务中的作用。你还会接触到并发编程中的挑战,比如如何处理多个任务同时访问共享数据时可能出现的“竞态条件”(Race Condition),以及如何使用锁(Lock)和其他同步机制来保证数据的正确性。  我们还将触及一些更前沿的概念,比如函数式编程(Functional Programming)的思想,它如何通过不可变数据和纯函数来简化并发程序的编写。最后,我们将简要探讨人工智能(AI)和机器学习(ML)的底层逻辑,理解它们是如何通过大量的数据和复杂的算法来模拟人类的智能,并为未来的软件开发带来无限可能。  结语:不止于代码,更在于思维  《代码的艺术:从像素到算法的奇妙旅程》并非一本让你成为编程大师的速成指南,也不是一本告诉你如何写出“炫酷”程序的秘籍。它更像是一次引人入胜的思维训练,一次对计算机科学核心思想的深度探索。通过本书,你将学会如何用一种全新的视角去审视我们周围的数字世界,理解那些驱动着现代文明的“看不见的手”。  这本书的价值在于,它能够帮助你培养一种解决问题的能力,一种将复杂现实转化为清晰逻辑步骤的能力,一种用严谨思维去构建解决方案的能力。无论你未来是否会成为一名程序员,这种思维方式都将是你宝贵的财富,帮助你在任何领域都能游刃有余。准备好踏上这段奇妙的旅程了吗?让我们一起,用代码的艺术,去探索无限的可能。