Cedeat的摸鱼中心

二部图（二分图）什么是二分图对于一个无向图G=(V,E)，如果将顶点V分隔为两个互不相交的子集（A,B），且图中的每条边（i，j）所关联的两个顶点分别属于两个不同的顶点集（i in A，j in B），则称图G为一个二分图。二分图有一个

2022-02-11 算法入门

算法图论/搜索

堆堆的结构：一颗完全二叉树（十分平衡，除最后一层（叶结点）以外，其他节点均非空，最后一层从左到右依次排布）。小根堆也指最小堆。经过排序的完全二叉树，其中每一个非终端节点均小于其左右子节点，其根节点为所有元素的最小值。大根堆同理。存储方

2022-02-11 算法入门

算法数据结构

最小生成树什么是最小生成树？设定一个n点m条边的无向图G=(V,E)，V表示图中点的集合，E表示图中边的集合，n=|V|，m=|E|。由V中的n个顶点和E中的n-1条边构成的无向连通子图成为G的一棵生成树，其中边权之和最小的生成树成为最小

2022-02-11 算法入门

算法图论/搜索

图论最短路 Dijkstra算法朴素Dijkstra算法 O(n^2)Dijkstra算法用于求节1到点n的最短路，适用于稠密图（其时间复杂度与边数m无关）。对每个点设定一个dist，代表其距离点1的距离，初始化为无穷大，后续再进

2022-02-11 算法入门

算法图论/搜索

欧拉函数定义1~N中与N互质的数的个数称为欧拉函数，记为ϕ(N)。若在算数基本定理中，N = p1^a1 * p2^a2 * ….. * pm^am。 ϕ(N) = N * (p1 - 1) / p1 * (p2 - 1) / p2 *

2022-02-11 算法入门

算法

线性DP数字三角形用f[i] [j]表示走到f[i] [j]的最大步数，一共只有两种走法，左上方走下来或右上方走下来，因此我们可以列出状态转移方程 f[i][j] = f[i - 1][j - 1] + a[i][j]; //左上方走下来

2022-02-11 算法入门

算法动态规划

约数约数，又称因数。整数a除以整数b(b≠0) 除得的商正好是整数而没有余数，我们就说a能被b整除，或b能整除a。a称为b的倍数，b称为a的约数。试除法求约数#include <bits/stdc++.h> using nam

2022-02-05 算法入门

算法数论

哈希表哈希表的作用将一个庞大的空间（值域）映射到比较小的空间（0-N），N一般为1e5-1e6左右。这种映射通常使用模运算来进行，但将若干较大范围的数映射到较小范围的数，难免会发生冲突（两个数映射到同一个数上），为解决这种冲突，我们需要特

2022-02-04 算法入门

算法数据结构

质数质数的判定-试除法质数的因子一定是成对出现的，因此不必枚举所有的因子，只要枚举其中较小的因子，也就是一半的因子即可。而较小因子的上限是sqrt(n)，所以只需到sqrt即可。 #include <bits/stdc++.h>

2022-02-04 算法入门

算法数论

树形DP状态表示：树形DP的状态集合有两个f[u, 0]和f[u, 1]，分别表示所有从以u为根的子树中选择，且不选u这个点的方案，和选这个点的方案。首先对于f[u, 0]，因为它没有选择u这个点，因此子节点自由选择，可以由f[j ,

2022-01-05 算法入门

算法动态规划

状态压缩DP状态压缩本质上就是用一个二进制数来表示出所有的状态，从而方便用位运算节省速度。蒙德里安的梦想要找到所有的方案数，我们需要找到所有横放1x2方格的合法方案数，当横放数量确定后，竖放的方格只需插入即可。状态表示：用f[i] [j

2022-01-05 算法入门

算法动态规划

记忆化搜索记忆化搜索有点像搜索+初始化判断，通过保存过去的结果，可以避免重复的搜索，以此达到更快的时间。 f[a] [b]表示走到a，b这一点的最大距离，因此f[a] [b]如果不为初始化的值，则一定是最大值，我们不必再重复搜索 #incl

2022-01-05 算法入门

算法动态规划