前言

基础算法模板 – Echo's blog (liveout.cn)

---

并查集

一共有 n个数，编号是 1∼n，最开始每个数各自在一个集合中。

现在要进行 m个操作，操作共有两种：

1. M a b，将编号为 a和 b的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
2. Q a b，询问编号为 和 b 的两个数是否在同一个集合中；

#include<iostream>
using namespace std;
const int N=100010;
int p[N];//定义多个集合

int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) p[i]=i;
    while(m--)
    {
        char op[2];
        int a,b;
        scanf("%s%d%d",op,&a,&b);
        if(*op=='M') p[find(a)]=find(b);
        else
        if(find(a)==find(b))
        printf("Yes\n");
        else
        printf("No\n");
    }
    return 0;
}

 

单调栈

给定一个长度为 N的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1−1

#include <iostream>
using namespace std;
const int N = 1e5+10;
int n;
int stk[N], tt;

int main()
{
    cin >> n;
    for (int i=0; i<n; i++)
    {
        int x;
        cin >> x;
        while (tt && stk[tt] >= x) tt--;
        
        if (tt) cout << stk[tt] << ' ';
        else cout << -1 << ' ';
        
        stk[++tt] = x;
    }
    return 0;
}

 

搜索

DFS（排列数字）

给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。

现在，请你按照字典序将所有的排列方法输出。

#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;
		}
	}
}

int main()
{
	cin >> n;
	dfs(1);
	
	return 0;
}

 

BFS（迷宫）

给定一个 n×m的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。

最初，有一个人位于左上角 (1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问，该人从左上角移动至右下角 (n,m) 处，至少需要移动多少次。

数据保证 (1,1) 处和 (n,m)处的数字为 0，且一定至少存在一条通路。

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
const int N = 110;
int n, m;
int g[N][N]; //迷宫 
int d[N][N]; //每一个点到起点距离 

int bfs()
{
	queue<PII> q;
	memset(d, -1, sizeof d);
	d[0][0] = 0;
	q.push({0,0}); //起点 
	
	int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
	while (q.size())
	{
		auto t = q.front();
		q.pop();
		for (int i=0; i<4; i++)
		{
			int x = t.first+dx[i], y = t.second+dy[i];
			if (x>=0 && x<n && y>=0 && y<m && g[x][y] == 0 && d[x][y]==-1)
			{
				d[x][y] = d[t.first][t.second]+1;
				q.push({x,y}); //下一个点	
			}
		}
	}
	return d[n-1][m-1];
}
 
int main()
{
	cin >> n >> m;
	for (int i=0; i<n; i++)
		for (int j=0; j<m; j++)
			cin >> g[i][j];
	cout << bfs() << endl;
	
	return 0;
}

 

BFS (图中点的层次)

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环。

所有边的长度都是 1，点的编号为 1∼n.

请你求出 1 号点到 n 号点的最短距离，如果从 1 号点无法走到 n 号点，输出 −1。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+10;

int h[N], e[N], ne[N], idx;
int d[N]; //存储每个节点离起点的距离  d[1]=0
int n, m;


void add(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;	
} 

int bfs()
{
	memset(d, -1, sizeof d);
	queue<int> q;
	d[1] = 0; //存储每个节点离起点的距离
	q.push(1);
	while (q.size())
	{
		int t = q.front();
		q.pop();
		
		for (int i=h[t]; i != -1; i=ne[i])
		{
			int j=e[i];
			if (d[j] == -1)
			{
				d[j] = d[t] + 1; //d[j]存储j节点离起点的距离，并标记为访问过
				q.push(j);
			}
		}
	}
	return d[n];
}

int main()
{
	cin >> n >> m;
	memset(h, -1, sizeof h);
	
	for (int i=0; i<m; i++)
	{
		int a, b;
		cin >> a >> b;
		add(a, b);
	}
	cout << bfs();
	return 0;
}

 

Dijkstra(优化版)

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n号点，则输出 −1。

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
const int N = 1e6+10;

// 稀疏图用邻接表来存
int h[N], w[N], e[N], ne[N], idx;
int dist[N]; //1 号点到 n 号点的最短距离
bool st[N]; // 如果为true说明这个点的最短路径已经确定

int n, m;

void add(int x, int y, int c)
{
    // 有重边也不要紧，假设1->2有权重为2和3的边，再遍历到点1的时候2号点的距离会更新两次放入堆中
    // 这样堆中会有很多冗余的点，但是在弹出的时候还是会弹出最小值2+x（x为之前确定的最短路径），
    // 并标记st为true，所以下一次弹出3+x会continue不会向下执行。
	w[idx] = c;
	e[idx] = y; ne[idx] = h[x]; h[x] = idx ++;
}

int dijkstra()
{
	memset(dist, 0x3f, sizeof dist);
	dist[1] = 0;
    
    //首先小根堆是根据距离来排的，所以有一个变量要是距离，
    // 其次在从堆中拿出来的时候要知道知道这个点是哪个点，不然怎么更新邻接点呢？所以第二个变量要存点
	priority_queue<PII, vector<PII>, greater<PII>> heap;
	heap.push({0, 1}); //距离＋点  // 这个顺序不能倒，pair排序时是先根据first，再根据second，
	
	while (heap.size())
	{
		PII k = heap.top(); // 取不在集合S中距离最短的点
		heap.pop();
		int distance = k.first, ver = k.second;
		if (st[ver]) continue;
		st[ver] = true;
		
		for (int i=h[ver]; i != -1; i=ne[i])
		{
			int j = e[i]; // i只是个下标，e中在存的是i这个下标对应的点。
			if (dist[j] > dist[ver] + w[i])
			{
				dist[j] = dist[ver] + w[i];
				heap.push({dist[j], j});
			}
		}
	}
	if (dist[n] == 0x3f3f3f3f) return -1;
	else return dist[n];
}



int main()
{
	memset(h, -1, sizeof h);
	cin >> n >> m;
	
	while (m --)
	{
		int x, y, c;
		cin >> x >> y >> c;
		add(x, y, c);
	}
	cout << dijkstra() << endl;
	
	return 0;
}

 

Floyd求最短路

给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。

再给定k个询问，每个询问包含两个整数x和y，表示查询从点x到点y的最短距离，如果路径不存在，则输出“impossible”。

数据保证图中不存在负权回路

#include <iostream>
using namespace std;

const int N = 210, M = 2e+10, INF = 1e9;

int n, m, k, x, y, z;
int d[N][N];

void floyd() {
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

int main() {
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(i == j) d[i][j] = 0;
            else d[i][j] = INF;
    while(m--) {
        cin >> x >> y >> z;
        d[x][y] = min(d[x][y], z);
        //注意保存最小的边
    }
    floyd();
    while(k--) {
        cin >> x >> y;
        if(d[x][y] > INF/2) puts("impossible");
        //由于有负权边存在所以约大过INF/2也很合理
        else cout << d[x][y] << endl;
    }
    return 0;
}

 

DP

01背包

有 N件物品和一个容量是 V的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX = 1005;
int v[MAX];
int w[MAX];
int f[MAX];

int main()
{
    int n,m;
    cin >> n >> m;
    for (int i=1; i<=n; i++)
        cin >> v[i] >> w[i];
    
    for (int i=1; i<=n; i++)
        for (int j=m; j>=v[i]; j--)
        {
           f[j] = max(f[j],f[j-v[i]]+w[i]);
        }
    
    cout << f[m] << endl;
    return 0;
}

 

完全背包

有 N种物品和一个容量是 V 的背包，每种物品都有无限件可用。

第 i 种物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N];

int main()
{
    cin >> n >> m;
    for (int i=1; i<=n; i++) cin >> v[i] >> w[i];
    
    for (int i=1; i<=n; i++)
        for (int j=v[i]; j<=m; j++)
            f[j] = max(f[j], f[j-v[i]]+w[i]);
            
    cout << f[m] << endl;
    
    return 0;
}

 

多重背包问题

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。 输出最大价值。

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int v[N], w[N], s[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    
    for (int i=1; i<=n; i++) cin >> v[i] >> w[i] >> s[i];
    
    for (int i=1; i<=n; i++)
        for (int j=0; j<=m; j++)
            for (int k=0; k<=s[i] && k*v[i] <= j; k++)
                f[i][j] = max(f[i][j], f[i-1][j-v[i]*k] + w[i]*k);
                
    cout << f[n][m] << endl;
    return 0;
}

 

线性DP（最长上升子序列）

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
int a[N];
int q[N];

int main()
{
    scanf("%d", &n);
    for (int i=0; i<n; i++) scanf("%d", &a[i]);
    
    int len = 0;
    for (int i=0; i<n; i++)
    {
        int l=0, r = len;
        while (l < r)
        {   //二分
            int mid  = l + r + 1 >> 1;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, r+1);
        q[r+1] = a[i];
    }
    printf("%d\n", len);
    
    return 0;
}

 

线性DP（最长公共子序列）

给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。

输入格式

第一行包含两个整数 N 和 M。

第二行包含一个长度为 N 的字符串，表示字符串 A。

第三行包含一个长度为 M 的字符串，表示字符串 B。

字符串均由小写字母构成。

输出格式

输出一个整数，表示最大长度。

数据范围

1≤N,M≤1000

输入样例：

4 5
acbd
abedc

输出样例：

3

代码

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];

int main()
{
    scanf("%d%d", &n, &m);
    scanf("%s%s", a+1, b+1);
    
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
        {
            f[i][j] = max(f[i-1][j], f[i][j-1]);
            if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i-1][j-1]+1);
        }
    printf("%d\n",f[n][m]);
    
    return 0;   
}

 

区间DP（石子合并）

设有 N 堆石子排成一排，其编号为 1,2,3,…,N。

每堆石子有一定的质量，可以用一个整数来描述，现在要将这 N 堆石子合并成为一堆。

每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。

例如有 4 堆石子分别为 1 3 5 2， 我们可以先合并 1、2 堆，代价为 4，得到 4 5 2， 又合并 1、2 堆，代价为 9，得到 9 2 ，再合并得到 11，总代价为 4+9+11=24；

如果第二步是先合并 2、3 堆，则代价为 7，得到 4 7，最后一次合并代价为 11，总代价为 4+7+11=22。

问题是：找出一种合理的方法，使总的代价最小，输出最小代价。

模板

for (int len = 1; len <= n; len++) {         // 区间长度
    for (int i = 1; i + len - 1 <= n; i++) { // 枚举起点
        int j = i + len - 1;                 // 区间终点
        if (len == 1) {
            dp[i][j] = 初始值
            continue;
        }

        for (int k = i; k < j; k++) {        // 枚举分割点，构造状态转移方程
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]);
        }
    }
}

 

#include <iostream>
#include <cstring>

using namespace std;

const int N = 307;

int a[N], s[N];
int f[N][N];

int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        s[i] += s[i - 1] + a[i];
    }

    memset(f, 0x3f, sizeof f);
    // 区间 DP 枚举套路：长度+左端点 
    for (int len = 1; len <= n; len ++) { // len表示[i, j]的元素个数
        for (int i = 1; i + len - 1 <= n; i ++) {
            int j = i + len - 1; // 自动得到右端点
            if (len == 1) {
                f[i][j] = 0;  // 边界初始化
                continue;
            }

            for (int k = i; k <= j - 1; k ++) { // 必须满足k + 1 <= j
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
            }
        }
    }

    cout << f[1][n] << endl;


    return 0;
}

 

线性DP（数字矩阵和）

小蓝有一个 3 行 6 列的数字矩阵，矩阵中的每个数都是 0 到 9 之间的数字。现在小蓝想从这个矩阵的第一行第一列画一条折线到第 3 行 6 列，线只能沿水平向右走或竖直向下走，只能在有数字的地方拐弯。小蓝想知道，这样一条线经过的数字的和最大是多少。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 35, M = 65;

int n = 30, m = 60;
char g[N][M];
int f[N][M];

int main()
{
for(int i = 1; i <= n; i ++) scanf("%s", g[i] + 1);

// cout << "?" << endl;

for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
{
f[i][j] = max(f[i - 1][j], f[i][j - 1]) + g[i][j] - '0';
}
cout << f[n][m] << endl;

return 0;
}

 

记忆化搜索（滑雪）

小蓝准备在一个空旷的场地里面滑行，这个场地的高度不一，小蓝用一个 n 行 m 列的矩阵来表示场地，矩阵中的数值表示场地的高度。 如果小蓝在某个位置，而他上、下、左、右中有一个位置的高度（严格）低于当前的高度，小蓝就可以滑过去，滑动距离为 1 。 如果小蓝在某个位置，而他上、下、左、右中所有位置的高度都大于等于当前的高度，小蓝的滑行就结束了。 小蓝不能滑出矩阵所表示的场地。 小蓝可以任意选择一个位置开始滑行，请问小蓝最多能滑行多远距离。

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 110;
int n, m;
int g[N][N], f[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; //dx上下 dy左右  

int dp(int x, int y) //dfs
{
	int &v = f[x][y];
	if (v != -1) return v;
	v = 1;
	for (int i=0; i<4; i++)
	{
		int a = x + dx[i], b = y + dy[i];
		if (a >= 1 && a <= n && b >= 1 && b <= m && g[x][y] > g[a][b])
			v = max(v, dp(a, b)+1); //dp(a, b)+1 表示从(a,b)到下一个点，中间加一
	}
	return v;
}

int main()
{
	cin >> n >> m;
	for (int i=1; i<=n; i++)
		for (int j=1; j<=m; j++)
			cin >> g[i][j];
			
	memset(f, -1, sizeof f);
	
	int res = 0;
	for (int i=1; i<=n; i++)
		for (int j=1; j<=m; j++)
			res = max(res, dp(i, j));
	cout << res;
}

 

数论

分解质因数

给定 n 个正整数 ai，判定每个数是否是质数。

#include <iostream>
#include <algorithm>

using namespace std;

bool is_prime(int x)
{
    if (x < 2) return false;
    for (int i=2; i<=x/i; i++)
    {
        if (x%i ==  0) return false;
    }
    return true;
}

int main()
{
    int n;
    cin >> n;
    while (n --)
    {
        int x;
        cin >> x;
        if (is_prime(x)) puts("Yes");
        else puts("No");
    }
    return 0;
}

 

判断闰年

#include<iostream>
using namespace std;

int main()
{
	int year;
	cin>>year;	//键盘中输入一个年份，保存到变量year中

	if((year%4 == 0 && year%100 != 0)|| year%400 == 0)//指定是否为闰年的判断条件
		cout<< year << "是闰年" << endl;	//条件成立则该年份是闰年
	else
		cout << year << "不是闰年" << endl;	//否则该年份不是闰年
	return 0;
}

 

进制转换(转换成10进制)

int convert(string s)
{
    //base为进制
	int sum = 0;
	for(int i = 0; i < s.size(); i ++)
  		sum = sum * base + s[i] - '0';
	return sum;
}

 

进制转换(10进制转换成 base 进制)

#include<bits/stdc++.h>
using namespace std;
int a,b;
char d[16]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
//0~16对应的编码

void jz(int k,int base)//将k转化为n进制数
{
    int r;
    r = k % base;//对n求余
    k = k / base;//除n
    if(k != 0)//k==0为边界条件
        jz(k, base);//递归
    cout << d[r];//输出对应编码
    return;
}
int main()
{
    cin>>a>>b;
    jz(a, b);
    return 0;
}

 

求最大公约数

#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int a, int b)
{
    return b ? gcd(b, a%b) : a;
}
int main() 
{
    int a, b;
    cin >> a >> b;
    cout<< gcd(a, b);
} 

 

求公约数及个数

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> get_divistors(int x) //求约数
{
    vector<int> res;
    for (int i=1; i<=x/i; i++)
        if (x % i == 0)
        {
            res.push_back(i);
            if (i != x/i) res.push_back(x/i);
        }
    sort(res.begin(), res.end());
    return res;
}

int main()
{
    int n;
    cin >> n;
    while (n --)
    {
        int x;
        cin >> x;
        auto res = get_divistors(x);
        for (auto x : res) cout << x << " "; //遍历存取约数的数组
        cout << endl;
        cout << res.size(); //约数个数
    }

    return 0;
}