算法基础模板

高精度加法

#include <bits/stdc++.h>
using namespace std;
const int N=10005;
int A[N],B[N],C[N],al,bl,cl;
void add(int A[],int B[],int C[])
{for(int i=cl-1;~i;i--){C[cl]=A[i]+B[i];C[cl+1]=C[cl]/10;C[cl]%=10;}if(C[cl])cl++;
}
int main()
{string a,b;cin>>a>>b;al=a.size(),bl=b.size(),cl=max(al,bl);for(int i=al-1;~i;i--)A[i]=a[i]-'0';for(int i=bl-1;~i;i--)B[i]=b[i]-'0';add(A,B,C);for(int i=cl-1;~i;i--)cout<<C[i];return 0;
} 

高精度减法

#include <bits/stdc++.h>
using namespace std;
const int N=10005;
int A[N],B[N],C[N];
int al,bl,cl;
//Eg:数是1234存储在数组中是倒叙存储的 
bool cmp(int A[],int B[])
{if(al!=bl)return al>bl;//如果bl>al结果为负数 for(int i=al-1;~i;i--)//如果长度相同一个一个比较 if(A[i]!=B[i]) return A[i]>B[i];return true;//避免结果位-0 
}
void sub(int A[],int B[],int C[])
{for(int i=0;i<cl;i++){if(A[i]<B[i])A[i+1]--,A[i]+=10;//位数不够想前面借一位 C[i]=A[i]-B[i];//存储差 }while(cl&&C[cl]==0)cl--;//处理前导0，当前cl!=0且C[cl]==0 
}
int main()
{string a,b;cin>>a>>b;al=a.size(),bl=b.size(),cl=max(al,bl);for(int i=al-1;~i;i--)A[al-1-i]=a[i]-'0';for(int i=bl-1;~i;i--)B[bl-1-i]=b[i]-'0';if(!cmp(A,B))swap(A,B),cout<<'-';//当A<B时将2个数交换并且打印负数 sub(A,B,C);for(int i=cl;~i;i--)cout<<C[i];return 0;
}

高进度乘法

#include <bits/stdc++.h>
using namespace std;
const int N=100005;
int al,bl,cl;
int A[N],B[N],C[N];
void mul(int A[],int B[],int C[])
{for(int i=0;i<bl;i++){for(int j=0;j<al;j++){C[i+j]+=A[j]*B[i];//累加乘积 C[i+j+1]+=C[i+j]/10;//进位C[i+j]%=10; //存于 }}while(cl&&C[cl]==0)cl--; //处理前导0 
}
int main()
{string a,b;cin>>a>>b;al=a.size(),bl=b.size(),cl=al+bl;for(int i=al-1;~i;i--)A[al-1-i]=a[i]-'0';for(int i=bl-1;~i;i--)B[bl-1-i]=b[i]-'0';mul(A,B,C); for(int i=cl;~i;i--)cout<<C[i];return 0;
}

高精度除法

#include <bits/stdc++.h>
using namespace std;
const int N=10005;
int al,b,cl;
int A[N],B[N],C[N];
void div(int A[],int b,int C[])
{long long r=0;for(int i=al-1;~i;i--){r=r*10+A[i];//被除数 C[al-1-i]=r/b;//存商 r%=b;//除数 }reverse(C,C+cl);while(cl&&C[cl]==0)cl--;//处理多余0 
}
int main()
{string a;cin>>a>>b;cl=al=a.size();for(int i=al-1;~i;i--)A[al-1-i]=a[i]-'0';div(A,b,C);for(int i=cl;~i;i--)cout<<C[i]; return 0;
}

简单的前缀和模板

#include <bits/stdc++.h>
using namespace std;
const int N=10005;
int a[N],s[N],n,c;
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];s[i]=s[i-1]+a[i]; }cin>>n;for(int i=0;i<n;i++){int l,r;cin>>l>>r;cout<<s[r]-s[l-1]<<endl;}
}

选择排序

//选择排序就是从第一个下标的数开始
//以第一个数为基准向后进行比较选出最小的
//然后换下表进行排序 
#include <bits/stdc++.h>
using namespace std;
const int N=100005;
int n,ans[N];
void selection(int a[N],int k)
{for(int i=0;i<k-1;i++){int minindex=i;//从初始的下标进行比较 for(int j=i+1;j<k;j++)if(a[j]<a[minindex])minindex=j;//比对到大小进行交换 if(minindex!=i)swap(a[i],a[minindex]);}
}
int main()
{cin>>n;for(int i=0;i<n;i++)cin>>ans[i];selection(ans,n);for(int i=0;i<n;i++)cout<<ans[i]<<" ";return 0;
}

冒泡排序

//冒泡排序每次从头到尾比较一次就会确定最后面的的一个元素的位置 
#include <bits/stdc++.h>
using namespace std;
const int N=100005;
int n,ans[N];
void bubble(int a[N],int k)
{for(int i=0;i<n-1;i++){bool flag=false;for(int j=0;j<n-i-1;j++)//防止越界 {if(ans[j]>ans[j+1]){swap(ans[j],ans[j+1]);flag=true;}if(!flag)break;//当数没有进行交换就说明后面已经排序过来不需要在进行排序了直接退出 }}
}
int main()
{cin>>n;for(int i=0;i<n;i++){cin>>ans[i];}bubble(ans,n);for(int i=0;i<n;i++)cout<<ans[i]<<" ";
}

插入排序

//插入排序用当前一个数与前一个数进行比较
//如果当前的数任然比前一个数要小任然不断往前放
//数组中第一个数认为他已经有序 
#include <bits/stdc++.h>
using namespace std;
const int N=100005;
int ans[N],n;
void insertion(int a[N],int k)
{for(int i=1;i<n;i++)//第一个数认为已经有序 {int key=a[i];int j=i-1;while(j>=0&&a[j]>key)//如果当前的数大于前一个数 {a[j+1]=a[j];//进行交换 j--;//将当数与前一个数进行比较	} a[j+1]=key;}
}
int main()
{cin>>n;for(int i=0;i<n;i++)cin>>ans[i];insertion(ans,n);for(int i=0;i<n;i++)cout<<ans[i]<<" ";return 0;
}

二分查找

模板

//二分查找模板
//模板一
// 在单调递增序列a中查找>=x的数中最小的一个（即x或x的后继）
while(l<r)
{int mid=l+r>>l;if(check(mid))	r=mid;elsel=mind+1;
} 
//模板二
// 在单调递增序列a中查找<=x的数中最大的一个（即x或x的前驱）
while(l<r)
{int mid=l+r>>l;if(check(mid)) l=mid;elser=mid-1
} 
//浮点二分
while(r-l<1e-5)//需要一个精确度保障
{double mind=(l+r)/2;if(check(mid)) l=mid;elser=mid;
} 

题目

/*题目描述
牛牛同学拿到了 2 组数字，请你编程帮他找出，第 2 组中的哪些数，在第 1 组数中出现了，从小到大输出所有满足条件的数。比如：
第 1 组数有：8 7 9 8 2 6 3
第 2 组数有：9 6 8 3 3 2 1 0
那么应该输出：2 3 3 6 8 9
输入格式
第一行两个整数 n 和 m，分别代表 2 组数的数量
第二行 n 个正整数
第三行 m 个正整数
对于 60% 的数据 1≤n,m≤1000，每个数 <=210^9
对于 100% 的数据 1≤n,m≤100000，每个数 <=210^9
输入样例
7 7
8 7 9 8 2 6 3
9 6 8 3 3 2 10
输出样例
2 3 3 6 8 9*/
#include <bits/stdc++.h>
using namespace std;
const int N=1000010;
int n,m,a[N],b[N],ans;
int search(int x)
{int l=0,r=n+1;while(l+1!=r){int mid=(l+r)>>1;if(a[mid>x])r=mid;else if(a[mid]<x)l=mid;elsereturn 1;}return 0;
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}for(int j=1;j<=m;j++){cin>>b[j];}sort(a+1,a+n+1);sort(b+1,b+m+1);for(int i=1;i<=m;i++){if(search(b[i]))cout<<b[i]<<" ";}return 0;
}

/*题目描述
请在一个有序递增数组中（不存在相同元素），
采用二分查找，找出值 x 的位置，
如果 x 在数组中不存在，请输出 -1！
输入格式:
第一行，一个整数 n，代表数组元素个数（n≤10 6）。
第二行，n 个数，代表数组的 n 个递增元素（1≤数组元素值≤10 8）。
第三行，一个整数 x，代表要查找的数（0≤x≤10 8）。
输出格式:
x 在数组中的位置，或者 -1。
输入样例
10
1 3 5 8 9 10 13 19 24 35
24
输出样例
9 */
#include <bits/stdc++.h>
using namespace std;
const int N=1000001;
int n,a[N],end,ans;
int search(int x)
{int l=0,r=n+1;while(l+1!=r){int mid=(l+r)>>1;//想当于(l+r)/2 if(a[mid]>x)r=mid;//取中间的数大 ，向左边缩小 else if(a[mid]<x)l=mid;else //取中间的数小 ，向右边缩小 return mid; }
}
int main()
{cin>>n;for(int i = 1;i<=n;i++){cin>>a[i];}cin>>end;ans=search(end);cout<<ans;return 0;
}

01背包-P1048_luo

//dp[i][j]:1-i物品自由选择，容量不超过j的情况 下的最大价值
//i:第多少件商品；j:商品的体积；dp[i][j]：商品的价值
//将其想像为一个二维表 
//体积cost[i]  价值val[i]
// 不选第i个：dp[i-1][j]
//选择i个物品： 
#include<bits/stdc++.h>
using namespace std;int vol[101],value[101],dp[101][1001];int main(){//t：表示时间，m:表示药品的个数 int t,m;cin>>t>>m;for(int i=1;i<=m;i++)cin>>vol[i]>>value[i];for(int i=1;i<=m;i++){for(int j=0;j<=t;j++){if(vol[i]>j)//当前物品的体积大于背包的容量dp[i][j]=dp[i-1][j];//当放不进去是放上一行的数据else{dp[i][j]=max(dp[i-1][j],dp[i-1][j-vol[i]]+value[i]);//放的进去求这一行和上一行的最大值 }}}cout<<dp[m][t];return 0;}

bfs模板题走迷宫

//bfs模板题
//起点初始化放进队列中--->如果队列不为空一直进行扩展
//弹出队列的点判断是否为终点--->不为终点进行4各方向扩张
//将扩展的点放入到队列中，将队首元素进行弹出 
#include <bits/stdc++.h>
using namespace std;
const int N=10005;
int n,m,a[N][N],v[N][N];
int startx,starty,p,q;
struct point{int x;int y;int step;
}; 
queue<point> r;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int main()
{//输入 cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];cin>>startx>>starty>>p>>q;//BFSpoint s;s.x=startx;s.y=starty;s.step=0;r.push(s);//将起始点入队 v[startx][starty]==1;//将扩展过的点都标记 int flag=0;while(!r.empty()){int x=r.front().x,y=r.front().y;//找到终点进行打印步数 if(x==p&&y==q){flag=1;cout<<r.front().step;break;}for(int k=0;k<=3;k++){int tx,ty;tx=x+dx[k];ty=y+dy[k];//当前点没有障碍物，没有经过 if(a[tx][ty]==1&&v[tx][ty]==0){point temp;temp.x=tx; temp.y=ty;temp.step=r.front().step+1;r.push(temp);//将新扩展的点放入到队列 v[tx][ty]=1;//将访问过的点进行标记 }}r.pop();//扩展完的元素需要将队首进行出队 } if(flag==0)cout<<"-1";return 0; 
}
/*5 4
1 1 2 1
1 1 1 1
1 1 2 1
1 2 1 1
1 1 1 2
1 1 4 3*/

dfs模板题做迷宫

//dfs模板题做迷宫
#include <bits/stdc++.h>
using namespace std;
const int N=10005;
int m,n,startx,starty,p,q,minx=99999999;
int a[N][N];//1:表示空地；2：表示障碍物
int v[N][N];//1:表示访问；2：表示未访问 //先判断是否到达终点,在向4个方向进行展开
//展开时要标记此点已经进过之后要回溯要清除这个点 
void dfs(int x,int y,int step)
{if(x==p&&y==q){if(step<minx)minx=step;return;	}	//顺时针试探//右if(a[x+1][y]==1&&v[x+1][y]==0){v[x+1][y]=1;dfs(x+1,y,step+1);v[x+1][y]=0;}//下if(a[x][y+1]==1&&v[x][y+1]==0){v[x][y+1]=1;dfs(x,y+1,step+1);v[x][y+1]=0;}//左if(a[x-1][y]==1&&v[x-1][y]==0){v[x-1][y]=1;dfs(x-1,y,step+1);v[x-1][y]=0;}//上if(a[x][y-1]==1&&v[x][y-1]==0){v[x][y-1]=1;dfs(x,y-1,step+1);v[x][y-1]=0;}return; 
} 
int main()
{cin>>m>>n;for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)cin>>a[i][j];cin>>startx>>starty>>p>>q;dfs(startx,starty,0);cout<<minx;return 0;
}
/*5 4
1 1 2 1
1 1 1 1
1 1 2 1
1 2 1 1
1 1 1 2
1 1 4 3*/

dfs全排列模板题

#include<iostream>
using namespace std;
const int N = 10;
int path[N];//保存序列
int state[N];//数字是否被用过
int n;
void dfs(int u)
{if(u > n)//数字填完了，输出{for(int i = 1; i <= n; i++)//输出方案cout << path[i] << " ";cout << endl;}for(int i = 1; i <= n; i++)//空位上可以选择的数字为:1 ~ n{if(!state[i])//如果数字 i 没有被用过{path[u] = i;//放入空位state[i] = 1;//数字被用，修改状态dfs(u + 1);//填下一个位state[i] = 0;//回溯，取出 i}}
}int main()
{cin >> n;dfs(1);
}

vector、queue、typedef的使用

//vector、queue、typedef的使用
#include <iostream>
#include <algorithm> 
#include <vector>
#include <queue>
using namespace std;
typedef pair<int,int>PII;
typedef vector<vector<int>> VVI;
typedef vector<PII> V;
int main()
{vector<int> v;v.push_back(8);//尾部插入一个元素v.push_back(9);v.push_back(3);v.push_back(5);	v.pop_back();//删除队尾元素int len=v.size();//返回元素个数cout<<len<<endl;for(int i=0;i<=len-1;i++)cout<<v[i]<<" ";sort(v.begin(),v.end());cout<<endl;for(int i=0;i<=len-1;i++)cout<<v[i]<<" ";cout<<endl;cout<<"-----------------------------------"<<endl;queue<int> q;q.push(48);q.push(8);q.push(1);q.push(92);//队尾插入元素int x=q.front();//访问队首元素cout<<x<<endl;q.pop();//删除队首元素int chang=q.size();//反水元素的个数cout<<chang<<endl;int flage=q.empty(); cout<<flage<<endl;while(!q.empty()){cout<<q.front()<<" ";q.pop();}cout<<endl;int flag=q.empty(); cout<<flag<<endl;cout<<"-----------------------------------"<<endl;PII p1={1,2};cout<<p1.first<<" "<<p1.second<<endl;V v1={{1,2},{8,9}};cout<<v1[0].first<<" "<<v1[0].second<<endl;cout<<v1[1].first<<" "<<v1[1].second<<endl;cout<<"-----------------------------------"<<endl;int ou[]={1,9,58,3,75,6,2,4,8,2,3,65};sort(ou,ou+12,greater<int>());for(int i=0;i<12;i++)cout<<ou[i]<<" "<<endl;
} 

最大公约数和最小公倍数

//输入两个正整数 m 和 n，求其最大公约数和最小公倍数。
#include <iostream>
using namespace std;int gcd(int a,int b)
{while(b != 0){int c = a % b;a = b;b = c;}return a;
}int main()
{int n,m;cin >> n >> m;cout << gcd(n,m) << " " << n * m / gcd(n,m);return 0;
}

质数的个数

//给定一个正整数 n，请你求出 1到n中质数的个数。
//设置2层循环在外面的循环时遍历数的
//里面的循环是用来将当前i的倍数进行标记的； 
#include <iostream>
#include <cstring>
using namespace std;
int n;
int st[1001000], primes[1001000], p[1001000];
int cnt;void v(int n){memset(st, false, sizeof st);st[0] = true;st[1] = true;for(int i = 2; i <= n; i++){if(!st[i]) primes[cnt++] = i;for(int j= i; j <= n; j+=i){st[j] = true;}}
}
int main(){cin >> n;v(n);cout << cnt;return 0;
}

质数的判断

#include <bits/stdc++.h>
using namespace std;
int check(int x)
{for(int i=2;i<=x/i;i++)if(x%i==0)return 1;
return 0;
}
int main()
{int n;//输入你要判断质数的个数 cin>>n;for(int i=1;i<=n;i++){int x;cin>>x;if(x==1)cout<<"no"<<endl;else if(check(x))cout<<"no"<<endl;elsecout<<"yes"<<endl;}return 0;	
}