0x08 总结与练习

在本章中，我们探讨了程序设计的一些基本算法思想。我们曾经多次提到过，任何问题都有其涉及的范围，称之为问题的“状态空间”。求解一个问题，就是在这个状态空间里的遍历与映射。递推与递归是遍历状态空间的两种基本形式。本章以及接下来的章节探讨的各种算法，则是对于“遍历顺序”“遍历过程中的决策方法”“状态空间中各状态之间的映射方式”给出的指导。枚举与模拟是按照问题的直接表述形式对状态空间进行朴素的遍历，搜索则是带有一定的选择性、决策性的遍历，贪心是在每步决策时采取局部最优策略的遍历，动态规划则是基于全局考量的分阶段、按维度、无重复遍历。二分、倍增以及与排序相关的一些算法会对状态空间实施划分、等价、代表、拼接等手段，直接降低遍历时需要面对的时空规模。

$\spadesuit$ 本章知识点

位运算

补码表示法，理解 C++ 无符号、有符号整数在计算机中的存储方式。各种按位运算，包括取位、置位、移位等，以及一些常见技巧。快速幂，64 位整数乘法二进制状态压缩，使用二进制数对状态进行压缩、提取的方法

枚举、模拟、递推

能想象问题“状态空间”，理解各种基本算法其实是对状态空间的遍历与映射
常见的枚举形式，无法设计有效算法时能够通过枚举的方式直接遍历状态空间
通过模拟，主要侧重代码实现能力的训练
递推边界、目标、递推公式的发现与设计
一维、二维前缀和的递推与应用

递归

理解递归思想、子问题、递归边界、回溯时还原现场
递归实现常见规模的状态空间的遍历
分治思想，对问题进行划分、递归、再合并
分形，主要练习对子问题的划分、提取、抽象
递归的机器实现，转化成非递归的通用方法

二分

整数集合二分法、实数域二分法单峰函数的三分法二分答案，把求解转化为判定

排序

各种排序算法，插入/选择/冒泡/堆/归并/快速/计数/基数/桶排序离散化

中位数相关问题，包括货仓选址、环形均分纸牌、动态维护中位数等
求第 $k$ 大数的 $0(N)$ 算法
逆序对相关问题，使用归并排序求逆序对

倍增

序列上的倍增算法及其应用RMQ-ST算法

贪心

贪心思想及其证明手段，主要通过较多题目开拓视野、归纳总结

$\spadesuit$ 练习

1. 完成本章中所有例题的代码实现

2. The Pilots Brothers' Refrigerator

题目地址：POJ2965，提示：枚举/位运算

1. 占卜 DIY

题目地址：TYVJ1424，提示：模拟

1. Fractal

题目地址：POJ2083，提示：递归/分形

5.Raid

题目地址：POJ3714，提示：分治/平面最近点对

6.秦腾与教学评估

题目地址：BZOJ1271，提示：二分

1. Corral the Cows

题目地址：POJ3179，提示：二分/离散化/前缀和

1. 糖果传递

题目地址：BZOJ1045，提示：排序/中位数/环形均分纸牌

1. Soldiers

题目地址：POJ1723，提示：排序/中位数/货仓选址问题扩展

1. Number Base Conversion

题目地址：POJ1220，提示：高精度运算/进制转换

1. To the Max

题目地址：POJ1050，提示：贪心

1. Task

题目地址：HDOJ4864，提示：贪心