蓝桥杯常用算法汇总
<memory.h>或<string.h>void *memset(void *s, int ch, size_t n);
#include <algorithm>sort(a,a+n)排序函数，从小到大，a为数组名字，n为元素个数sort(vector.begin(),vector.end())排序vector只要数据类型定义了小于操作符，即可用sortsort(a,a+n,compare)即可按照自定义顺序排列，compare为比较函数，返回值为boollower_bound(a,a+n,x)二分查找，查找大于或等于x的第一个位置，只能查找vector<>数组，返回值为vector<>::iterator指针unique(vector1.begin(),vector1.end())，重排元素，使得所有值提前，返回值为重排后最后一个非重复值的后面的值的迭代器，即从返回值到vector1.end()是无意义的值，也是重复值的总数量reverse(vector1.begin(),vector1.end())，反转元素顺序next_permutation(p,p+n)，求下一个全排列，枚举用
#include <vector> 数组定义示例：vector<int> b(5);或者vector<int> a;赋值：b[0]=1;只有第一种定义可以这样赋值函数：int size()，获取大小void resize(int num)，改变大小void push_back(int x)，向尾部添加元素void pop_back()，删除最后一个元素void clear()，清空bool empty()，检查是否为空iterator insert(iterator x,y)，向vector数组的x位置插入元素y，x可以为v.begin()+2iterator erase(iterator x)，删除vector数组的x位置元素iterator begin()，返回头指针iterator end()，返回尾指针vector<>::iterator为一个可以指向其元素的指针
#include <set> 集合，其中不含重复元素，且其中元素已从小到大排序，从1开始定义示例：set<int> a;函数：int size()，获取大小iterator find(x)，若找到x，返回该键值迭代器的位置，否则，返回最后一个元素后面一个位置，即s.end()void clear()，清空bool empty()，检查是否为空iterator insert(y)，向set集合插入元素yiterator erase(iterator x)，删除set集合的值为x的元素，返回值为下一个位置的迭代器iterator begin()，返回头指针iterator end()，返回尾指针set<>::iterator为一个可以指向其元素的指针
#include <map> 映射，索引定义示例：map<string,int> month_name;赋值：map[“July”]=7;函数：iterator find(y)，寻找索引值为y的元素，返回指向其的指针iterator insert(map<string,int>(“July”,7))，向map映射插入元素(“July”,7)iterator erase(iterator x)，删除map映射的迭代器x的元素map< string,int>::iterator l_it;;l_it=m.find(“July”);if(l_it==m.end())cout<<"we do not find July"<<endl;else m.erase(l_it); //delete July;iterator begin()，返回头指针iterator end()，返回尾指针map<>::iterator为一个可以指向其元素的指针
#include <stack>定义示例：stack<int> s;void push(x)，将值x压入栈void pop()，删除顶部元素top()，获得栈顶元素，但不删除bool empty()，检查是否为空int size()，获取大小
#include <queue>定义示例：queue<int> q;void push(x)，将值x入队void pop()，出队front()，获得队头元素，但不删除bool empty()，检查是否为空int size()，获取大小
#include <string>string substr(int pos = 0,int n = npos) const; //返回pos开始的n个字符组成的字符串void swap(string &s2); //交换当前字符串与s2的值string &insert(int p0, const char *s); //在p0位置插入字符串string &erase(int pos = 0, int n = npos); //删除pos开始的n个字符，返回修改后的字符串int find(char c, int pos = 0) const; //从pos开始查找字符c在当前字符串的位置int find(const char *s,int pos = 0) const; //从pos开始查找字符串s在当前串中的位置
快速排序：void quicksort(int *a,int l,int r){if(l>=r)return;int temp=a[l]; //哨兵int i=l,j=r;while(i<j){while(i<j){ //从右开始往左判断if(a[j]>=temp){j--;}else{a[i++]=a[j];break;}}while(i<j){ //从左开始往右判断if(a[i]<=temp){i++;}else{a[j--]=a[i];break;}}}a[i]=temp; //将哨兵放回中间位置quicksort(a,l,i-1); //左边排序quicksort(a,i+1,r); //右边排序}
归并排序：void mergesort(int *a,int l,int r,int *b){if(l>=r)return ;int mid=l+r;mid/=2;mergesort(a,l,mid,b); //左边有序mergesort(a,mid+1,r,b); //右边有序int k=l,i=l,j=mid+1; //注意k的初值while(i<=mid&&j<=r){ //将i-mid和j-r两组有序序列，归并在一个有序序列中if(a[i]<=a[j])b[k++]=a[i++];elseb[k++]=a[j++];}while(i<=mid) //将i-mid剩余的数放在最后b[k++]=a[i++];while(j<=r) //将j-r剩余的数放在最后b[k++]=a[j++];for(k=l;k<=r;k++) //将b数组中的数据拷贝到原数组中a[k]=b[k];}
并查集：#define N 100int father[N];void init() {for(int i=0; i<N; i++)father[i] = i;}// 合并两个元素所在的集合void union(int x,int y) {x = getfather(x);y = getfather(y);if(x!= y)father[x]=y;}// 判断两个元素是否属于同一个集合bool same(int x,int y) {return getfather(x)==getfather(y);}// 获取根结点int getfather(int x) {while(x != father[x])x = father[x];return x;}// 获取根结点，是上边函数的改进，压缩了路径长度int getfather(int x) {if(x != father[x])father[x] = getfather(father[x]); // 路径压缩修改的是father数组return father[x];}
二分查找：int erfen(int *a,int l,int r,int v){ //a为待查找数组，l为下界下标，r为上界下标，v为目标值int mid;while(l<=r){mid=l+r;mid/=2;if(a[mid]==v) return mid;else if(a[mid]>v) r=mid-1;else l=mid+1;} return -1;}
01背包动态规划：int f[5000];int v[201],w[201];int main(int argc, char** argv) {int n=0,m,i,j,mx=0;cin>>n>>m;for(i=1;i<=n;i++){cin>>w[i]>>v[i];}for(i=1;i<=n;i++){for(j=m;j>=w[i];j--){f[j]=max(f[j],f[j-w[i]]+v[i]);mx=max(mx,f[j]);}}cout<<mx;return 0;}
LIS最长上升子序列int LIS(int *a,int n){int *dp=new int[n]; //存储以i为尾的最长上升子序列长度int mx=0,m,i,j;dp[0]=1; //初值，第一个字符为1for(i=1;i<n;i++){m=0;for(j=0;j<i;j++){ //对当前i之前的所有元素的最长上升子序列做判断if(dp[j]>m&&a[j]<a[i]){m=dp[j];}}dp[i]=m+1; //最大m值再加上1mx=max(mx,dp[i]); //同时判断所有最长上升子序列长度的最大值}return mx;}
LCS最长公共子序列动态规划法：void LCS(string str1,string str2){int x_len = str1.length();int y_len = str2.length();int arr[50][50] = {
{0,0}};int i = 0;int j = 0;//动态规划二维矩阵for(i = 1; i <= x_len; i++){for(j = 1; j <= y_len; j++){if(str1[i - 1] == str2[j - 1]){arr[i][j] = arr[i - 1][j - 1] + 1;}else{if(arr[i][j - 1] >= arr[i - 1][j]){arr[i][j] = arr[i][j - 1];}else{arr[i][j] = arr[i -1][j];}}}}//打印最长公共子序列stack<char> s;for(i = x_len, j = y_len; i >= 1 && j >= 1;){if(str1[i - 1] == str2[j - 1]){s.push(str1[i - 1]);//cout<<str1[i - 1]<<" ";i--;j--;}else{// if(arr[i][j -1] >= arr[i - 1][j])//打印两种情况if(arr[i][j -1] > arr[i - 1][j]){j--;}else{i--;}}}while(!s.empty()){cout<<s.top();s.pop();}cout << endl;}递归法：（只能求数量）int LCS(char* x,char *y){if(strlen(x)==0) return 0;if(strlen(y)==0) return 0;if(*x==*y) return LCS(x+1,y+1)+1;return max(LCS(x,y+1),LCS(x+1,y));}
Dijkstra最短路径算法#define MAX 9999999#define NUM 6int edge[NUM][NUM]; //存储两点间距离int dist[NUM]; //存储到每个点的最短距离int mark[NUM]; //标记是否已选//n:多少个点 start:起始点 void Dijkstra(int n,int start){int i,j,k=start;int min;for(i=0;i<n;i++){mark[i]=0;dist[i]=edge[start][i];}mark[start]=1;dist[start]=0;for(i=0;i<n;i++){min=MAX;for(j=0;j<n;j++){if(!mark[j]&&dist[j]<min){min=dist[j];k=j;}}mark[k]=1;for(j=0;j<n;j++){if(!mark[j]&&dist[j]>dist[k]+edge[k][j]){dist[j]=dist[k]+edge[k][j];}}}}
Floyd#define MAX 9999999#define NUM 6int edge[NUM][NUM];int temp[NUM][NUM];void Floyd(int a[NUM][NUM],int b[NUM][NUM]){int i,j,k;for(k=0;k<NUM;k++){for(i=0;i<NUM;i++){for(j=0;j<NUM;j++){if(k==0)b[i][j]=a[i][j];else{b[i][j]=min(b[i][j],b[i][k]+b[k][j]);}}}} }
最小生成树（prim）最好选择下边Krusal算法#define MAX 100000#define VNUM 6 int edge[NUM][NUM];int lowcost[NUM]; //记录Vnew中每个点到V中邻接点的最短边int addvnew[NUM]; //标记某点是否加入Vnewint adjecent[NUM]; //记录最小生成树的边，从adjecent[i]到ivoid prim(int start){int i,j,k;int v,min;int sum=0;for(i=0;i<NUM;i++){addvnew[i]=0;adjecent[i]=start;lowcost[i]=edge[start][i];}addvnew[start]=1;for(i=0;i<NUM-1;i++){min=MAX;v=-1;for(j=0;j<NUM;j++){if(!addvnew[j]&&min>lowcost[j]){min=lowcost[j];v=j;}}if(v!=-1){addvnew[v]=1;sum+=lowcost[v];for(j=0;j<NUM;j++){if(!addvnew[j]&&lowcost[j]>edge[v][j]){lowcost[j]=edge[v][j];adjecent[j]=v;}}}}}
Kruskal#define N 100Int w[N],p[i],r[i]; //w为权值数组,p为并查集数组,r为边权值排序数组，里边存储的是边的w对应的标号Int cmp(const int I,const int j){ return w[i]<w[j]; }Int find(int x){ return p[x]==x?x:find(p[x]); }Int Kruskal(){Int ans=0;For(int i=0;i<n;i++) p[i]=I;For(int i=0;i<n;i++) r[i]=I;Sort(r,r+m,cmp);//给边升序排列For(int i=0;i<n;i++){Int e=r[i]; int x=find(u[e]); int y=find(v[e]);If(x!=y) { ans+=w[e]; p[x]=y; }}return ans;}
可重集的全排列（递归）void print_permutation(int n,int P[],int A[],int cur) //P按顺序存储待排列数，A同样大小的临时空间数组{int i,j;if(cur==n){for(i=0;i<n;i++) printf("%d ",A[i]); //可输出可统计printf("\n");}else for(i=0;i<n;i++) if(!i||P[i]!=P[i-1]){int c1=0,c2=0;for(j=0;j<cur;j++) if(A[j]==P[i])c1++;for(j=0;j<n;j++) if(P[i]==P[j])c2++;if(c1<c2){A[cur]=P[i];print_permutation(n,P,A,cur+1);}}}next_permutation(p,p+n)，求下一个全排列
二进制法求子集void print_submet(int n,int s){ //打印一个子集for(int i=0;i<n;i++) if(s&(1<<i)) printf("%d ",i); //s=101时，代表子集{0，2}printf("\n");}int main() {int n=7; //代表集合{0，1，2，3，4，5，6}，二进制表示for(int i=0;i<(1<<n);i++) //枚举所有子集print_submet(n,i);return 0;}
快速求幂int pow3(int x,int n){if(n==0) //任何数的0次幂都是1return 1;else{ //把尾部的0全部去除while((n&1)==0){n>>=1;x*=x;}}int res=x; //后边的都不明白n>>=1;while(n!=0){x*=x;if((n&1)!=0)res*=x;n>>=1;}return res;}
辗转相除法求最大公约数：int gcd(int a,int b){int temp;while(a%b!=0){temp=a;a=b;b=temp%b;}return b;}辗转相除法最大公倍数：int lcm(int a,int b){int a1=a,b1=b,temp;while(a%b!=0){temp=a;a=b;b=temp%b;}return a1/b*b1;}