摘要： 最小生成树 1）概念： 在一个无向带权图中，可以联通所有结点并且权值最小的路径就是最小生成树 2）实现算法： 2.1）Kruskal： 将所有边按照权值从大到小排序，然后利用并查集，判断每一条的边的的两个结点是否在同一集合中，不在就合并，并且加上该条边的权值，在就跳过，最后将所有边都处理完就可以得到 阅读全文

摘要： 拓扑排序 1）解决依赖关系的问题 例如：一个人需要上n门课，但是上a课之前要先上b课，上b课之前要先上c课，求上课的顺序。可以将上述关系抽象为一个有向图，c -> b, b -> a，并将每一个结点的入边数量用一个入度表存起来，a:1,b:1,c:0 入度为零的就是可以直接上的课，先输出c,然后以c 阅读全文

摘要： 基础建图 1）竞赛一边使用邻接矩阵，邻接表，和链式前向星法建图 1.1）邻接矩阵： 用一个二维数组来表示图，下标表示结点，例如：a[3][4] = 1;表示有一条 3 -> 4 的边，如果有权值，则将1替换为权值 代码： const int MAX = 100; vector<vector<int> 阅读全文

摘要： 并查集 1）概念：处理不相交集合合并及查询问题的树型数据结构 2）基本功能：查找（find），合并（union） 3）代码实现： #include<iostream> using namespace std; //并查集优化：扁平化（路径压缩），小挂大 const int MAXN = 100000 阅读全文

摘要： 一个简单的在终端运行的贪吃蛇 效果如下： 代码： #include<iostream> #include<conio.h> #include<windows.h> #include<random> #include<ctime> #include<chrono> #include<sstream> 阅读全文

摘要： 最大公约数和同余原理 1）辗转相除法求最大公约数： 本质上利用递归思想，设有两个数 a 和 b (a > b),求a 与 b 的最大公约数可以先进行 a % b = res1,res1 一定小于b, 这时让 a = b, b = res1;再次让 a % b = res2, a = b; b = r 阅读全文

摘要： 异或运算 1）基本性质： n ^ 0 = n; n ^ n = 0; //交换律 a ^ b = b ^ a; //结合律 (a ^ b) ^ c = (a ^ c) ^ b; //在对两个二进制数进行异或运算时，可以将异或看作不进位相加 //例如：101101 ^ 010111 = 111010 阅读全文

摘要： 基数排序 1）基本思想： 不通过直接比较数值大小，而是将整数按位分开（个，十，百），从低位到高位，依次排序 2）实现方法： 基数排序通常采用 LSD (Least Significant Digit first) 策略，即从最低有效位（个位）开始排序。我们以数组 [170, 45, 75, 90, 阅读全文

摘要： 堆结构和堆排序 1）基本思想： 1.堆结构：利用数组来模拟堆（以完全二叉树形式构造），用数组下标充当堆的节点位置，并用一个变量size表示堆的大小 2.堆排序：利用大根堆，通过将根节点的数和最后一个节点的数交换位置，可以将最大数排到最后面，然后再对堆进行调整，使其重新变成大根堆，通过不断操作，完成排 阅读全文

摘要： 随机快速排序 1）基本思想：在一个数组中，随机挑选一个数x并以x为基准，将比x小的数排到x左侧，大于x的数排到右侧并且令左半部分(比x小的部分)的最后一个数为x，这时x在数组中的位置就排好了，然后再分别对两侧的部分进行相同的操作，最后就可以使数组有序 2）基本代码： #include<iostrea 阅读全文