『算法-ACM 竞赛-疯子的算法总结』6.2 复杂排序算法 ① 归并排序 merge_sort()归并排序采取了分治的思想，每次分别排左半边和右半边，不断递归调用自己，直到只有一个元素递归结束，开始回溯，调用 merge 函数，合并两个有序序列，再合并的时候每次给末尾追上一个最大 int 这样就不怕最后一位的数字不会被排序。 123456789101112131415161718192021222

『算法-ACM 竞赛-疯子的算法总结』6.1 简单排序总 选择排序+插入排序+比较排序+冒泡排序一、数组的排序算法1.选择排序选择排序是指每次选择所需排序数组中的最大值或者最小值（根据排序方式选择，从大到小选最大，从小到大选最小），将这个元素与前面没有进行排序的元素交换。下面以 1 4 2 5 9 6 这些乱序元素，来表现排序过程。第一次排序 9 4 2 5 1 6第二次排序 9 6 2 5 1

『算法-ACM 竞赛-疯子的算法总结』5 矩阵乘法 （矩阵快速幂）学过线性代数的都知道矩阵的乘法，矩阵乘法条件第为一个矩阵的行数等与第二个矩阵的列数，乘法为第一个矩阵的第一行乘以第二个矩阵的第一列的对应元素的和作为结果矩阵的第一行第一列的元素。（详解参见线性代数）于是我们可以写出矩阵惩乘法的代码 123456789101112131415struct JZ{ int m[maxn][m

『算法-ACM 竞赛-疯子的算法总结』4 贪心算法一、贪心算法解决最优化问题的算法一般包含一系列的步骤，每一步都有若干的选择。对于很多最优化问题，只需要采用简单的贪心算法就可以解决，而不需要采用动态规划方法。贪心算法使所做的局部选择看起来都是当前最佳的，通过局部的最优化选择来产生全局最优解。本文将介绍贪心算法的理论基础和一些简单应用。在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，

『算法-ACM 竞赛-疯子的算法总结』3 STL Ⅱ 迭代器（iterator） + 容器一、迭代器（Iterator）背景：指针可以用来遍历存储空间连续的数据结构，但是对于存储空间费连续的，就需要寻找一个行为类似指针的类，来对非数组的数据结构进行遍历。定义：迭代器是一种检查容器内元素并遍历元素的数据类型。迭代器提供对一个容器中的对象的访问方法，并且定义了容器中对象的范围。迭代器（Iterator

『算法-ACM 竞赛-疯子的算法总结』2 STL Ⅰ 算法 （ algorithm ）写在前面： 为了能够使后续的代码具有高效简洁的特点，在这里讲一下 STL，就不用自己写堆，写队列，但是做为 ACMer 不用学的很全面，我认为够用就好,我只写我用的比较多的。 什么是 STL(STl 内容）:容器（Container）：是一种数据结构，如 list，vector，和 deques ，以模板类的方法

『算法-ACM 竞赛-疯子的算法总结』14 ST 算法（区间最值）疯子的算法总结 14–ST 算法（区间最值）借助倍增和动态规划可以实现 O（1）的时间复杂度的查询 预处理：① 区间 DP 转移方程 f[i][j] = min(MAX 同理)(f[i][j - 1],f[i + ][j - 1]) f[i][j]表示从 i 位置开始的后 2^j 个数中的最大值 用 f[i][j]表示从

『算法-ACM 竞赛-疯子的算法总结』12 倍增疯子的算法总结 12–倍增最近发现倍增讲的很少，这可以理解为二分新姿势！ 我们设想一个背景，公主被邪恶的王八抓走了，马里奥大叔这次要去救公主了，如果他到的不及时公主就要被杀死了，他能抱得美人归吗？马里奥有一种神奇的能力，它可以在一秒钟之内走任意距离！已经知道了王八城堡很高，在哪里都能看见！ 憨批马里奥：地球是圆的，我向相反的方向走，额。。。走多少米呢

『算法-ACM 竞赛-疯子的算法总结』11 次小生成树+严格次小生成树疯子的算法总结 11–次小生成树+严格次小生成树一、总体思路首先,我这一题的思路是倍增 LCA+Kruskal 首先，kruskal 求最小生成树 不会的戳这里 求次小生成树 倍增 LCA 关键在于次小生成树怎么求： 问自己一些问题 怎么求不严格次小生成树 不严格次小生成树为什么不严格 方法每次选择 U—V 之间的边

『算法-ACM 竞赛-疯子的算法总结』10 最小生成树 Kruscal疯子的算法总结 10–最小生成树 Kruscal 按照权值排序可得，就有如下顺序: 1. 1-2 1 2. 1-4 2 3. 1-5 2 4. 2-5 3 5. 2-3 4 6. 4-5 4 每次选取最小边泉，判断是否同属一个集合，如果不属于同一集合，就把它加到左端点集合中，也就是说，两个点不属于一个集合说明这条边不在树中，即可