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}...

7.Hash表哈希表的作用：把一个比较大的空间，通过一个函数映射到一个比较小的空间。 一般做哈希运算时，取一个质数作为模，会使得冲突的概率降低 哈希表的冲突解决方法： 拉链法 开放寻址法 AcWing 840.模拟散列表（1）拉链法创建一个数...

（一）数论1.质数 对所有的大于1的自然数字，定义了【质数/合数】这一概念。对于所有小于等于1的自然数，没有这个概念，它们既不是质数也不是合数。 质数的定义：对于大于1的自然数，如果这个数的约数只包含1和它本身，则这个数被称为质数，或者素数...

（四）容斥原理先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。 以S1,S2,S3三个集合为例，求出三个集合中包含的元素个数，可以通过韦...

（五）简单博弈论公平组合游戏ICG 若一个游戏满足： 由两名玩家交替行动； 在游戏进程的任意时刻； 可以执行的合法行动与轮到哪名玩家无关； 不能行动的玩家判负； 则称该游戏为一个公平组合游戏。 NIM博弈属于公平组合游戏，但城建的棋类游戏，比如围...

3.区间DPAcWing 282. 石子合并实现思路： f(i,j)表示将第i堆到第j堆石子合并为一堆时的最小代价 状态划分：选一个分割点k，将ik，k+1j这两个堆（两个区间）的石子合并，然后加上两个区间堆的总合并代价（采用前缀和计算区间i到j...