前言

基础算法模板 – 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;
}

 

标签: C/C++, 数据结构

已有 22 条评论

  1. 二猫 二猫

    嗯，，，，，虽然没看懂，但很赞 :dinosaur-shy:

    回复
    1. Echo Echo

      哈哈 :dinosaur-shy:

      回复
  2. 我吃红提子 我吃红提子

    看不懂，但加油，祝你好运( ^_^)／

    回复
    1. Echo Echo

      哈哈，感谢 :dinosaur-shy:

      回复
  3. czar-alex czar-alex

    加油博主，周六就初赛了

    回复
    1. Echo Echo

      嗯嗯，一起加油，我能拿个奖就行٩(ˊᗜˋ*)و

      回复
  4. 梧桐漓染 梧桐漓染

    加油

    回复
    1. Echo Echo

      嗯啊

      回复
  5. 呜呜 呜呜

    呃呃

    回复
  6. coquetish coquetish

    帅呀

    回复
  7. baihuli baihuli

    测试验证

    回复
  8. George George

    博主好牛?

    回复
    1. Echo Echo

      谢谢～

      回复
      1. George George

        博主，你这个网站访问响应好慢，问题是啥啊，避避雷

        回复
        1. Echo Echo

          图片全部托管在 github 以及服务器里了，还有字体，所以访问很慢。之前是用 cdn，但是欠费了

          回复
          1. George George

            好的，谢谢??

          2. Losst Losst

            试试Edgeone 9.9的套餐？ 我个人用着还不错

          3. Echo Echo

            这是什么呀

  9. zxt zxt

    赞

    回复
  10. George George

    问一下，主播文章是用markdown写的吗，用的什么插件啊，我也想这样

    回复
    1. Echo Echo

      markdown 写的，然后转 html 发布，wp 也有挺多 md 插件，可以搜索下哪个好用

      回复
  1. 1
  2. 2

添加新评论