算法竞赛进阶指南

《算法竞赛进阶指南》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、0x00基本算法本章知识点位运算补码表示法，理解C++无符号、有符号整数在计算机中的存储方式各种按位运算，包括取位、置位、移位等，以及一些常见技巧快速幂，64位整数乘法二进制状态压缩，使用二进制数对状态进行压缩、提取的方法枚举、模拟、递推能想象问题“状态空间”，理解各种基本算法其实是对状态空间的遍历与映射常见的枚举形式，无法设计有效算法时能够通过枚举的方式直接遍历状态空间通过模拟，主要侧重代码实现能力的训练递推边界、目标、递推公式的发现与设计一维、二维前缀和的递推与应用递归理解递归思想、子问题、递归边界、回溯时还原现场递归实现常见规模的状态

2、空间的遍历分治思想，对问题进行划分、递归、再合并分形，主要练习对子问题的划分、提取、抽象递归的机器实现，转化成非递归的通用方法二分整数集合二分法、实数域二分法单峰函数的三分法二分答案，把求解转化为判定排序各种排序算法，插入/选择/冒泡/堆/归并/快速/计数/基数/桶排序离散化中位数相关问题，包括货仓选址、环形均分纸牌、动态维护中位数等求第?大数的O(?)算法逆序对相关问题，使用归并排序求逆序对倍增序列上的倍增算法及其应用RMQ-ST算法贪心贪心思想及其证明手段，主要通过较多题目开拓视野、归纳总结0x10基本数据结构本章知识点栈栈的基本实现，

3、使用数组和栈顶位置变量模拟一个栈栈的灵活应用，例如使用辅助栈保存额外信息、对顶栈等表达式计算，后缀表达式、中缀转后缀、中缀表达式递归求值单调栈队列一般队列、双端队列、循环队列的基本实现单调队列，理解使用单调性处理问题的思想链表与邻接表双向链表的实现与操作，以及数组模拟链表邻接表结构，图和树的邻接表存储与遍历HashHash表，使用邻接表结构实现开散列法字符串Hash，前缀与区间Hash值、二分法的结合字符串KMP模式匹配算法，????数组的灵活运用最小表示法，循环同构问题TrieTrie的插入、检索等基本操作Trie与xor问题二叉堆二叉堆的

4、基本操作及其实现，Insert、GetTop、Extract、Remove等二叉堆的灵活应用，与贪心算法相结合，数据结构间“建立映射”的思想?叉Huffman树与Huffman编码0x20搜索本章知识点树与图的遍历树与图的深度优先遍历，树的DFS序、深度、重心，图的连通块划分树与图的广度优先遍历，拓扑排序，bitset优化的可达性统计深度优先搜索深搜的三种基本递归形式，经典的子集和、全排列、N皇后问题等深搜框架的设计与实现，搜索树理论剪枝剪枝的设计思想与实现优化搜索顺序、排除等效冗余、可行性与最优性剪枝、记忆化等常见剪枝手法迭代加深迭代加深

5、思想，迭代加深DFS（ID-DFS）双向搜索思想，双向DFS广度优先搜索广搜框架的设计与实现，熟练使用记录数组判重、方向常数数组等广搜的常见问题类型，如走地图、多起点BFS、双重BFS等广搜变形双端队列BFS，双向BFS优先队列BFS，理解并能根据每次扩展代价的实际情况选择正确的BFS形式A*估价函数的设计准则，估值f(state)≤未来实际代价g(state)A*算法的实现，A*=优先队列BFS+估价函数IDA*IDA*算法的实现，IDA*=迭代加深DFS+估价函数0x30数学知识本章知识点质数质数的判定，试除法质数的筛选，Eratost

6、henes筛法、线性筛法算术基本定理，试除法分解质因数约数算术基本定理的约数个数推论、约数和推论试除法求约数，倍数法求1~N每个数的约数集合最大公约数，最小公倍数，更相减损术，欧几里得算法欧拉函数的定义与基本性质，积性函数的定义与基本性质试除法计算欧拉函数，Eratosthenes筛法与线性筛法快速递推欧拉函数同余同余、同余类、剩余系的定义费马小定理，欧拉定理及其推论Bezout定理，扩展欧几里得算法乘法逆元的计算与应用线性同余方程、方程组的求解，中国剩余定理高次同余方程中指数的求解，BabyStep,GiantStep算法矩阵乘法矩阵乘法运

7、算与基本性质矩阵乘法加速递推，状态矩阵、转移矩阵的构造方法高斯消元与线性空间系数矩阵、增广矩阵、主元、自由元、初等行变换等概念高斯消元的实现，方程组唯一解、多解、无解的判断线性空间的相关概念，高斯消元求线性空间的基线性空间的推广，异或空间的性质与应用，去重与不去重异或空间的形态组合计数加法原理，乘法原理，排列数，组合数及其性质组合数的递推求法、逆元求法、分解质因数约分求法二项式定理，Lucas定理多重集的排列数和组合数Catalan数列的定义和应用容斥原理与Möbius函数容斥原理的理解与应用多重集组合数的完整解析Mobius函数的定义、计算

8、与应用概率与数学期望随机变量、概率、数学期望等相关定义数学期望的线性性质，数学期望的递推计算，数学期望与动态规划的结合0/1分数规划0/1分数规划模型与二分法求解博