从零开始的算法模板

### C++基础头文件库及主函数+关闭输入输出流

```cpp
#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cout<<"Hello World"<<'\n';
	return 0;
}
```
### int128+FastIO
```cpp
#include<bits/stdc++.h>
using namespace std;
using Big=__int128;
inline Big read() 
{
    int x=0,f=1;
    char c=getchar();
    while(!isdigit(c))
	{
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)) 
	{
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(Big x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int main()
{
	return 0;
}

```

### 低精度A+B模板

```cpp
#include<bits/stdc++.h>
using namespace std;
int a,b;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>a>>b;
	cout<<a+b<<'\n';
	return 0;
}
// Luogu P1001
```
### 桶排序模板

```cpp
#include<bits/stdc++.h>
#define MAXN 10000010
using namespace std;
int n,x,MAX;
int b[MAXN];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	MAX=0x8f8f8f8f;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>x;
		b[x]++;
		if(x>MAX) MAX=x;
	}
	for(int i=1;i<=MAX;i++)
	{
		if(b[i]>0) cout<<i<<' '<<b[i]<<'\n';
	}
	return 0;
}
//统计n个数中,各个数出现的次数
```
### 快速排序模板（STL封装）

```cpp
#include<bits/stdc++.h>
using namespace std;
int n;
int a[100010];
int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1);
	cout<<a[1];
	for(int i=2;i<=n;i++) cout<<' '<<a[i];
	cout<<'\n';
	return 0;
}//P1177 【模板】排序
```

### 栈模板（vector实现）

```cpp
#include<bits/stdc++.h>
using namespace std;
vector<unsigned long long> vc;
unsigned long long n,x,t;
string o;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(); 
	cin>>t;
	while(t--) 
	{
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>o;//确定操作
			if(o=="push") 
			{
				cin>>x;
				vc.push_back(x);
			}
			if(o=="pop")
			{
			  if(!vc.empty()) vc.pop_back();
			    else cout<<"Empty"<<'\n';
			}
			if(o=="query")
			{
			  if(!vc.empty()) cout<<vc.back()<<'\n';
			    else cout<<"Anguei!"<<'\n'; 
			}
			if(o=="size") cout<<vc.size()<<'\n';
		}
		vc.clear(); 
	} 
	return 0;
} 
//B3614 【模板】栈 
```
### 队列模板（STL模板）

```cpp
#include<bits/stdc++.h>
using namespace std;
int n,o,x;
queue<int> q;
int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>o;
		if(o==1) 
		{
			cin>>x;
			q.push(x);
		} 
		if(o==2)
		{
			if(!q.empty()) q.pop();
			  else cout<<"ERR_CANNOT_POP"<<'\n';
		}
		if(o==3)
		{
			if(!q.empty()) cout<<q.front()<<'\n';
			  else cout<<"ERR_CANNOT_QUERY"<<'\n'; 
		}
		if(o==4) cout<<q.size()<<'\n';
	}
	return 0;
}//B3616 【模板】队列
```
### 01背包模板及结构体

```cpp
#include<bits/stdc++.h>
#define nm 10010
using namespace std;
int n,W;
int f[nm];
struct node
{
	int c,w;//价值 费用 
}a[nm]; 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>W>>n;
	for(int i=1;i<=n;i++) cin>>a[i].w>>a[i].c;
	for(int i=1;i<=n;i++)
	  for(int j=W;j>=a[i].w;j--) 
	    f[j]=max(f[j],f[j-a[i].w]+a[i].c);
	cout<<f[W]<<endl;
	return 0;
}
//P1048 [NOIP2005 普及组] 采药
```

### 大根堆及优先队列模板

```cpp
#include<bits/stdc++.h>
using namespace std;
int n,x;
int b[10000010];
priority_queue<int> q;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) 
	{
		cin>>x;
		if(!b[x])
		{
			q.push(x);
			b[x]=1;
		}
	}
	while(!q.empty())
	{
		cout<<q.top()<<'\n';
		q.pop();
	}
	return 0;
}
//在将n个数去重并压入优先队列 从大到小输出
```
### 小根堆模板

```cpp
#include<bits/stdc++.h>
using namespace std;
int n,x;
int b[10000010];
priority_queue<int,vector<int>,greater<int> > q;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) 
	{
		cin>>x;
		if(!b[x])
		{
			q.push(x);
			b[x]=1;
		}
	}
	while(!q.empty())
	{
		cout<<q.top()<<'\n';
		q.pop();
	}
	return 0;
}
//在将n个数去重并压入优先队列 从小到大输出
```
### 并查集模板

```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=10010;
int n,m,x,y,z;
int fa[maxn];
int find(int x)
{
	if(x==fa[x]) return x;
     else return fa[x]=find(fa[x]);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++)
	{
    	cin>>z>>x>>y; 
        if(z==2)
		{
        	if(find(x)!=find(y)) cout<<"N"<<endl;
			  else cout<<"Y"<<endl;
		}
		  else fa[find(x)]=find(y);	
	}
	return 0;
}//P3367 【模板】并查集
```
### Kruskal模板

```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=5e3;
struct edge
{
	int u,v,w;
}e[(N<<5)|7];
int n,m,ans,sum,cnt;
int fa[N|7];
bool cmp(edge a,edge b)
{
	return a.w<b.w;
}
int find(int x)
{
	if(x!=fa[x]) return fa[x]=find(fa[x]);
	return x;
}
void kru()
{
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;i++)
	{
		int u=find(e[i].u);
		int v=find(e[i].v);
		if(v==u) continue;
		ans+=e[i].w;
		fa[v]=u;
		cnt++;
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;	
	kru();
	cout<<ans<<'\n';
	return 0;
}
```

### 线段树模版

```cpp
#include<bits/stdc++.h>
#define AC 0
#define ll long long
using namespace std;
const int N=1e5+10;
int n,m;
ll a[N];
struct STree
{
    int l,r;
    ll s,lazy;
}tr[N<<2];
void pushup(int u){tr[u].s=tr[u<<1].s+tr[u<<1|1].s;}
void pushdown(int u)
{
    if(tr[u].lazy)
	{
        int lson=u<<1,rson=u<<1|1;
        tr[lson].s+=tr[u].lazy*(tr[lson].r-tr[lson].l+1);
        tr[rson].s+=tr[u].lazy*(tr[rson].r-tr[rson].l+1);
        tr[lson].lazy+=tr[u].lazy;
        tr[rson].lazy+=tr[u].lazy;
        tr[u].lazy=0;
    }
}
void build(int u,int l,int r)
{
    tr[u]={l,r,0,0};
    if(l==r)
	{
        tr[u].s=a[l];
        return;
    }
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}
void update(int u,int l,int r,ll k)
{
    if(tr[u].l>=l&&tr[u].r<=r)
	{
        tr[u].s+=k*(tr[u].r-tr[u].l+1);
        tr[u].lazy+=k;
        return;
    }
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid) update(u<<1,l,r,k);
    if(r>mid) update(u<<1|1,l,r,k);
    pushup(u);
}
ll query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].s;
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    ll res=0;
    if(l<=mid) res+=query(u<<1,l,r);
    if(r>mid) res+=query(u<<1|1,l,r);
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(m--)
	{
        int op,x,y;
        ll k;
        cin>>op;
        if(op==1)
		{
            cin>>x>>y>>k;
            update(1,x,y,k);
        }
			else
			{
            	cin>>x>>y;
            	cout<<query(1,x,y)<<'\n';
        	}
    }
    return AC;
}
```

### 堆优化+Dijkstra

```cpp
#include<bits/stdc++.h>
#define mn 100010
#define inf 0x3f3f3f3f
using namespace std;
int s,t,a,b,c;
struct edge 
{
    int v,nxt,w;
} e[mn<<1];
int h[mn],p;
inline void add(int a,int b,int c) 
{
    e[++p].nxt=h[a];
	h[a]=p;
    e[p].v=b;
	e[p].w=c;
}//存图 
struct node
{
    int x,d;
    bool operator<(const node&b)const{return d>b.d;}
};
priority_queue<node> q;//堆优化 
int n,m,dis[mn];
inline void Dij(int s) 
{
    for(int i=1;i<=n;i++) dis[i]=inf;
    node o;o.x=s,o.d=0;
    q.push(o);
	dis[s]=0;
    while(!q.empty()) 
	{
        node o=q.top();
		q.pop();
        if(o.d!=dis[o.x]) continue;
        int x=o.x,d=o.d;
        for(int i = h[x]; i; i = e[i].nxt)
		{
            int v=e[i].v,w = e[i].w;
            if(dis[v]>dis[x]+w) 
			{
                dis[v]=dis[x]+w;
                node oo;
				oo.x=v,oo.d=dis[v];
                q.push(oo);
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b>>c;
		add(a,b,c);
		add(b,a,c);
	}
	Dij(s);
	cout<<dis[t]<<'\n';
	return 0;
}
//P1339 [USACO09OCT] Heat Wave G
```

正在渲染内容...