世界大学生程序设计竞赛（ACM/ICPC）高级教程 第2册 程序设计中常用的解题策略PDF|Epub|txt|kindle电子书版本网盘下载

世界大学生程序设计竞赛（ACM/ICPC）高级教程 第2册 程序设计中常用的解题策略PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第7章 利用树状结构解题的策略1

7.1 解决树的最大一最小划分问题的一般方法1

7.2 利用最小生成树及其扩展形式解题8

7.2.1 利用最小生成树解题10

7.2.2 最小k度限制生成树的思想和应用15

7.2.3 次小生成树的思想和应用18

7.3 利用线段树解决区间计算问题20

7.3.1 线段树的基本概念20

7.3.2 线段树的基本操作21

7.3.3 应用线段树解题23

7.4 利用伸展树优化动态集合的操作27

7.4.1 伸展树的基本操作27

7.4.2 伸展树的效率分析30

7.4.3 应用伸展树解题32

7.5 利用左偏树实现优先队列的合并33

7.5.1 左偏树的定义和性质33

7.5.2 左偏树的操作35

7.5.3 应用左偏树解题41

7.6 利用“跳跃表”替代树结构43

7.6.1 跳跃表的概况43

7.6.2 跳跃表的基本操作44

7.6.3 跳跃表的效率分析47

7.6.4 应用跳跃表解题49

小结53

第8章 利用图形（网状）结构解题的策略54

8.1 利用网络流算法解题54

8.1.1 网络与流的概念54

8.1.2 最大流算法的核心——增广路径57

8.1.3 通过求最大流计算最小割切61

8.1.4 求容量有上下界的最大流问题65

8.1.5 网络流的应用70

8.2 利用图的匹配算法解题76

8.2.1 匹配的基本概念76

8.2.2 计算二分图匹配的方法77

8.2.3 利用一一对应的匹配性质转化问题84

8.2.4 优化匹配算法87

8.3 利用“分层图思想”解题94

8.3.1 利用“分层图思想”构建图论模型94

8.3.2 利用“分层图思想”优化算法96

8.4 利用平面图性质解题102

8.4.1 平面图的概念102

8.4.2 平面图的应用实例103

8.5 正确选择图论模型，优化图的运算106

8.5.1 正确选择图论模型106

8.5.2 在充分挖掘和利用图论模型性质的基础上优化算法111

小结116

第9章 数据关系上的构造策略118

9.1 选择数据逻辑结构的基本原则118

9.1.1 充分利用“可直接使用”的信息119

9.1.2 不记录“无用”信息122

9.2 选择数据存储结构的基本方法125

9.2.1 合理采用顺序存储结构126

9.2.2 必要时采用链式存储结构126

9.3 科学组合多种数据结构128

小结130

第10章 数据统计上的二分策略131

10.1 利用线段树统计数据131

10.2 一种解决动态统计的静态方法135

10.2.1 讨论一维序列的求和问题136

10.2.2 将一维序列的求和问题推广至二维137

10.3 在静态二叉排序树上统计数据138

10.3.1 建立静态二叉排序树138

10.3.2 在静态二叉排序树上进行统计139

10.3.3 静态二叉排序树的应用140

10.4 在虚二叉树上统计数据143

小结147

第11章 动态规划上的优化策略148

11.1 减少状态总数的基本策略149

11.1.1 改进状态表示149

11.1.2 选择适当的规划方向152

11.2 减少每个状态决策数的基本策略153

11.2.1 利用最优决策的单调性154

11.2.2 优化决策量161

11.2.3 合理组织状态163

11.2.4 细化状态转移164

11.3 减少状态转移时间的基本策略166

11.3.1 减少决策时间166

11.3.2 减少计算递推式的时间168

小结170

第12章 计算几何上的应对策略172

12.1 应对纯粹计算题的策略探讨172

12.1.1 利用二重二叉树计算长方体的体积并173

12.1.2 利用多维线段树和矩形切割思想解决平面统计或空间统计问题179

12.1.3 利用极大化思想解决最大子矩形问题188

12.1.4 利用半平面交的算法计算凸多边形197

12.2 应对存在性问题的策略探讨200

12.2.1 直接通过几何计算求解200

12.2.2 转换几何模型求解202

12.3 应对最佳值问题的策略探讨204

12.3.1 采用高效的几何模型204

12.3.2 采用极限法205

12.3.3 采用逼近最佳解的近似算法211

小结212