模板（基础算法）

并查集

int find(int x){
	return f[x] == x? x : f[x] = find(f[x]);
}
 
void hb(int a,int b){
	int x = find(a);
	int y = find(b);
	
	if(x == y)return;
	f[x] = y;	
}

快速幂

int qpow(int a, int b){
	int res = 1;
	while(b){
		if(b & 1)res = (res * a) % mod;
		
		a = a * a % mod;
		b >>= 1;
	}
	return res % mod;
}

最大公约数 gcd

int gcd(int a, int b){
	if(b == 0) return a;
	retrun gcd(b, a % b);
}

最小公约数 lcm

int lcm(int a, int b){
	return a * b / gcd(a, b);
}

迪杰斯特拉求最短路径

时间复杂度： $O ((n + m) (l o g n))$
空间复杂度： $O (n + m)$

int n, m, s;
void solve(){
    cin>>n>>m>>s;
    vector<pair<int,int>> G[n+10];
 
    rep(i,1,m){
        int a,b,c;cin>>a>>b>>c;
        G[a].push_back({b,c});
    }
 
    vi dis(n + 10, INF); //记录 1 到这个 点 的最短距离
    vi vis(n + 10); //记录这个点是否出圈，也就是是否已经到 到这个点 的最短路径
    dis[s] = 0;
 
    priority_queue <pair<int, int>> q;  //优先队列，现存的最短路
    q.push({0, s});
    while(q.size()){
        auto x = q.top();
        q.pop();
        int a = -x.first;  
        int b = x.second;  
        if(vis[b])continue;//到达这个点的最短的最短路径已经求了 //这个点已经不用再去找了
 
        vis[b] = 1;//遍历这个点之前将 b 标记为 1，表明到达b点的最短路径已经找过了 
        
        for(auto v : G[b]){//从 b 点可以到哪些点
            if(dis[v.first] > dis[b] + v.second){//试图更新到 v 点的最短路径
                dis[v.first] = dis[b] + v.second;
                q.push({-dis[v.first], v.first});//将这个新的最短路径和点放进去
            }
        }
    }
 
    rep(i,1,n){
        if(dis[i] == INF){
            cout<<tmp-1<<(i==n?endl:" ");
        }else{
        cout<<dis[i]<<(i==n?endl:" ");}
    }
    return;
}

欧拉筛 - 线性筛

时间复杂度： $O (n)$
空间复杂度： $O (n)$

int N = 1e7;
vi pr; //素数序列
vi b(N + 10); //记录每个值的最小质因子，原本初始化都为自己
vi f(N + 10, 1); //1代表为素数，0代表为非素数。一开始先假设所有的数都为素数
 
rep(i, 1, N){
    b[i] = i; //初始化
}
f[0] = 0;
f[1] = 0;
 
rep(i, 2, N){
    if(f[i] == 1) pr.push_back(i);
    rep(j, 0, pr.size() - 1){
    
   	 if(pr[j] * i > N){
   		 break;
   	 }
   	 
   	 f[pr[j] * i] = 0;
   	 b[pr[j] * i] = pr[j];
   	 
   	 if(i % pr[j] == 0) break;
    }
}

加了最大质因数的优化版

 int N = 1e7;
 vi pr; //素数序列
 vi b(N + 10); //记录每个值的最小质因子，原本初始化都为自己
 vi c(N + 10); //记录最大质因数
 vi f(N + 10, 1); //1代表为素数，0代表为非素数。一开始先假设所有的数都为素数
 
 rep(i, 1, N){
	 b[i] = i; //初始化
	 c[i] = i;
 }
 
 f[0] = 0;
 f[1] = 0;
 
 rep(i, 2, N){
	 if(f[i] == 1) pr.push_back(i);
	 rep(j, 0, pr.size() - 1){
	 
		 if(pr[j] * i > N){
			 break;
		 }
		 
		 f[pr[j] * i] = 0;
		 b[pr[j] * i] = pr[j];
		 c[pr[j] * i] = max(c[i], pr[j]);
		 
		 if(i % pr[j] == 0) break;
	 }
 }

模逆元 - 费小马定理

时间复杂度： $O (l o g m o d)$
空间复杂度： $O (1)$

int qpow(int a,int b);
 
int mm(int x){
	return qpow(x,mod-2);
}
 
(a / b) % mod -> a * mm (b) % mod;

多重背包+二进制优化

int num=1;
rep(i,1,n){
	cin>>v>>w>>s;
	for(int j=1;j<=s;j<<=1){
		vv[num]=j*v;//存体积
		ww[num++]=j*w；存价值	
	}
	if(s){
		vv[num]=s*v;
		ww[num++]=s*w;
	}
}
 
01背包
rep(i,1,n)
	rep(j,m,1){
	
	}

埃氏筛

int N=1e7;
vi f(N+10,1);记录是否为素数，1为素数，0为非素数，一开始初始化为假设所有数都为素数
vi pr;//存储素数
f[0]=0;
f[1]=0;
 
rep(i,2,N){
	if(f[i]){
		pr.push_back(i);
		for(int j=i*i;j<=N;j+=i){
			f[j]=0;
		}
	}
}

树状数组

时间复杂度 :
建树： $O (n l o g n)$ / $O (n)$
修改 / 查询： $O (l o g n)$
空间复杂度： $O (n)$

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define vi vector<int>
#define vii vector<vector<int>>
const int N=4e5+10;
 
int lowbit(int x){
    return x&(-x);
}
 
void solve(){
    int n,m;cin>>n>>m;
    vi a(n+10);
 
    rep(i,1,n)cin>>a[i];
 
    vi b(n+10);
    rep(i,1,n){
        int p=i;
        while(p<=n){
            b[p]+=a[i];
            p+=lowbit(p);
        }
    }
 
    rep(i,1,m){
        int tmp;cin>>tmp;
 
        if(tmp==1){
            int x,cur;cin>>x>>cur;//加一个数时
 
            int p=x;
            while(p<=n){
                b[p]+=cur;
                p+=lowbit(p);
            }
        }else{
            int x,y;cin>>x>>y;//查询[x,y]的和时
 
            x-=1;
            int p=x;
            int re1=0;
            int re2=0;
            while(p>=1){
                re1+=b[p];
                p-=lowbit(p);
            }
 
            p=y;
            while(p>=1){
                re2+=b[p];
                p-=lowbit(p);
            }
            cout<<re2-re1<<endl;
        }
    }
    return;
}

贝尔曼

处理含有边权为负数的最短路径

时间复杂度： $O (nm)$
空间复杂度： $O (n + m)$
下面的代码主要为枚举每个点的出边
但是如果题目当中 $n$ 和 $m$ 相差不大，意味着这是一个稀疏图，那么我们可以在 $r e p (i, 1, n)$ 里面枚举每条边，时间复杂度 $O (nm)$ ，但是实际运行时间会小得多

第 $n$ 轮还被更新的点，说明达到这个点存在负环

vector<pair<int,int>> G[N];//记录有向边和边权
vi dis(n+10，INF);//记录最短路径
 
dis[1] = 0;
 
int flag=0;//判断每次循环是否有松弛操作发生，若没有发生，说明所有点的最短路径都已经找到，可以跳出循环。 如果循环结束的时候松弛操作还是发生了，说明存在负环，（也就是这个点的最短路径是负数且存在环，不断地循环重复路径，会让这个最短路径越来越小。
rep(i,1,n){
	flag = 0;
	rep(j, 1, n){
		if(dis[j] == INF)continue;//说明这个点还没有到达过，用这个点去更新没有意义
		
		for(auto v:G[j]){
			if(dis[v.first] > dis[j] + v.second){
				flag = 1;
				dis[v.first] = dis[j] + v.second;
			}
		}
	}
	
	if(flag == 0)break;
}
if(flag == 1) cout<<"存在负环"<<endl;
	
rep(i,1,n)cout<<(dis[i]==INF?-1:dis[i])<<" \n"[i==n];

贝尔曼优化 - SPFA

这个优化感觉有点神秘，我有一点看不懂…做题的时候尽量少用吧，除非前面时间复杂度太大了

vector<pair<int,int>> G[N]; //记录有向边和边权
vi dis(n + 10，INF); //记录最短路径
vi cnt(n + 10); //记录边数
vi vis(n + 1);
dis[s] = 0; 
vis[s] = 1;
queue<int> q;
q.push(s);
 
while(!q.empty()){
	int u = q.front();
	q.pop();
	vis[u] = 0;
	for(auto v : G[u]){
		if(dis[u] + v.second < dis[v.first]){
			dis[v.first] = dis[u] + v.second;
			cnt[v] = cnt[u] + 1;
			if(cnt[v] >= n) 表示存在负环，然后跳出这一整个程序
			if(vis[v.first] == 0) q.push(v.first);
			vis[v.first] = 1; 
		}
		
	}
}
 
如果没有前面跳出，那就相当于没有负环	
rep(i,1,n)cout<<(dis[i]==INF?-1:dis[i])<<" \n"[i==n];

区间dp

时间复杂度 $O (n^{3})$

模板题：石子合并

题意
有 $N$ 堆石子排成一排，其编号为 1,2,3,...,N
每堆石子有一定的质量 $m_{i}$ ，现在要将这 $N$ 堆石子合并成为一堆，每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后于这两堆石子相邻的石子将与新堆相邻。

合并时由于选择的顺序不同，合并的总代价也不相同。
试找出一种合理的方法，使总的代价最小，并输出最小代价。

$1 \leq N \leq 300$

题解
用 $f [l] [r]$ 表示合并 $l 到 r$ 的最小代价
🐖： $f [i] [i]$ 表示本来那一堆，代价为 0

合并两堆和代价可以表示为：
$f [l] [r] = f [l] [k] + f [k + 1] [r] + p r e [r] - p r e [l - 1]$

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define vi vector<int> 
#define vii vector<vi>
const int INF = 1e18;
 
void solve(){
    int n;cin>>n;
    vi a(n+10);
    vi pre(n+10);
    vii f(n+10,vi(n+10,INF));
 
    rep(i,1,n){
        cin>>a[i];
        pre[i]=pre[i-1]+a[i];
        f[i][i]=0;//初始化
    }
    
    rep(len,2,n)//枚举区间长度
        for(int l=1;l+len-1<=n;l++){//枚举左区间
            int r=l+len-1;
            rep(k,l,r-1)//枚举中间k
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+pre[r]-pre[l-1]);
        }
 
    cout<<f[1][n]<<endl;
    return;
}
 
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T = 1;
    //cin>>T;
    while(T--) solve();
    return 0;
}

线段树

变量名：

struct node{
	int l;  //左边界
	int r;  //右边界
	int sum; //区间总值
	int add; //懒标记
};

建树

//定义左节点，右节点 , 可以看上图
#define lc p<<1 //左移一位，相当于 p*2 ，速度更快
#define rc (p<<1) + 1

//建立线段树
 
vector<node> tr(4 * n +1);
vector<int> w(n + 1);
 
void pushup(int p){
	tr[p].sum = (tr[lc].sum + tr[rc].sum);
	return;
}
 
void build(int p, int l, int r){
	//先对这个tr[p]进行初始化
	tr[p] = {l, r, 0, 0};
	if(l == r) {
		tr[p].sum = w[l];
		return;
	}
	
	int m = (l + r) >> 1;
	build(lc, l, m);
	build(rc, m+1, r);
	pushup(p);
	return;
}
 
void solve(){
	rep(i, 1, n) cin >> w[i];
	
	build(1, 1, n);  //分别代表，节点编号，区间左段，区间右端
}

区间内每个点统一加 $k$ ——懒标记

//向下传懒标记
void pushdown(int p){
	if(tr[p].add){
		tr[lc].sum += tr[p].add * (tr[lc].r - tr[lc].l + 1);
		tr[rc].sum += tr[p].add * (tr[rc].r - tr[rc].l + 1);
		tr[lc].add += tr[p].add;
		tr[rc].add += tr[p].add;
		tr[p].add = 0;
	}
	return;
}
 
// p为节点编号 ， x 要加 k 的区间的左端点 ， y 为要加 k 的区间的右端点
void update(int p, int x, int y, int k){
	//如果 p 指向的区间包含在 [x,y] 之内，那么就是 p 的区间内每个点都要加上 k
	if(tr[p].l >= x && tr[p].r <= y){
		tr[p].add += k;
		tr[p].sum += k * (tr[p].r - tr[p].l + 1);
		return;
	}
	pushdown(p);
	int m = (tr[p].l + tr[p].r) >> 1;
	if(x <= m) update(lc , x, y, k);
	if(y >= m + 1) update(rc, x, y, k);
	pushup(p);
}

查询

//查询区间 ， 总值为 sum
int query(int p, int x, int y){
	if(tr[p].l >= x && tr[p].r <= y){
		return tr[p].sum;
	}
	pushdown(p);
	int sum = 0;
	int m = (tr[p].l + tr[p].r) >> 1;
	if(x <= m) query(lc, x, y);
	if(y >= m + 1) query(rc, x, y);
	return sum; 
}

单调栈

int n; cin >> n;
//这是找比自己大的
vi l(n + 1), r(n + 1), st;
vi a(n + 1);
 
rep(i, 1, n) cin >> a[i];
rep(i, 1, n){
	if(!st.empty() && a[st.back()] <= a[i]) st.pop_back(); //删到更大为止
	
	l[i] = st.size() == 0 ? 0 : st.back();
	st.push_back(i);
}
 
st.clear();
per(i, n, 1){
	if(!st.empty() && a[st.back()] <= a[i]) st.pop_back();
	
	r[i] = st.size() == 0 ? 0 : st.back();
	st.push_back(i);
}

三分法

适用情况：遇到凸函数求峰点，或者遇到凹函数求谷点的时候
一共存在四个变量，分别为 $l, r, mi d l, mi d r$
$mi d l = (l + r) >> 1$
$mi d r = (mi d l + r) >> 1$

示例代码：

int l = 0, r = n;
while(l < r){
	int midl = (l + r) >> 1;
	int midr = (midl + r) >> 1;
	
	int sum1 = check(midl);
	int sum2 = check(midr);
	if(sum1 < sum2) l = midl;
	else r = midr;
}
cout << l << endl;

最长上升子序列

int lengthLIS(vector<int>& nums) {
    vector<int> res;
    for (int x : nums) {
        auto it = lower_bound(res.begin(), res.end(), x);
        if (it == res.end()) res.push_back(x);
        else *it = x;
    }
    return res.size();
}

没有指针版：

等哪天相通了再来写吧

ST表

用于维护区间最值，与线段树维护区间最值的核心区别在于， $S T$ 表无法中途进行某个值的修改或者某个区间的修改，但在仅仅维护最值这件事上，它得代码量更加少

变量解释：
二维数组， $s t [l e n] [i]$ , 表示 $a [i] 到 a [i + 2^{l e n} - 1]$ 这个区间的最值

vii st(21, vi (n + 1));
 
rep(i, 1, n) st[0][i] = a[i];
 
rep(k, 1, 20){ //构造
	for(int j = 1; j + (1 << k) - 1 <= n; j++){
		st[k][j] = max(st[k - 1][j], st[k][j + (1 << (k - 1))]);
	}
}
 
rep(i, 1, q){ //查询
	int l, r; cin >> l >> r;
	int k = __lg(r - l + 1);
	
	cout << max(st[k][l], st[k][r - (1 << k) + 1]);
}

字典树

//以 0 为根节点出发
vii f(N, vi(30)); //一维记录根节点编号， 二维记录哪个字母, 记录这个的编号
 
int p = 1;
rep(i, 1, n){
	string s; cin >> s;
	int x = 0;
	rep(j, 0, s.size() - 1){
		if(!f[x][s[j]]){
			f[x][s[j]] = p;
			p ++;
			x = p;
		}else{
			x = f[x][s[j]]; 
		}	
	}
}

Adersity breeds strength.

探索