前言
基础算法模板 – Echo's blog (liveout.cn)
并查集
一共有 n个数，编号是 1∼n，最开始每个数各自在一个集合中。
现在要进行 m个操作，操作共有两种：
M a b，将编号为 a和 b的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；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;
}
-->
前言基础算法模板 – Echo's blog (liveout.cn)并查集一共有 n个数，编号是 1∼n，最开始每个数各自在一个集合中。现在要进行 m个操作，操作共有两种：M a b，将编号为 a和 b的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；Q a b，询问编号为 和 b 的两个数是否在同一个集合中；#include<iostream>u...
