小苏子
小苏子PDF在线图书

挑战程序设计竞赛(第2版) 内容简介

挑战程序设计竞赛(第2版) 内容简介

挑战程序设计竞赛(第2版) 目录

挑战程序设计竞赛(第2版) 精彩文摘

《挑战程序设计竞赛(第2版)》对程序设计竞赛中的基础算法和经典问题进行了汇总,分为准备篇、初级篇、中级篇与高级篇4章。作者结合自己丰富的参赛经验,对严格筛选的110 多道各类试题进行了由浅入深、由易及难的细致讲解,并介绍了许多实用技巧。每章后附有习题,供读者练习,巩固所学。第1章 蓄势待发–准备篇1.1  何谓程序设计竞赛1.2  最负盛名的程序设计竞赛1.2.1  世界规模的大赛–Google Code Jam(GCJ)1.2.2  向高排名看齐!–TopCoder1.2.3  历史最悠久的竞赛– ACM-ICPC1.2.4  面向中学生的信息学奥林匹克竞赛–JOI-IOI1.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的题目Ants1.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  有关计数问题的DP2.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 Product2.7.2  Crazy Rows2.7.3  Bribe the Prisoners2.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 Tree3.3.3  分桶法和平方分割3.4  熟练掌握动态规划3.4.1  状态压缩DP3.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  Numbers3.7.2  No Cheating3.7.3  Stock Charts3.7.4  Watering Plants3.7.5  Number Sets3.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  Nim4.2.3  Grundy数4.3  成为图论大师之路4.3.1  强连通分量分解4.3.2  2-SAT4.3.3  LCA4.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 Layer4.8.2  Year of More Code Jam4.8.3  Football Team4.8.4  Endless Knight4.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中。不断进行这个操作,就可以得到一棵生成树了。接下来我们来证明通过这个方法得到的生成树就是最小生成树。

赞(0)
未经允许不得转载:小苏子图书 » 挑战程序设计竞赛(第2版) 内容简介