Skip to content

Latest commit

 

History

History
198 lines (113 loc) · 8.55 KB

010.算法梳理：初级篇.md

File metadata and controls

198 lines (113 loc) · 8.55 KB

原文

算法梳理：初级篇

1.1 说明

本篇为《挑战程序设计竞赛（第2版）》读书笔记系列，旨在：

  • 梳理算法逻辑

  • 探索优化思路

  • 深入代码细节

1.2 目录

初级篇

  1. 穷竭搜索

  2. 贪心

  3. 动态规划

  4. 数据结构

  5. 图论

  6. 数论

1.3 题解

配套习题及详解同步发布在GitHub仓库 acm-challenge-workbook，持续更新。

1.4 题库

Google Code Jam（GCJ） Peking University Online Judge（POJ） CodeForces（CF） LeetCode（LC） Aizu Online Judge（AOJ）

2.1 穷竭搜索

2.1.1 核心思想

  1. 深度优先搜索（DFS）：从某个状态开始，不断转移，直至无法转移，回退到前一步， 再继续转移到其他状态，直到找到最终解。通常采用递归函数或者栈（Stack）来实现。

  2. 宽度优先搜索（BFS）：从初始状态开始，总是先搜索至距离初始状态近的状态。 每个状态都只经过一次，因此复杂度为O(状态数*转移方式数)。通常采用循环或队列（Queue）实现。

2.1.2 优化细节

  1. 特殊状态枚举：可行解空间多数可采用DFS，但当其比较特殊时，可简短地实现。

    • 全排列使用STL中的next_permutation

    • 组合或子集使用位运算

  2. 剪枝：明确知道从当前状态无论如何转移都不会存在解的情况下，不再继续搜索而是直接跳过。

  3. 栈内存与堆内存：

    • main函数中的局部变量存储在栈内存中，统一分配后不再扩大，影响栈深度，与机器设置有关。通常，C++中执行上万次递归是可行的。

    • new或malloc的分配的是堆内存，全局变量存储在堆内存中，使用全局变量代替局部变量可减少栈溢出的风险。

  4. 加深深度优先搜索（IDDFS）：初始的DFS递归深度限制为1，在找到解之前不断增加递归深度。

2.2 贪心

2.2.1 核心思想

  1. 贪心算法：遵循某种规律，不断贪心选取当前最优策略。

  2. 贪心证明：

    • 与其它选择方案相比，该算法并不会得到更差的解（归纳法）

    • 不存在其他的解决方案（反证法）

2.3 动态规划

2.3.1 核心思想

  1. 动态规划（DP）：通过定义某种最优子状态，进行状态间转移达到最终解。

  2. 记忆化搜索：将重复状态通过标记降低复杂度。

  3. 多种形式的DP：搜索的记忆化或利用递推关系的DP，或从状态转移考虑的DP。状态定义和循环顺序都会影响复杂度。

2.3.2 优化细节

  1. 使用memset初始化

  2. 重复循环数组

  3. dp仅bool是一种浪费

  4. 根据规模改变DP对象

2.3.3 经典模型

  1. 背包问题（01背包，完全背包）

  2. 最长子序列（LCS，LIS）

  3. 划分数（第二类Stirling数，Bell数）

2.4 数据结构

2.4.1 核心思想

  1. 优先队列：包含两类操作插入和取值。插入一个数值，获取最小值并删除。堆可高效实现优先队列。

  2. 堆：儿子的值一定不小于父亲的值的一种二叉树。插入时先在堆末插入，不断上移直至无大小颠倒。取值时，删除最小值， 将堆末节点复制到根，不断下移直至无大小颠倒。插入和取值复杂度都为O(logn)。

  3. 二叉搜索树：对所有节点都满足，左子树上的所有节点比自己小，右子树上的所有节点比自己大。 插入与查询类似二分，删除时将删除节点左子树最大值或右子树（无左子树时）上移，每种操作复杂度都为O(logn)。

  4. 并查集：一种管理元素分组情况的数据结构。可以查询两个元素是否同组，可以合并两组元素，但不能进行分割操作。 一次操作复杂度为阿克曼函数反函数a(n)，比O(logn)快。

2.4.2 优化细节

  1. 平衡二叉树（AVL）：当左右子树深度差超过1时，将更深的子树旋转上移，达到整棵树的平衡，避免二查搜索树退化后复杂度升至O(n)。

  2. 路径压缩：并查集向上的递归操作中，沿途所有节点一旦向上走到一次根节点，就把其到父亲的边直接连向根。

  3. 并查集的同组：广义可表示组内所有元素代表的情况同时发生或不发生。

  4. STL标准库：

    • 优先队列：priority_queue（默认根为最大值）

    • 二查搜索树：set（集合）、map（键和值对应）、multiset和multimap（可存放重复键值）

2.5 图论

2.5.1 核心思想

  1. 图：顶点集合为V、边集为E的图记作G=(V,E)，从u到v的边记作e=(u,v)。根据边是否有向分为有向图和无向图， 根据是否有环分为有环图和无环图。图可由邻接表和邻接矩阵两种方式表示。

  2. Bellman-Ford算法（单源最短路）：记录起点到每个点i的最短距离d[i]，用所有的边条件持续更新d[i]， 直到每个d[i]都已经为最小无法更新。图可包含负权边，包含负环的判断方法为将所有d[i]初始化为0，第V次d[i]是否仍存在更新。复杂度为O(EV)。

  3. Dijkstra算法（单源最短路）：从起点出发<s, d[s]=0>出发，更新s所有可到达的边j，若d[j]有更新， 则加入最小堆，以便下次找到剩余集合中d[i]最小的点i，再从i出发BFS，直到到达终点t。不能处理包含负权边的图。复杂度为O(ElogV)。

  4. Floyd-Warshall算法（多源最短路）：定义从i到j且经过k的最短路为d[i][j]用d[i][k]+d[k][j]来更新， 三重循环直接得到任意两点间的最短路。图可包含负权边，包含负环的判断方法为是否存在顶点i使d[i][i]为负。复杂度O(V^3)。

  5. Prim算法（最小生成树）：假设V的子集X已经构造了部分最小生成树，那么接下来就是选取从X到X的补集中权值最小的边加入。 可使用最小堆维护待选的边，复杂度为O(ElogV)。

  6. Kruskal算法（最小生成树）：将所有边升序排列，依次取出每条最小的边， 若该边的两个端点不在相同并查集内，则将该边加入最小生成树，并将两点用并查集连接。 耗时最多的操作为边的排序，复杂度O(ElogE)。

2.5.2 优化细节

  1. 最短路本质是动态规划，最小生成树本质是贪心。

  2. Bellman-Ford算法和Floyd-Warshall算法可处理包含负权边的图，并结合各自特性判断是否存在负环。

  3. 差分约束：将不等式组转化为包含负权边的单源最短路问题，一般采用Bellman-Ford方法解决。 若d[i]+x>=d[j]，则创建有向边e(i,j)=x。从起点s到终点t的最短路d[t]为s和t允许的最大差。 若存在负环，则不等式组无解；若d[t]=INF，则s和t相差可任意。

2.6 数论

2.6.1 核心思想

  1. 辗转相除算法（最小公约数）：gcd(a,b)=gcd(b,a%b)，循环至b为0，此时得到最小公约数为a。

  2. 扩展欧几里德算法（解二元一次方程）：求解ax+by=gcd(a,b)，类似辗转相除法。 求extgcd(a,b,&x,&y)时，递归求得d=extgcd(b,a%b,y,x)的解存入y和x。则ax+by=gcd(a,b)的解为x和y-(a/b)*x。

  3. 素数筛法：通过已求得的素数，将所求范围内所有该素数的倍数都标记为合数。 依序遍历空间，未被筛掉的即为新的素数。复杂度O(nloglogn)，可看作线性的。

  4. 反复平方法（快速幂）：求x的n次幂，可二分递归求x的n/2次幂，即x^n=(x^(n/2))^2 * x^(n&1)。复杂度为O(logn)。

2.6.2 优化细节

  1. ax+by=gcd(a,b)的解大小：x的绝对值不大于b，y的绝对值不大于a。 若要求得满足某个范围的解，可通过参数k调节，x+=k(b/d)、y-=k(a/d)为原方程的解簇。

  2. 线性素数筛法：遍历解空间，无论当前数是否为素数，将已经求得得素数集合中的数乘以它得到合数标记筛去。 并且若该数为合数，它乘以的素数为它的因子，则对该数不再继续循环已有的素数集合。 上述可保证，每个合数都只通过乘以它最小的因子得到，即复杂度为线性。 注意，该方法使得已有的素数集合中的组合并不一定被立即筛去，在以后遍历到特定合数时才会被标记。

  3. 模运算：用64位处理对32数的模，避免发生溢出。模运算对加减乘可以直接应用， 但对同模的两边做除法时，若原始ac=bc(mod m)，则a-b=m*k/c，则a=b(mod m/gcd(m,c))。