纯模板，望以后忘c++的我可以理解这份备忘录

基础

框架

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	
	return 0;
}

---

排序

void mp(){
	for(ll i=1;i<=n-1;i++){
		if(a[i]>a[i+1]) swap(a[i+1],a[i]);
	}
}
void xp(){
	for(ll i=1;i<=n-1;i++){
		ll k=i;
		for(ll j=i+1;j<=n;j++){
			if(a[j]<a[k]) k=j;
		}
		swap(a[i],a[k]);
	}
}
void cp(){
	for(ll i=2;i<=n;i++){
		ll x=a[i];
		ll j=i-1;
		while(j>=1&&a[j]>x) a[j+1]=a[j],j--;
		a[j+1]=x;
	}
}
void tp(){
	ll cnt=0;
	for(ll i=1;i<=1000;i++){
		if(a[i]!=0) cnt++;
	}
	cout<<cnt<<endl;
	for(ll i=1;i<=1000;i++){
		if(a[i]!=0) cout<<i<<" ";
	}
}
void mg(ll l,ll r){//归并排序
	if(l>=r) return ;
    ll mid=l+r>>1;
	mg(l,mid);
	mg(mid+1,r);
	ll i=l,j=mid+1,cnt=0;
	while(i<=mid&&j<=r){
		if(a[i]<=a[j]) b[++cnt]=a[i++];
		else b[++cnt]=a[j++];
	}
	while(i<=mid) b[++cnt]=a[i++];
	while(j<=r) b[++cnt]=a[j++];
	for(ll i=1;i<=cnt;i++) a[l+i-1]=b[i];
}
void ks(ll l,ll r){//快速排序
	if(l>=r) return ;
	ll p=l+rand()%(r-l+1);
	swap(a[l],a[p]);
	ll i=l,j=r,k=a[l];
	while(i<j){
		while(i<j&&a[j]>=k) j--;
		a[i]=a[j];
		while(i<j&&a[i]<=k) i++;
		a[j]=a[i];
	}
	a[i]=k;
	ks(l,i-1);
	ks(i+1,r);
}

---

二分查找

int a[N];
int er(int l,int r,int x){
    while(l<=r){
    	int mid=(l+r)/2;
    	if(a[mid]==x) return mid;
    	else if(a[mid]>x) r=mid-1;
		else l=mid+1;
	}
	return -1;
}
调用：er(1,n,t);

---

二分答案

ll er(ll l,ll r){
	ll ans=0;
	while(l<=r){
		ll mid=l+r>>1;
		if(check(mid)) l=mid+1,ans=mid;
		else r=mid-1;
	}
	return ans;
}

---

前缀和

int a[N],pre[N];
int n;
for(int i=1;i<=n;i++){
	cin>>a[i];
	pre[i]=pre[i-1]+a[i];
}
int l,r;
cin>>l>>r;
cout<<pre[r]-pre[l-1]<<endl;

---

差分

ll n,p,ans=1e9,a[N],c[N];
for(ll i=1;i<=n;i++) cin>>a[i],c[i]=a[i]-a[i-1];
c[x]+=z;c[y+1]-=z;//修改[x,y]区间和
for(ll i=1;i<=n;i++) c[i]+=c[i-1];

深搜
暴力dfs（枚举类，容易理解最好骗分）

模板
void dfs(ll x){
	if(x==n+1){
        check();
		return ;
	}
    vis[i]=0;    
    dfs(x+1);
    vis[i]=1;        
    dfs(x+1);
}
//全排列
void dfs(ll x){
	if(x==n+1){
		for(ll i=1;i<=n;i++) printf("%5d",ans[i]);
		cout<<"\n";
		return ;
	}
	for(ll i=1;i<=n;i++){
        if(!vis[i]){
            vis[i]=1;
    		ans[x]=i;
    		dfs(x+1);
            vis[i]=0;
        }
	}
}

图上连通块

ll n,m,cnt;
bool a[N][N],vis[N];
void dfs(ll x){
	for(ll i=1;i<=n;i++){
		if(!vis[i]&&a[x][i]){
			vis[i]=true;
			dfs(i);
		}
	}
}
int main(){
	cin>>n>>m;
	for(ll i=1;i<=m;i++){
		ll u,v;cin>>u>>v;
		a[u][v]=a[v][u]=true;
	}
	for(ll i=1;i<=n;i++){
		if(!vis[i]){
			cnt++;
			vis[i]=true;
			dfs(i);
		}
	}
	cout<<cnt;
	return 0;
} 

---

广搜

//迷宫
char a[10][10];
bool vis[10][10];
ll d[4][2]={0,1,1,0,0,-1,-1,0};
struct node{ll x,y,step;};
void bfs(){
	queue<node> q;
	q.push({1,1,0});
	vis[1][1]=1;
	while(!q.empty()){
		node h=q.front();
		q.pop();
		if(h.x==5&&h.y==5){
			cout<<h.step;
			return ;
		}
		for(ll i=0;i<4;i++){
			ll tx=h.x+d[i][0];
			ll ty=h.y+d[i][1];
			ll ts=h.step+1;
			if(tx>=1&&tx<=5&&ty>=1&&ty<=5&&a[tx][ty]=='0'&&vis[tx][ty]==0){
				vis[tx][ty]=1;
				q.push({tx,ty,ts});
			}
		}
	}
	cout<<-1;
}
//连通块
ll n,m,vis[N][N],ans;
char a[N][N];
ll d[8][2]={0,1,1,0,0,-1,-1,0,1,-1,-1,1,1,1,-1,-1};
struct node{ll x,y;};
void bfs(ll x,ll y){
	queue<node> q;
	vis[x][y]=1;
	q.push({x,y});
	while(!q.empty()){
		node h=q.front();
		q.pop();
		for(ll i=0;i<8;i++){
			ll tx=h.x+d[i][0],ty=h.y+d[i][1];
			if(tx<=n&&tx>=1&&ty<=m&&ty>=1&&!vis[tx][ty]&&a[tx][ty]=='连通字符'){
				vis[tx][ty]=1;
				q.push({tx,ty});
			}
		}
	}
    return ;
}
for(ll i=1;i<=n;i++){
		for(ll j=1;j<=m;j++){
            if(!vis[i][j]&&a[i][j]=='连通字符'){
                ans++;
                bfs(i,j);
            }
        }
	}
//最短路径
ll n,m,ans,vis[N];
struct node{
	ll x,step;
};
void bfs(){
	queue<node> q;
	q.push({n,0});
	vis[n]=1;
	while(!q.empty()){
		node h=q.front();
		q.pop();
		if(h.x==m){
			ans=h.step;
			return ;
		}
		ll k=h.x*2;//传送门方式
		if(k<=N&&!vis[k]){
			vis[k]=1;
			q.push({k,h.step+1});
		}
		k=h.x+1;//一步方式
		if(k<=N&&!vis[k]){
			vis[k]=1;
			q.push({k,h.step+1});
		}
		k=h.x-1;//退一步方式
		if(k>=1&&!vis[k]){
			vis[k]=1;
			q.push({k,h.step+1});
		}
        //上述方式可替换，公式如下
        k=h.x;//替换数值
		if(k设置边界&&!vis[k]){
			vis[k]=1;
			q.push({k,h.step+1});
		}
	}
}
//01bfs
void bfs(){
	deque<node> q;
	q.push_back({sx,sy});
	dst[sx][sy]=0;
	while(!q.empty()){
		node h=q.front();
		q.pop_front();
		for(ll i=0;i<4;i++){
			ll tx=h.x+d[i][0],ty=h.y+d[i][1];
			if(tx>=1&&tx<=n&&ty>=1&&ty<=m){
				if(选择1){
					if(dst[tx][ty]>dst[h.x][h.y]+1){
						dst[tx][ty]=dst[h.x][h.y]+1;
						q.push_back({tx,ty});
					}
				}else{//选择2
					if(dst[tx][ty]>dst[h.x][h.y]){
						dst[tx][ty]=dst[h.x][h.y];
						q.push_front({tx,ty});
					}
				}
			}
		}
	}
}
//图上最短路
void bfs(){
	deque<ll> q;
	q.push_back(1);
	dst[1]=0;
	while(!q.empty()){
		ll h=q.front();
		q.pop_front();
		for(ll i=0;i<ve[h].size();i++){
			ll k=ve[h][i];
			if(dst[k]>dst[h]+1){
				dst[k]=dst[h]+1;
				q.push(k);
			}
		}
	}
}
//拓扑排序(bfs思想，本质不是bfs)
ll n,m,siz,ans[N],ind[N];
vector<ll> ve[N];
void tp(){
	queue<ll> q;
	for(ll i=1;i<=n;i++){
		if(ind[i]==0) q.push(i);
	}
	while(!q.empty()){
		ll h=q.front();q.pop();
		ans[++siz]=h;
		for(ll i=0;i<ve[h].size();i++){
			ll k=ve[h][i];ind[k]--;
			if(ind[k]==0) q.push(k);
		}
	}
}
int main(){
	cin>>n>>m;
	for(ll i=1;i<=m;i++){
		ll u,v;cin>>u>>v;
		ve[u].push_back(v);
		ind[v]++;
	}
	tp();
	if(siz!=n) 进行操作
    else 进行操作
	return 0;
} 

---

提高

---

图上最短路
Dijkstra 注：Dijkstra贪心思想，找最小点

void dij(ll n,ll s){
	for(ll i=0;i<=n;i++) dis[i]=1e9;
	dis[s]=0;
	priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> q;
	q.push({dis[s],s});
	while(!q.empty()){
		ll u=q.top().second;
		q.pop();
		if(!vis[u]){
			vis[u]=1;
			for(ll j=0;j<g[u].size();j++){
				ll v=g[u][j].v,w=g[u][j].w;
				if(dis[v]>dis[u]+w){
                    dis[v]=dis[u]+w;
                    q.push({dis[v],v});
                }
			}
		}
	}
}
或
struct node{ll x,y;};
struct Node{
	ll x,dst;
	bool operator<(const Node&other) const{
		return dst>other.dst;
	}
};
vector<node> ve[N];
void dij(){
	priority_queue<Node> q;
	q.push({s,0});
	dst[s]=0;
	while(!q.empty()){
		Node h=q.top();q.pop();
		if(vis[h.x]) continue;
		vis[h.x]=true;
		for(ll i=0;i<ve[h.x].size();i++){
			ll k=ve[h.x][i].x;
			if(dst[k]>dst[h.x]+ve[h.x][i].y){
				dst[k]=dst[h.x]+ve[h.x][i].y;
				q.push({k,dst[k]});
			}
		}
	}
}
时间复杂度：mlogn

Bellman-Ford（暴力的Dijkstra，容易理解，但会被坑）

//未优化
struct node{ll y,z;};
vector<node> v[N];
void bmf(){
	for(ll i=1;i<=n;i++) dis[i]=1e9;
	dis[s]=0;
	for(ll i=1;i<N;i++){
		for(ll j=0;j<v[i].size();j++){
			ll y=v[i][j].y,z=v[i][j].z;
			if(dis[y]>dis[i]+z) dis[y]=dis[i]+z;
		}
	}
}
//优化后（SPFA）（似了[捂脸笑]
void bmf(){
	for(ll i=1;i<=n;i++) dis[i]=1e9;
	dis[s]=0,vis[s]=1;
    queue<ll> q;
    q.push(s);
    while(!q.empty()){
        ll h=q.front();q.pop();vis[h]=0;
		for(ll j=0;j<v[h].size();j++){
			ll x=h,y=v[h][j].y,z=v[h][j].z;
			if(!vis[x]&&dis[y]>dis[x]+z) dis[y]=dis[x]+z,q.push(y);
		}
	}
}
时间复杂度：nm

Floyd

void fld(){//直接输入dis数组，dis在开始就初始化了
	for(ll k=1;k<=n;k++){
		for(ll i=1;i<=n;i++){
			for(ll j=1;j<=n;j++){
				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
			}
		}
	}
}

---

算法技巧
离散化

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+10;
ll n,a[N],b[N];
int main(){
	cin>>n;
	for(ll i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
	sort(b+1,b+n+1);
	ll m=1;
	for(ll i=2;i<=n;i++){
		if(b[m]!=b[i]) b[++m]=b[i];
	}
	for(ll i=1;i<=n;i++){
		cout<<lower_bound(b+1,b+m+1,a[i])-b<<" ";
	}
	return 0;
} 

---

不基础的数据结构
前：基础数据结构：栈、队列、vector
but now:
ST表(展示例子为求最小值)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=5e5+10;
ll n,m,a[N],st[N][20];
void init(){
	for(ll j=1;(1<<j)<=n;j++){
		for(ll i=1;i+(1<<j)-1<=n;i++){
			st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
}
ll find(ll l,ll r){
	ll k=log2(r-l+1);
	ll ans=min(st[l][k],st[r-(1<<k)+1][k]);
	return ans;
}
int main(){
	cin>>n>>m;
	for(ll i=1;i<=n;i++) cin>>st[i][0];
	init();
	for(ll i=1;i<=m;i++){
		ll l,r;cin>>l>>r;
		cout<<find(l,r)<<' ';
	}
	return 0;
} 

单调栈(展示例子为第一个大于$a_i$的，可灵活改变判断条件)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=3e5+10;
ll n,a[N],ans[N];
stack<ll> s;
int main(){
	cin>>n;
	for(ll i=1;i<=n;i++) cin>>a[i];
	for(ll i=n;i>=1;i--){
		while(s.size()&&a[i]>=a[s.top()]) s.pop();
		if(s.size()) ans[i]=s.top();
		else ans[i]=0;
		s.push(i);
	}
	for(ll i=1;i<=n;i++) cout<<ans[i]<<' ';
	return 0;
} 

单调队列/滑动窗口(此处展示的是求区间最大值或最小值)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+10;
ll n,k,a[N];
int main(){
	cin>>n>>k;
	for(ll i=1;i<=n;i++) cin>>a[i];
	deque<ll> q1,q2;
    //最小值
	for(ll i=1;i<=n;i++){
		while(q1.size()&&q1.front()<i-k+1) q1.pop_front();
		while(q1.size()&&a[i]<=a[q1.back()]) q1.pop_back();
		q1.push_back(i);
		if(i>=k) cout<<a[q1.front()]<<' ';
	}
	cout<<'\n';
    //最大值
	for(ll i=1;i<=n;i++){
		while(q2.size()&&q2.front()<i-k+1) q2.pop_front();
		while(q2.size()&&a[i]>=a[q2.back()]) q2.pop_back();
		q2.push_back(i);
		if(i>=k) cout<<a[q2.front()]<<' ';
	}
	return 0;
} 

树状数组

//单点修改，区间查询(此处例子均为区间和)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=5e5+10;
ll n,m,a[N],tr[N];
ll lowbit(ll x){
	return x&-x;
}
void update(ll x,ll k){
	for(ll i=x;i<N;i+=lowbit(i)){
		tr[i]+=k;
	}
}
ll find(ll l){
	ll ans=0;
	for(ll i=l;i>0;i-=lowbit(i)){
		ans+=tr[i];
	}
	return ans;
}
int main(){
	cin>>n>>m;
	for(ll i=1;i<=n;i++) cin>>a[i],update(i,a[i]);
	while(m--){
		ll op,x,y;
		cin>>op>>x>>y;
		if(op==1) update(x,y);
		else cout<<find(y)-find(x-1)<<'\n';
	}
	return 0;
} 
//区间修改，单点查询
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=5e5+10;
ll n,m,a[N],tr[N];
ll lowbit(ll x){
	return x&-x;
}
void update(ll x,ll k){
	for(ll i=x;i<N;i+=lowbit(i)){
		tr[i]+=k;
	}
}
ll find(ll l){
	ll ans=0;
	for(ll i=l;i>0;i-=lowbit(i)){
		ans+=tr[i];
	}
	return ans;
}
int main(){
	cin>>n>>m;
	for(ll i=1;i<=n;i++) cin>>a[i],update(i,a[i]-a[i-1]);
	while(m--){
		ll op;cin>>op;
		if(op==1){
			ll x,y,k;cin>>x>>y>>k;
			update(x,k);
			update(y+1,-k);
		}else{
			ll k;cin>>k;
			cout<<find(k)<<'\n';
		}
	}
	return 0;
}

注意注意，最万能最大托来袭
线段树(此处展示例子为单点修改查找区间最大值最小值与和)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e5+10;
ll n,m,a[N];
struct node{ll mx,mn,sum;}tr[N*4];
void push(ll u){
	tr[u].mx=max(tr[u*2].mx,tr[u*2+1].mx);
	tr[u].mn=min(tr[u*2].mn,tr[u*2+1].mn);
	tr[u].sum=tr[u*2].sum+tr[u*2+1].sum;
}
void build(ll u,ll l,ll r){
	if(l==r){
		tr[u].mx=a[l];
		tr[u].mn=a[l];
		tr[u].sum=a[l];
		return ;
	}
	ll mid=l+r>>1;
	build(u*2,l,mid);
	build(u*2+1,mid+1,r);
	push(u);
}
void update(ll u,ll l,ll r,ll ls,ll rs,ll x){
	if(l==ls&&r==rs){
		tr[u].mx=x,tr[u].mn=x;
		tr[u].sum=x;
		return ;
	}
	ll mid=l+r>>1;
	if(ls<=mid) update(u*2,l,mid,ls,rs,x);
	if(rs>=mid+1) update(u*2+1,mid+1,r,ls,rs,x);
	push(u);
}
ll find1(ll u,ll l,ll r,ll ls,ll rs){
	if(l>=ls&&r<=rs) return tr[u].mx;
	ll mid=l+r>>1,mx=-1e18;
	if(ls<=mid) mx=find1(u*2,l,mid,ls,rs);
	if(rs>=mid+1) mx=max(mx,find1(u*2+1,mid+1,r,ls,rs));
	return mx;
}
ll find2(ll u,ll l,ll r,ll ls,ll rs){
	if(l>=ls&&r<=rs) return tr[u].mn;
	ll mid=l+r>>1,mn=1e18;
	if(ls<=mid) mn=find2(u*2,l,mid,ls,rs);
	if(rs>=mid+1) mn=min(mn,find2(u*2+1,mid+1,r,ls,rs));
	return mn;
}
ll find3(ll u,ll l,ll r,ll ls,ll rs){
	if(l>=ls&&r<=rs) return tr[u].sum;
	ll mid=l+r>>1,sum=0;
	if(ls<=mid) sum+=find3(u*2,l,mid,ls,rs);
	if(rs>=mid+1) sum+=find3(u*2+1,mid+1,r,ls,rs);
	return sum;
}
int main(){
	cin>>n>>m;
	for(ll i=1;i<=n;i++) cin>>a[i];
	build(1,1,n);
	while(m--){
		ll op,l,r;
		cin>>op>>l>>r;
		if(op==1) update(1,1,n,l,l,r);
		else if(op==2) cout<<find1(1,1,n,l,r)<<'\n';
		else if(op==3) cout<<find2(1,1,n,l,r)<<'\n';
		else if(op==4) cout<<find3(1,1,n,l,r)<<'\n';
	}
	return 0;
} 

---

另外的

---

STL容器

//栈
stack<ll> s;
//队列
queue<ll> q;
//优先队列(堆)
priority_queue<ll(存的类型),一个实现优先队列的容器，如vector<ll>,greater<ll>(从小到大)/less<ll>(从大到小)> q;
//排序的
set<ll> s;
//映射(字典)
map<ll,ll> m;
//结构体的变种
pair<ll,ll> p;(不如结构体，拉完了）

---

重载运算符

struct node{
    string xh;
    ll n;
    bool operator<(const node & b)const{
        return n<b.n;(从小到大)
    bool operator<(const node & b)const{
        return n>b.n;(从大到小)
};