总结与练习 | 基本算法
参考《算法竞赛进阶指南》、AcWing题库
基本算法总结与练习
在本章中, 我们探讨了程序设计的一些基本算法思想。我们曾经多次提到过, 任何问题都有其涉及的范围, 称之为问题的 “状态空间” 。求解一个问题, 就是在这个状态空间里的遍历与映射。递推与递归是遍历状态空间的两种基本形式。本章以及接下来的章节探讨的各种算法, 则是对于 “遍历顺序” “遍历过程中的决策方法” “状态空间中各状态之间的映射方式” 给出的指导。枚举与模拟是按照问题的直接表述形式对状态空间进行朴素的遍历, 搜索则是带有一定的选择性、决策性的遍历, 贪心是在每步决策时采取局部最优策略的遍历, 动态规划则是基于全局考量的分阶段、按维度、无重复遍历。二分、倍增以及与排序相关的一些算法会对状态空间实施划分、等价、代表、拼接等手段, 直接降低遍历时需要面对的时空规模。
本章知识点
位运算
补码表示法, 理解 C++无符号、有符号整数在计算机中的存储方式
各种按位运算, 包括取位、置位、移位等, 以及一些常见技巧
快速幂, 64 位整数乘法
二进制状态压缩, 使用二进制数对状态进行压缩、提取的方法
位运算不进位的特点以及各位之间的独立性
递推与递归
能想象问题 “状态空间”，理解各种基本算法其实是对状态空间的遍历与映射
递推边界、目标、递推公式的发现与设计
理解递归思想、子问题、递归边界、回溯时还原现场
递归实现常见规模的状态空间的遍历
分治思想, 对问题进行划分、递归、再合并
分形, 主要练习对子问题的划分、提取、抽象
递归的机器实现, 转化成非递归的通用方法
前缀和与差分
一维、二维前缀和的递推与应用
差分序列的定义与应用
二分
整数集合二分法、实数域二分法
单峰函数的三分法
二分答案, 把求解转化为判定
排序
各种排序算法, 插入/选择/冒泡/堆/归并/快速/计数/基数/桶排序
离散化
中位数相关问题, 包括货仓选址、环形均分纸牌、动态维护中位数等
求第 大数的 算法
逆序对相关问题, 使用归并排序求逆序对
倍增
序列上的倍增算法及其应用
RMQ-ST 算法
贪心
贪心思想及其证明手段, 主要通过较多题目开拓视野、归纳总结
