5.并查集并查集结构能够支持快速进行如下的操作： 将两个集合合并 询问两个元素是否在一个集合当中 并查集可以在近乎O(1)的时间复杂度下，完成上述2个操作 并查集的基本原理：用树的形式来维护一个集合。用树的根节点来代表这个集合。对于树中的每个节点...

4.前缀和与差分1.一维前缀和一维前缀和：S[i]=a1+a2+a3+a4+…..+ai，要求a从a1开始，且S[0]=0 前缀和的作用：给定一组序列数据，可以计算任意第l个数到第r个数的和，S[r]-S[l-1]（这里就解释了...

5.双指针算法主要思想： 针对单一序列使用两个指针，如快速排序 针对不同的两个序列使用两个指针，如归并排序 双指针算法可以实现对暴力（朴素）算法的优化，使时间复杂度由O(n^2)优化到O(n)，要求序列有单调关系 代码模板 123456for(i...

6.位运算主要思想： 获取一个数的二进制的第k位：x>>k & 1，将x右移k位即第k位就移动到最低有效位，每次右移后的数与1做按位与运算，只会保留最低有效位即第k位的二进制数。如x=10111，x>>2，...

8.C++中的STL(标准模板库)（1）vector, 变长数组，倍增的思想 头文件 #include <vector> ​ size() 返回元素个数 ​ empty() 返回是否为空 ​ clear(...

2.树与图的遍历、拓扑排序 树和图的存储首先，树是一种特殊的图（无环连通图）。所以，这里只说图的存储即可。 首先，图分为2种，有向图和无向图。 有向图中2个点之间的边是有方向的，比如a -> b，则只能从a点走到b点，无法从b点走到a点。 无向...

3.最短路径 单源最短路 多源汇最短路在最短路问题中，源点 也就是 起点，汇点 也就是 终点 单源最短路单源最短路，指的是求一个点，到其他所有点的最短距离。（起点是固定的，单一的） 所有边权都是正数 朴素Dijkstra O(n^2)，基于贪心 ...

4.最小生成树最小生成树：由n个节点，和n-1条边构成的无向连通图被称为G的一颗生成树，在G的所有生成树中，边的权值之和最小的生成树，被称为G的最小生成树。(换句话说就是用最小的代价把n个点都连起来) Prim算法（普利姆） 朴素版Prim（时间复...

5.二分图：染色法、匈牙利算法二分图：可以将一个图中的所有点，分成左右两部分，使得图中的所有边，都是从左边集合中的点，连到右边集合中的点。而左右两个集合内部都没有边。 再通俗点理解：一个图是二分图当且仅当图中不含奇数环（奇数环：边数为奇数的环） （一...

（二）高斯消元高斯消元能在O(𝑛^3)的时间复杂度内求解n个方程，n个未知数的多元线性方程组，即$$a_{11}x_{1}+a_{12}x_{2}+a_{13}x_{3}+\dots +a_{1n}x_{n} = b_{1}\a_{21}...