蓝桥杯算法模板（自用）

1、万能头文件

#include <bits/stdc++.h>

2、最大公约数与两数之间求和公式

1、最大公约数 int gcd(int a,int b) { return b == 0? a:gcd(b,a%b); } 2、两数之间求和公式 int Sn(int a, int b) { return (a+b)*(b-a+1)/2; }

3、进制间的转换

1、十进制转 n 进制 短除法 void conversion(int a,int n) { if(a <= 0) { cout << 0; return; } stack<int> aa; while(a) { aa.push(a%n); a/=n; } while(!aa.empty()) { int t = aa.top(); if(t > 9) { char c = t-10 + 'A'; cout << c; }else cout << t ; aa.pop(); } } 2、n 进制转换其他十进制 n进制的数值每个位数的数 * n ^ (根据所在的位置，小数点往左从 0 开始) 的累加和

4、利用stringstream进行类型转换

1、int 转 string #include<sstream> void i2s(int number , string &str) { stringstream ss; ss << number; ss >> str; } ps:可以用于int、double、float 转string类型 2、string 转 int int s2i(int number,string & str) { stringstream ss ; ss << str; ss >> number; return number; }

5、快速幂计算

long long fastPower(long long base,long long power) { long long result = 1; while(power > 0) { if(power&1) result = result*base%1000; power >>= 1; base = base*base%1000; } return result; }

6、快速排序

int partition(int arr[],int i, int j) { while(i < j) { while(i < j && arr[i] <= arr[j]) j--; if(i < j) swap(arr[i],arr[j]); while(i < j && arr[i] <= arr[j]) i++; if(i < j) swap(arr[i],arr[j]); } return i } void quick_sort(int arr[], int low, int high) { if(low < high) { int piovt = partition(arr,low,high); quick_sort(arr,low,piovt-1); quick_sort(arr,piovt+1,high); } }

7、并查集

主要用于查找判断两个节点之间是否存在联系。 所以主要是两个操作：1、查找根结点。2、判断并处理 整个模板可以分为三部分：初始化、查找、处理 #include <bits/stdc++.h> int id[1000]; int size[1000]; int find(p) { while(p != id[p]) { id[p] = id[id[p]]; //路径压缩，破坏树结构 p = id[p]; } return p; } void Union(int p, int q) { int i = find(p); int j = find(q); if(i == j) return ; if(size[i] <= size[j]) { id[i] = j; size[j] += size[i]; }else { id[j] = i; size[i] += size[j]; } } int main() { for(int i = 0; i < 1000; i++) { id[i] = i; size[i] = 1; } }

8、斐波那契问题

兔子繁殖问题{1,1,2,3,5,8,13…} 关键点：第三年之后每年的兔子数等于前一年兔子数+前两年兔子数 最遍历的解法为：通过循环递推出每年的兔子数，使用递归时间复杂度较复杂

9、多源点最短路径：Floyd

关于图的问题，都少不了对数据的初始化 Floyd的核心代码: 主要利用中间点 K 的改变更新图中 i 到 j 的最短路径 for(int k = 1; k <= N; k++) for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) map[i][j] = min(map[i][j],map[i][k]+map[k][j]); 可能考到的问题：最短路径、可删除边、最小环 缺点：

10、单源点最短路径：Dijkstra

双循环依次更新开始源点到各源点的距离 //参数 k 为开始源点 void dijkstra(int k) { dis[k] = 0; //关键 //循环遍历 for(int i = 0; i < N; i++) { int temp = -1; //标记找到的最小值 int aaa = inf; //进行迭代松弛 for(int j = 0; j < N; j++) { if( !vis[j] && dis[j]< aaa) { aaa = dis[j]; temp = j; } } if(temp == -1) return; vis[temp] = 1; //根据找到的最短路径更新 dis for(int j = 0; j < N; j++) { if(!vis[j])//找到没有确定最短路径的结点 { //判断是否是最短路径 if(dis[j] > dis[temp] + map[temp][j]) { //更新dis dis[j] = dis[temp] + map[temp][j]; } } } } }

11、动态规划

动态规划解题步骤 1、问题抽象化 2、建立模型 3、寻找约束条件 4、判断是否满足最优性原理 5、找大问题与小问题的递推关系式 6、填表 7、寻找解组合

12、01背包问题

01背包：从 n 个物品中选中 m 个物品放入背包中，使得背包容量不超过 w 并且价值最大（每个物品都是完整的） 核心代码: w[i] 物品重量；dp[i][j] i 物品，j重量；v[i] 价值 ；index[i] 记录最优解 找出最大价值（填表） for(int i = 1; i <= n; i++) for(int j = 1; j <= w; j++) if(j < w[i]) dp[i][j] = dp[i-1][j]; else dp[i][j] = max(dp[i-1][j],dp[i][j-w[i]] + v[i]); 最优解回溯：找出选中的物品 void findMax（int i , int j） { if(i >= 0) { if(dp[i][j] == dp[i-1][j]) { index[i] = 0; findMax(i-1,j); }else if(j - w[i] >= 0 && dp[i][j] == dp[i-1][j -w[i]] + v[i]){ index[i] = 1; findMax(i-1,j-w[i]); } } }

13、最小生成树

#include <iostream> #include <algorithm> using namespace std; const int inf = 1000; //代表无线距离，没有连接 int map[100][100]; //各边关系 //补助数组的结构体 typedef struct { int lowcost; //权值 int adjvex; //与其相邻的结点 }Element; // Prim算法 //参数1：结点个数 //参数2：根结点 void Prim(int n,int w) { int temp; //记录新加入的结点 Element El[10]; //声明一个结构体变量数组，假设最多有10个结点 //初始化根结点与各结点的关系 for(int i = 0; i < n; i++) { El[i].lowcost = map[w][i]; //与结点 i 之间的权值 El[i].adjvex = w; //与结点 i 相邻的结点 } //将根结点加入树 El[w].lowcost = 0; //权值为 0 表示已经连接不需要在判断 // Prim算法的主体部分 //将剩下的所有结点遍历加入树 for(int i = 0; i < n-1;i++) { int min = 1000; //最小的权值 temp = 100; //遍历未连接结点 的权值，找到最小权值 for(int j = 0; j < n; j++) { //如果该结点还没有加入树，并且它与已经加入树的结点之间的权值 最小 if(El[j].lowcost != 0 && El[j].lowcost < min) { min = El[j].lowcost; //更新最小权值 temp = j; //记录最小权值的结点 } } //输出最小生成树的边。 El[k].adjvex为与 k 结点连接的结点 cout << El[temp].adjvex << "------" << temp << endl; El[temp].lowcost = 0; //将 temp 结点加入树 //根据新加入的结点 temp 调整与未加入树的结点之间最小权值 for(int j = 0; j < n; j++) { if(map[temp][j] < El[j].lowcost) { El[j].lowcost = map[temp][j]; El[j].adjvex = temp; } } } } int main(int argc, char** argv) { /* 测试用例 6 9 0 1 34 0 5 19 0 2 46 1 4 12 2 3 17 2 5 25 3 5 25 3 4 38 4 5 26 */ int n ,m; int a,b,c; while(cin>>n>>m) { //对图进行初始化 for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(i == j) map[i][j] = 0; else map[i][j] = inf; //边与边的关系 for(int i = 0; i < m; i++) { cin >> a >> b >> c; map[a][b] = map[b][a] = c; } Prim(n,0); } system("pause"); return 0; }

14、考前重点复习

最短路径问题：关于单源点Dijkstra与多源点Floyd 算法的区别与选择。 单源点：只记录从开始结点到各结点之间最短的路径， 通过与dfs算法的结合可以解决 最短路径 + 最小权值 + 路过的结点等问题的组合。 使用一维数组进制记录，dfs需要二维数组 多源点：使用二维数组记录各结点之间的最短路径。

最小生成树与最短路径的区别： 最短路径求的是到结点的最小距离 而最小生成树求的是整个树的权值最小 prim算法就是从根结点出发遍历出与它相连的最小权值的结点，再通过找到的结点更新。从这方面来看与Dijkstra算法很相似。

Dijkstra + dfs 的结合。 prim typedef struct