程序设计中常用的解题策略PDF|Epub|txt|kindle电子书版本下载

程序设计中常用的解题策略PDF格式电子书版下载

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

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

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

1.1.1 解法1——二分查找最大的下界2

1.1.2 解法2——向下移动“割”3

1.1.3 在两种解法的基础上进一步优化8

1.2 利用最小生成树及其扩展形式解题11

1.2.1 利用最小生成树解题14

1.2.2 最小k度限制生成树的思想和应用23

1.2.3 次小生成树的思想和应用34

1.3 利用线段树解决区间计算问题37

1.3.1 线段树的基本概念37

1.3.2 线段树的基本操作39

1.3.3 应用线段树解题40

1.4 利用伸展树优化动态集合的操作49

1.4.1 伸展树的基本操作50

1.4.2 伸展树的效率分析52

1.4.3 应用伸展树解题54

1.5 利用左偏树实现优先队列的合并58

1.5.1 左偏树的定义和性质58

1.5.2 左偏树的操作59

1.5.3 应用左偏树解题66

1.6 利用“跳跃表”替代树结构69

1.6.1 跳跃表的概况69

1.6.2 跳跃表的基本操作69

1.6.3 跳跃表的效率分析72

1.6.4 应用跳跃表解题74

小结86

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

2.1 利用网络流算法解题87

2.1.1 网络与流的概念87

2.1.2 在增广路径的基础上计算最大流88

2.1.3 利用最大流最小割切定理解题99

2.1.4 求容量有上下界的最大流问题102

2.1.5 计算带费用的流量问题109

2.2 利用图的匹配算法解题120

2.2.1 匹配的基本概念120

2.2.2 计算二分图的匹配122

2.2.3 利用一一对应的匹配性质转化问题128

2.3 利用“分层图思想”解题145

2.3.1 利用“分层图思想”化未知为已知145

2.3.2 利用分层图思想优化算法150

2.4 利用平面图性质解题155

2.4.1 平面图的基本概念155

2.4.2 平面图的应用实例156

2.4.3 偏序集的基本概念166

2.4.4 偏序集的应用实例168

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

小结179

第3章 数据关系上的构造策略181

3.1 选择数据的逻辑结构的基本原则181

3.1.1 充分利用“可直接使用”的信息182

3.1.2 不记录“无用”信息185

3.2 选择数据的存储结构的基本方法191

3.2.1 合理采用顺序存储结构192

3.2.2 必要时采用链式存储结构192

3.3 科学组合多种数据结构198

3.3.1 数据结构的“并联”198

3.3.2 数据结构的“嵌套”204

小结210

第4章 数据统计上的二分策略211

4.1 利用线段树统计数据211

4.1.1 解决一维数据序列的统计问题211

4.1.2 解决二维数据区的统计问题214

4.2 一种解决动态统计的静态方法219

4.2.1 讨论一维序列的求和问题219

4.2.2 二维序列的求和问题221

4.3 在静态二叉排序树上统计数据223

4.3.1 建立静态二叉排序树223

4.3.2 在静态二叉排序树上进行统计224

4.3.3 静态二叉排序树的应用225

4.4 在虚二叉树上统计数据229

小结235

第5章 动态规划上的优化策略236

5.1 减少状态总数的基本策略236

5.1.1 改进状态表示237

5.1.2 选择适当的规划方向240

5.2 减少每个状态决策数的基本策略243

5.2.1 利用最优决策的单调性243

5.2.2 优化决策量253

5.2.3 合理组织状态255

5.2.4 细化状态转移260

5.3 减少状态转移时间的基本策略269

5.3.1 减少决策时间270

5.3.2 减少计算递推式的时间277

小结280

第6章 计算几何上的应对策略282

6.1 应对纯粹计算题的策略探讨282

6.1.1 利用多维线段树解决矩形或长方体几何的计算问题283

6.1.2 利用矩形切割思想进行几何计算和数据统计294

6.1.3 利用极大化思想解决最大子矩形问题307

6.1.4 利用半平面交的算法计算凸多边形319

6.2 应对存在性问题的策略探讨327

6.2.1 直接通过几何计算求解327

6.2.2 转换几何模型求解338

6.3 应对最佳值问题的策略探讨340

6.3.1 采用高效的几何模型341

6.3.2 采用极限法349

6.3.3 采用逼近最佳解的近似算法360

小结362