首页 > 编程语言 >C++常见算法&数据结构模版

C++常见算法&数据结构模版

时间:2023-10-01 19:33:30浏览次数:36  
标签:pre int 模版 fath C++ dep 点击 数据结构 dp

各种常见算法 & 数据结构模板

1. 最长不下降子序列(LIS)

1.1 \(O(n^2)\) 做法

点击查看代码
for (int i = 1;i <= n;i++) {
		cin >> a[i];
		dp[i] = 1;
	}
	for (int i = 1;i <= n;i++) {
		for (int j = 1;j < i;j++) {
			if (a[i] > a[j]) {
				dp[i] = max(dp[i],dp[j] + 1);
			}
		}
		ans = max(ans,dp[i]);
	}

1.2 \(O(n \log n)\) 做法

点击查看代码
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int dp[N], n, x, k = 1;
int main() {
    cin >> n >> x;
    dp[1] = x;
    for (int i = 2; i <= n; i++) {
        scanf("%d",&x);
        if (x > dp[k]) {
            dp[++k] = x;
        } else {
            int p = lower_bound(dp + 1, dp + k + 1, x) - dp;
            dp[p] = x;
        }
    }
    cout << k;
    return 0;
}

2. 背包问题

2.1 01背包-二维数组

点击查看代码
	cin >> maxw >> n;
	for (int i = 1;i <= n;i++) {
		cin >> w >> v;
		for (int j = 1;j <= maxw;j++) {
			if (w > j) {
				dp[i][j] = dp[i - 1][j];
			} else {
				dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - w] + v);
			}
		}
	}
	cout << dp[n][maxw];

2.2 01背包-一维数组优化

点击查看代码
	cin >> maxv >> n; // maxv: 价值
	for (int i = 1;i <= n;i++) {
		cin >> v;
		for (int j = maxv;j >= v;j--) {
			dp[j] = max(dp[j],dp[j - v] + v);
		}
	}
	cout << dp[maxv];

2.3 完全背包-一维数组优化

点击查看代码
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 1e4 + 10, S = 1e7 + 10;
ll dp[S], vi, wi, maxw, n;
int main() {
    scanf("%lld%lld", &maxw, &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld%lld", &wi, &vi);
        for (int j = wi; j <= maxw; j++) {
            dp[j] = max(dp[j], dp[j - wi] + vi);
        }
    }
    printf("%lld", dp[maxw]);
    return 0;
}

2.4 多重背包-普通版本

点击查看代码
#include <iostream>

using namespace std;

const int N = 110;
int dp[N], v, s, w;
int n, maxw;
int main() {
    scanf("%d%d", &n, &maxw);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d", &w, &v, &s);
        for (int k = 1; k <= s; k++) {
            for (int j = maxw; j >= w; j--) {
                dp[j] = max(dp[j], dp[j - w] + v);
            }
        }
    }
    printf("%d", dp[maxw]);
    return 0;
}

2.5 多重背包-二进制优化版

点击查看代码
#include <iostream>

using namespace std;

const int N = 2e4 + 10;
int dp[2010], v[N], w[N];
int n, wi, vi, si, maxw, k;
int main() {
    scanf("%d%d", &n, &maxw);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d", &wi, &vi, &si);
        for (int t = 1; t <= si; t *= 2) {
            k++;
            v[k] = t * vi;
            w[k] = t * wi;
            si -= t;
        }
        if (si > 0) {
            k++;
            v[k] = si * vi;
            w[k] = si * wi;
        }
    }
    for (int i = 1; i <= k; i++) {
        for (int j = maxw; j >= w[i]; j--) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    printf("%d", dp[maxw]);
    return 0;
}

2.6 分组背包

点击查看代码
#include <iostream>

using namespace std;

const int N = 110;
int dp[N], v[N][N], w[N][N], s[N];
int n, maxw;
int main() {
    scanf("%d%d", &n, &maxw);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &s[i]);
        for (int j = 1; j <= s[i]; j++) {
            scanf("%d%d", &w[i][j], &v[i][j]);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = maxw; j >= 1; j--) {
            for (int k = 1; k <= s[i]; k++) {
                if (w[i][k] <= j) 
                    dp[j] = max(dp[j], dp[j - w[i][k]] + v[i][k]);
                
            }
        }
    }
    printf("%d", dp[maxw]);
    return 0;
}

2.7 二维费用背包

点击查看代码
#include <iostream>

using namespace std;

const int N = 410;
int dp[N][N], maxw, maxv, vi, wi, c;
int n;
int main() {
    scanf("%d%d", &maxw, &maxv);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> wi >> vi >> c;
        for (int j = maxw; j >= wi; j--) {
            for (int k = maxv; k >= vi; k--) {
                dp[j][k] = max(dp[j][k], dp[j - wi][k - vi] + c);
            }
        }
    }
    cout << dp[maxw][maxv];
    
    return 0;
}

3. 图论最短路

3.1 朴素Dijkstra

时间复杂度:\(O(n^2)\)

点击查看代码
#include <bits/stdc++.h>

using namespace std;

const int N = 60;
int a[N][N];
int d[N];
bool f[N];
int n,s;
int main() {
	cin >> n >> s;
	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= n;j++) {
			cin >> a[i][j];
		}
	}
	memset(d,0x3f,sizeof(d)); // 初始化为INF
	d[s] = 0; // 走到起点的最短路为0
	for (int i = 1;i <= n;i++) {
		int mi = -1; 
      		// 找到最小数下标
		for (int j = 1;j <= n;j++) {
			if (!f[j] && (mi == -1 || d[j] < d[mi])) {
				mi = j;
			}
		}
		f[mi] = true;
      		// 从最短路的点开始更新最短路
		for (int j = 1;j <= n;j++) {
			if (!f[j] && a[mi][j] && a[mi][j] + d[mi] < d[j]) {
				d[j] = a[mi][j] + d[mi];
			}
		}
		
	}
	for (int i = 1;i <= n;i++) {
		if (i != s) {
          		//走不到 -> 0x3f3f3f3f
			if (d[i] == 0x3f3f3f3f) cout << -1 << " ";
			else cout << d[i] << " ";
		}
	}
	return 0;
}

3.2 优先队列BFS优化 Dijkstra

时间复杂度:\(O(m \times logm)\)

点击查看代码
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
typedef pair<int,int> PII;
struct node{
    int to,next,len;
}a[N];
int pre[N],k = 0;
int n,m,x,y,len;
priority_queue<PII,vector<PII>,greater<PII>> q; // 优先队列
void add(int x,int y,int len) { // 建边
    a[++k] = {y,pre[x],len};
    pre[x] = k;
}
bool f[N];
int d[N];
int main() {
    scanf("%d%d",&n,&m);
    for (int i = 1;i <= m;i++) {
        scanf("%d%d%d",&x,&y,&len);
        add(x,y,len);
    }
    // 初始化
    q.push({0,1});
    memset(d,0x3f,sizeof(d));
    d[1] = 0;
    
    while (!q.empty()) {
        PII h = q.top();
        int dis = h.first,p = h.second;
        q.pop();
        if (f[p]) continue;
        f[p] = true;
        if (p == n) { // 走到终点
            cout << dis;
            return 0;
        }
        for (int i = pre[p];i;i = a[i].next) { // 更新最短路
            int to = a[i].to;
            if (a[i].len + dis < d[to]) {
                d[to] = a[i].len + dis;
                q.push({a[i].len + dis,to});
            }
        }
    }
    cout << -1;
    return 0;
}

3.3 Floyd

时间复杂度:\(O(n^3)\)

点击查看代码
#include <bits/stdc++.h>

using namespace std;


const int N = 110,INF = 0x3f3f3f3f;
int d[N][N];
int n,m,x,y,l;
int main() {
	cin >> n >> m;
	memset(d,0x3f,sizeof(d));
	for (int i = 1;i <= n;i++) d[i][i] = 0;
	
	for (int i = 1;i <= m;i++) {
		cin >> x >> y >> l;
		d[x][y] = l;
	}
	for (int k = 1;k <= n;k++) {
		for (int i = 1;i <= n;i++) {
			for (int j = 1;j <= n;j++) {
				if (d[i][k] != INF && d[k][j] != INF) {
					d[i][j] = min(d[i][j],d[i][k] + d[k][j]);
				}
			}
		}
	}
	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= n;j++) {
			if (d[i][j] == INF) cout << "N ";
			else cout << d[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}

4.树

4.1 树的直径

两次深搜求直径:

  1. 从树上任意找一个点 \(x\) 搜索离 \(x\) 最远的点 \(u\) ,\(u\) 一定是直径的一个端点;

  2. 从直径的一个端点 \(u\) 开始搜索,搜索出离 \(u\) 最远的点 \(v\) ,\(v\) 一定是直径的另一个端点,因此 \(uv\) 一定是直径。

点击查看代码
#include <bits/stdc++.h>

using namespace std;

const int N = 110;
int n,x,y;
struct node{
	int to,next;
}a[N * 2];
int pre[N];
int k = 0;
int dep[N];
void add(int x,int y) {
	a[++k] = {y,pre[x]};
	pre[x] = k;
}


void dfs(int x,int fath) {
	dep[x] = dep[fath] + 1;
	for (int i = pre[x];i;i = a[i].next) {
		if (a[i].to != fath) {
			dfs(a[i].to,x);
		}
	}
}

int main() {
	cin >> n;
	for (int i = 1;i <= n - 1;i++) {
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	dfs(1,0);
	int x = 1;
  	// 求出离1号点最远的那个点
	for (int i = 2;i <= n;i++) {
		if (dep[i] > dep[x]) x = i;
	}
	dfs(x,0);
	int y = 1;
  	// 找出离x号点最远的点y
	for (int i = 1;i <= n;i++) {
		if (dep[i] > dep[y]) y = i;
	}
	printf("%d",dep[y] - 1);

4.2 树的中心

树的中心指的是,该结点离树中的其他结点,最远距离最近

树的中心满足如下性质:

(1)它一定在某条树的直径上,且到直径的两端的距离差不超过1

(2)即使树有多条直径,但树的中心至多有2个,且均为直径的中点。

求树的中心:由于树的中心一定在直径上,求出直径的两个端点 \(u v\),加深 \(v\) 深度更深。

(1) 如果 \(dep[v]\) 是奇数,爬树 \(dep[v]/2\) 次;

(2) 如果 \(dep[v]\) 是偶数,爬树 \(dep[v]/2-1\) 次,得到两个中心的靠下的一个点,另一个点就是该点的父;

点击查看代码
#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int n,x,y;
struct node{
	int to,next;
}a[N * 2];
int pre[N];
int k = 0;
int dep[N],fa[N];
void add(int x,int y) {
	a[++k] = {y,pre[x]};
	pre[x] = k;
}


void dfs(int x,int fath) {
	dep[x] = dep[fath] + 1;
	fa[x] = fath;
	for (int i = pre[x];i;i = a[i].next) {
		if (a[i].to != fath) {
			dfs(a[i].to,x);
		}
	}
}

int main() {
	cin >> n;
	for (int i = 1;i <= n - 1;i++) {
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	dfs(1,0);
	int x = 1;
	for (int i = 2;i <= n;i++) {
		if (dep[i] > dep[x]) x = i;
	}
	dfs(x,0);
	int y = 1;
	for (int i = 1;i <= n;i++) {
		if (dep[i] > dep[y]) y = i;
	}
	if (dep[y] % 2 == 1) {
		int d = dep[y] / 2;
		for (int i = 1;i <= d;i++) {
			y = fa[y];
		}
		printf("%d",y);
	} else {
		int d = dep[y] / 2 - 1;
		for (int i = 1;i <= d;i++) {
			y = fa[y];
		}
		if (y < fa[y]) cout << y << " " << fa[y];
		else cout << fa[y] << " " << y;
	}
	return 0;
}

4.3 树的公共祖先(LCA)

解法一:染色法

点击查看代码
#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int n,x,y;
struct node{
	int to,next;
}a[N * 2];
int pre[N];
int k = 0;
int dep[N],fa[N];
void add(int x,int y) {
	a[++k] = {y,pre[x]};
	pre[x] = k;
}
bool vis[N];

void dfs(int x,int fath) {
	dep[x] = dep[fath] + 1;
	fa[x] = fath;
	for (int i = pre[x];i;i = a[i].next) {
		if (a[i].to != fath) {
			dfs(a[i].to,x);
		}
	}
}

int main() {
	cin >> n;
	int u,v;
	cin >> u >> v;
	for (int i = 1;i <= n - 1;i++) {
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	dfs(1,0);
	vis[u] = true;
	while (fa[u] != 0) {
		u = fa[u];
		vis[u] = true;
	}
	while (!vis[v]) {
		v = fa[v];
	}
	cout << v;
	return 0;
}

解法二:两个结点同时向上移动

思路:

(1)求出每个结点的深度;

(2)如果两个结点重叠,那么得知公共祖先;

(3)如果不重叠,选择深度更大的结点,向父元素移动,重复上述过程,直到重叠。

点击查看代码
#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int n,x,y;
struct node{
	int to,next;
}a[N * 2];
int pre[N];
int k = 0;
int dep[N],fa[N];
void add(int x,int y) {
	a[++k] = {y,pre[x]};
	pre[x] = k;
}
bool vis[N];

void dfs(int x,int fath) {
	dep[x] = dep[fath] + 1;
	fa[x] = fath;
	for (int i = pre[x];i;i = a[i].next) {
		if (a[i].to != fath) {
			dfs(a[i].to,x);
		}
	}
}

int main() {
	cin >> n;
	int u,v;
	cin >> u >> v;
	for (int i = 1;i <= n - 1;i++) {
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	dfs(1,0);
	while (u != v) {
		if (dep[u] > dep[v]) {
			u = fa[u];
		} else {
			v = fa[v];
		}
	}
	cout << u;
	
	return 0;

4.4 树的重心

求出每个结点删除后的最大子树的大小,并求出该值的最小值,最后循环看哪些树删除后子树大小==所求的最小值,哪些结点就是重心。

点击查看代码
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int n,x,y;
struct node{
	int to,next;
}a[N * 2];
int pre[N];
int k = 0;
int dep[N],fa[N],si[N];
int ma[N];
int mi = INT_MAX;
void add(int x,int y) {
	a[++k] = {y,pre[x]};
	pre[x] = k;
}
bool vis[N];

int dfs(int x,int fath) {
	dep[x] = dep[fath] + 1;
	fa[x] = fath;
	si[x] = 1;
	for (int i = pre[x];i;i = a[i].next) {
		if (a[i].to != fath) {
			si[x] += dfs(a[i].to,x);
		}
	}
	return si[x];
}

int main() {
	cin >> n;
	for (int i = 1;i <= n - 1;i++) {
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	dfs(1,0);
	for (int i = 1;i <= n;i++) {
		ma[i] = n - si[i];
		for (int j = pre[i];j;j = a[j].next) {
			if (a[j].to != fa[i]) {
				ma[i] = max(ma[i],si[a[j].to]);
			}
		}
		mi = min(ma[i],mi);
	}
	for (int i = 1;i <= n;i++) {
		if (ma[i] == mi) {
			cout << i << " ";
		}
	}
	return 0;
}

5.最长公共子序列(LCS)

5.1 \(O(n^2)\) 做法

点击查看代码
#include <iostream>

using namespace std;

const int N = 1010;
int n, dp[N][N], a[N], b[N];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i] == b[j]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    printf("%d", dp[n][n]);
    return 0;
}

5.2 \(O(n \log n)\) 做法

点击查看代码
#include <iostream>

using namespace std;

const int N = 1e5 + 10;
int dp[N], a[N], b[N], n, c[N];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        c[a[i]] = i;
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    dp[1] = c[b[1]];
    int k = 1;
    for (int i = 2; i <= n; i++) {
        if (c[b[i]] > dp[k]) {
            dp[++k] = c[b[i]];
        } else {
            int p = lower_bound(dp + 1, dp + k + 1, c[b[i]]) - dp;
            dp[p] = c[b[i]];
        }
    }
    printf("%d", k);
    return 0;
}

6. 并查集

6.1 朴素并查集

点击查看代码
int find(int x) {
	if (x == fa[x]) return x;
	return find(fa[x]);
}
点击查看代码
void merge(int x, int y) {
	int rx = find(x), ry = find(y);
	if (rx != ry) fa[rx] = ry;
}

6.2 路径压缩

点击查看代码
int find(int x) {
	if (x == fa[x]) return x;
	return fa[x] = find(fa[x]);
}

7. 最小生成树

7.1 \(Kustral\) 算法

点击查看代码
for (int i = 1;i <= k;i++) {
		if (find(a[i].x) != find(a[i].y)) {
			merge(a[i].x, a[i].y);
			sum += a[i].len;
			c++;
			
			if (c == n - 1) {
				printf("%d", sum);
				return 0;
			}
		}
	}

8. 素数筛法

8.1 埃氏筛法

点击查看代码
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;
bool f[N];
int n, ans;
int main() {
	scanf("%d", &n);
	f[0] = f[1] = true;
	for (int i = 2;i <= sqrt(n);i++) {
		if (!f[i]) {
			for (int j = i * 2;j <= n;j += i) {
				if (!f[j]) {
					f[j] = true;
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		if (!f[i]) ans++;
	}
	printf("%d", ans);
	return 0;
}

8.2 欧拉筛法

点击查看代码
f[0] = f[1] = true;
	for (int i = 2;i <= e;i++) {
		if (!f[i]) primes[++k] = i;
		for (int j = 1;i * primes[j] <= e;j++) {
			f[i * primes[j]] = true;
			if (i % primes[j] == 0) break;
		}
	}

标签:pre,int,模版,fath,C++,dep,点击,数据结构,dp
From: https://www.cnblogs.com/yhx0322/p/17739165.html

相关文章

  • C++ STL标准容器的特点和典型的使用场景
    概念和作用C++标准模板库(StandardTemplateLibrary,STL)提供了一组通用的模板类和函数,用于处理常见的数据结构和算法。STL中的标准容器是其中的重要组成部分,它们提供了不同的数据结构和操作方式,适用于各种不同的使用场景。说白了,就是每一种容器代表一种特定的数据结构。我们在学C......
  • C++对拍模版
    Windowscheck.cpp#include<bits/stdc++.h>usingnamespacestd;intmain(){ while(true) { system("data.exe"); system("std.exe"); system("brute.exe"); if(system("fcstd.outbrute.out"))......
  • C++快读、快写模版
    inlineintread(){ charch=getchar(); intx=0,f=1; while(!isdigit(ch))if(ch=='-')f=-1,ch=getchar(); while(isdigit(ch))x=x*10+ch-'0',ch=getchar(); returnx*f;}inlinevoidprint(intn){if......
  • Python代码转换成C++
    Python和C++是两种不同的编程语言,但它们都有各自的优势和适用场景。在某些情况下,我们可能需要将Python代码转换成C++代码,以获得更高的执行效率或更好的性能。本文将从多个方面介绍如何将Python代码转换为C++代码。一、代码结构Python和C++在代码结构上存在一些差异。Python是一种解......
  • C/C++学习 -- 流加密算法(RC4算法)
    在信息安全领域,加密算法扮演着至关重要的角色。其中,RC4算法是一种广泛使用的流密码算法,用于数据的保密性和机密性。本文将深入探讨RC4算法的概述、特点、原理,以及提供C语言和C++语言实现RC4算法的代码案例。一、RC4算法概述RC4算法,又称RivestCipher4或Ron'sCode4,是一种流密码(St......
  • Go每日一库之155:go-spew(输出 Go 数据结构)
    对于应用的调试,我们经常会使用fmt.Println来输出关键变量的数据。或者使用log库,将数据以log的形式输出。对于基础数据类型,上面两种方法都可以比较方便地满足需求。对于一些结构体类型数据,通常我们可以先将其序列化后再输出。如果结构体中包含不可序列化的字段,比如func类型......
  • C++中悬垂指针(delete后指针)仍然可以访问所指内存的问题
    C++中悬垂指针(delete后指针)仍然可以访问所指内存的问题在指针被delete之后,此时指针被称为空悬指针或者悬垂指针,即指向一块曾经保存数据对象,但现在已经无效的内存的指针。在C++编程中,当我们delete一个指针后,指针所指向的堆地址空间便被释放,指针值变成无效,该内存可以用于之后的内......
  • C/C++中的ACM题目输入处理——简单易上手
    这里就不按其他文章的以各种情况为分类方法,而是以方法本身为分类办法。因为有一些方法是不同情况通用的,比如已知数量数字的输入和未知数量数字的输入,其实可以用同一种办法。输入C/C++:scanf正则表达式头文件<stdio.h>或<cstdio>普通使用时,语法为scanf("%d",&a),当遇到空格符、......
  • C++ 转换构造函数
    在C++中如果一个构造函数只有一个参数,那么这个构造函数就是转换构造函数(ConvertingConstructor),这个构造函数可以将参数类型转换成构造函数所在的类对应的类型。举个例子,假设有如下类Complex:1classComplex{2private:3inti;4intj;56public:......
  • 位图&布隆过滤器剖析 #C++
    位图位图概述位图(bitset)中存储位(bit),每个元素只有两个可能值,1/0或者true/false。与bool数组相比,位图的空间开销更小,每个元素占据1bit空间,是C++最小内置类型char的八分之一。位图是哈希思想衍生出的容器,在完成哈希表判断元素存在功能的同时,极大地节省了所需的内存空间。位图......