算法模板
一、STL常用函数
1.string
头文件cstring
size()//获取字符串长度
insert()//插入字符串，用法:s.insert(a,b),a是起始下标，b是插入的字符串
append()//插入字符串，用法:s.append(a),a是插入到原字符串末尾的字符串
erase()//删除任意字符，用法:s.erase(a,b),a是起始下标，b是从下标a开始删除的长度
substr()//截取字符字串，用法:s.substr(a,b),a是起始下标，b是从下标a开始截取的长度
back()//获取最后一个字符
pop_back()//删除最后一个字符
empty()//判断是否为空
clear()//清空字符串
find()//查找字符串，用法a=s.find(b),b是要查找的子串，返回值a大小是子串的起始下标（-1时表示不存在该子串）
2.stack
头文件stack
top()//返回一个栈顶元素的引用
push(const T& obj)//将对象副本压入栈顶
pop()//弹出栈顶元素
size()//返回栈中元素的个数
empty()//在栈中没有元素的情况下返回 true
3.queue
头文件queue
front()//返回 queue 中第一个元素的引用
back()//返回 queue 中最后一个元素的引用。
push(const T& obj)//在 queue 的尾部添加一个元素的副本
pop()//删除 queue 中的第一个元素。
size()//返回 queue 中元素的个数。
empty()//如果 queue 中没有元素的话，返回 true
二、并查集（洛谷p3367)
#include<iostream>
using namespace std;
int f[10086];
int find(int x){
return f[x]==x?x:f[x]=find(f[x]);
}
void unity(int x,int y){
f[find(y)]=find(x);
}
int main(){
int m,n;
cin>>n>>m;//n个元素，m组关系
for(int i=1;i<=n;i++)
f[i]=i;//并查集初始化
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
unity(a,b);//a,b属于同一个集合，初始化存进f数组
}
int b,c;
cin>>b>>c;
if(find(b)==find(c))
cout<<"True";//如果find函数返回值相等，说明两数在同一集合
}
三、快速幂（洛谷p1226)
long long pow_mod(long long a,long long b,long long m)
{
if(b==0)return 1;
int x=pow_mod(a,b/2,m);
long long ans=(long long)x*x%m;
if(b%2==1)ans=ans*a%m;
return ans;
}
四、高精度加法(洛谷p1601)
#include <bits/stdc++.h>
using namespace std;
string a,b,c;int t1,t2;
int main(){
cin>>a>>b;
while(a.length()>b.length())
b="0"+b;
while(a.length()<b.length())
a="0"+a;
for(int i=a.length()-1;i>=0;i--){
t1=a[i]-'0'+b[i]-'0'+t2;
t2=t1/10;
t1%=10;
c=char(t1+'0')+c;
}
if(t2!=0)
c=char(t2+'0')+c;
cout<<c;//输出
return 0;
}
五、GCD&LCM
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
int lcm(int a,int b){
return a*b/gcd(a,b);
}
六、快读、快写
第一种
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
第二种
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
inline void write(int x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
}
使用方法：
int main(){
int a,b;
a=read();
b=read();
write(a+b);
return 0;
}
七、搜索
1.dfs
void dfs(int p,int q)
{
if(p<0||p>=l||q<0||q>=r||a[p][q]=='#'||b[p][q]!=0)return;//边界跳出条件
sum++;//结果统计
b[p][q]++;//已遍历节点标记
for(int i=0;i<4;i++)
dfs(p+xx[i],q+yy[i]);//递归
}
2.bfs
int bfs(int x,int y)
{
memset(a,0,sizeof(a));//存储当前节点是否被访问过
memset(b,0,sizeof(b));//存储当前节点的最小值状态
a[x]=1,b[1]=0;//初始节点状态更新
queue<int>q;
q.push(x);//头节点放入队列
while(!q.empty())
{
int s=q.front();//取队首元素
q.pop();//弹出
if(s==y)
return b[y];//如果队首元素为答案直接返回
else
{
if(!a[s+1]&&s+1<=100000&&s+1>=0)q.push(s+1),a[s+1]=1,b[s+1]=b[s]+1;
if(!a[s-1]&&s-1>=0&&s-1<=100000)q.push(s-1),a[s-1]=1,b[s-1]=b[s]+1;
if(!a[s*2]&&s*2<=100000&&s*2>=0)q.push(s*2),a[s*2]=1,b[s*2]=b[s]+1;//将队首元素的后续状态放入队列
}
}
return 0;
}
八、二分
int bsearch(int l, int r)
{
while (l < r)
{
int mid = (l + r)/2;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至1004454362@qq.com