【算法总结】图论-最小生成树一、概念在一个无向连通图中，如果存在一个连通子图包含原图中所有的结点和部分边，且这个子图不存在回路，那么我们称这个子图为原图的一棵生成树。在带权图中，所有的生成树中边权的和最小的那棵（或几棵）被称为最小生成树。定理：在要求解的连通图中，任意选择一些点属于集合A，剩余的点属于集合B，必定存在一...

【算法总结】图论-并查集一、概念：并查集并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结...

【算法总结】图论-预备知识 邻接矩阵：用一个二维数组来表示图的相关信息，如edge[i][j]表示结点i和结点j之间的关系（以及权重）——在表示的图为稠密图，且频繁地判断特定结点对是否相邻时，使用邻接矩阵较为适宜。邻接链表：链式存储结构，为图的每个顶点建立一个单链表，第i个单链表中保存...

【算法总结】高精度整数我们首先明确高精度整数的保存形式，我们常用如下结构体来保存一个高精度整数structbiginteger{intdigit[1000];//保存大整数中若干位的数字，暂且使用每4位为一个单位保存intsize;//size是digit数组中第一个我们还未使用的数组单元，即digit数组下一个存储单...

【算法总结】素数素数即只能被自身和1整除的大于1的正整数。一、素数判定怎样确定一个数是素数？我们可以用所有大于1小于其本身的整数去试着整除该数，若在该区间内存在某个数能整除该数则该数不是素数；若这些数都不能整除它，则该数为素数。这一朴素的算法思想时间复杂度为O（n），n为我们要测试的数字。但其实，我们并不用测试到n-1...

【算法总结】最大公约数和最小公倍数一、最大公约数（GCD：greatest common divisor）欧几里得算法：若a、b全为零则它们的最大公约数不存在；若a、b其中之一为零，则它们的最大公约数为a、b中非零的那个；若a、b都不为零，则使新a=b；新b=a%b，然后重复该过程。 例4...

【算法总结】%运算符与取余运算取余套路：对取得的余数加上除数后，再对该和求除数的模，即可解决符号问题，保证取余结果恒正。（这里b是绝对值，恒大于0）ans=(r+b)%b一、数位拆解数位拆解即把一个给定的数字（如3241）各个数位上的数字拆开，即拆成3、2、4、1。例4.1特殊乘法AC代码（数学方法）#include&...

【算法总结】二叉排序树二叉排序树是一棵特殊的二叉树，它是一棵二叉树但同时满足如下条件：对于树上任意一个结点，其上的数值必大于等于其左子树上任意结点数值，必小于等于其右子树上任意结点的数值。二叉排序树的存储方式与二叉树保持一致，我们更多的关注它独有的操作。我们从二叉树的插入开始了解其建树方式，对二叉排序树插入数字x：1....

【算法总结】二叉树我们从二叉树的遍历谈起。众所周知，在对二叉树的遍历过程中，根据遍历每一个结点的左子树、结点本身、右子树的顺序不同可将对二叉树的遍历方法分为前序遍历、中序遍历、后序遍历。我们摒弃数据结构教科书上复杂的遍历方式，而是使用我们在上一章所重点讨论过的递归程序来简单的实现它。假设二叉树结点由以下结构体表示：&n...

在一棵树中，从任意一个结点到达另一个结点的通路被称为路径，该路径上所需经过的边的个数被称为该路径的长度。若树中结点带有表示某种意义的权值，那么从根结点到达该节点的路径长度再乘以该结点权值被称为该结点的带权路径长度。树所有的叶子结点的带权路径长度和为该树的带权路径长度和。给定n个结点和它们的权值，以它们为叶子结点构造一棵...

算法总结-深搜由于是深度优先，后进入的结点需要先读取，因此选取堆栈实现，在栈中保存从起始结点（状态）到当前结点的路径上的所有结点。一般用递归实现。非递归框架DFS(){初始化栈while(栈不为空&未找到目标结点){取栈顶元素扩展，扩展出的结点放回栈顶}......}递归框架在深度优先搜索中，状态空间的图结构并...

算法总结-广搜（BFS：breadth-firstsearch）广度优先搜索算法（用QUEUE）把初始节点S0放入Open表（待扩展表）中；如果Open表为空，则问题无解，失败退出；把Open表的第一个节点取出放入Closed表，并记该节点为n；考察节点n是否为目标节点。若是，则得到问题的解，成功退出；若节点n不可拓展...

算法总结-递归定义：所谓递归即函数直接或间接地调用函数本身，调用的方式按照问题的不同人为定义，这种调用方式被称为递归方式。同时，为了不使这样的递归无限的发生，我们必须设定递归的出口，即当函数达到某种条件时停止递归。问题的求解过程->划分成相同性质的子问题的求解->子问题的求解过程可以很容易地求出->这...

算法总结-枚举定义：依次尝试搜索空间中所有的解，测试其是否符合条件，若符合则输出答案，否则继续测试下一组解。注意：在使用枚举这种相对较为暴力的解法来进行解题时，我们对其时间复杂度要做特别的关注。枚举问题的时间复杂度往往与需要枚举的情况个数有关，因为我们必须不遗不漏地枚举每一种可能成为答案的情况。所以搜索空间越大，枚举的...

动态规划-背包问题此博客分别讨论0-1背包，完全背包和多重背包，并给出相应的解题模板。0-1背包题目：有一个容量为V的背包，和一些物品。这些物品分别有两个属性，体积w和价值v，每种物品只有一个。要求用这个背包装下价值尽可能多的物品，求该最大价值，背包可以不被装满。 0-1背包问题：在最优解中，每个物品只有两种...