【C++】一些模板

未分类
2.5k 词

动态规划

01背包

模板题链接：P1048 [NOIP 2005 普及组] 采药

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;

int m, n, w[N], c[N], dp[N];

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

完全背包

模板题链接：B2174 完全背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;

int m, n, w[N], c[N], dp[N];

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

多重背包

模板题链接：B2173 多重背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int m, n, w[N], c[N], dp[N], len, x, y, z;

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		cin >> x >> y >> z;
		int cnt = 1;
		while (z >= cnt)
		{
			len++;
			w[len] = cnt * x;
			c[len] = cnt * y;
			z -= cnt;
			cnt *= 2;
		}
		if (z)
		{
			len++;
			w[len] = z * x;
			c[len] = z * y;
		}
	}
	for (int i = 1; i <= len; i++)
		for (int j = m; j >= w[i]; j--)
				dp[j] = max(dp[j], dp[j - w[i]] + c[i]);
	cout << dp[m];
	
	return 0;
}

数据结构

并查集

模板题链接：P3367 【模板】并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;

const int N = 2 * 1e6 + 10;

int n, m, type, x, y, fa[N];

int find(int x)
{
	if (x == fa[x])
		return x;
	else
		return fa[x] = find(fa[x]); // 🦌径🦆缩
//		return find(fa[x]);         // 没🦌径🦆缩
}

void uio(int x, int y)
{
	int fx = find(x), fy = find(y);
	if (fx != fy)
		fa[fy] = fx;
	return ;
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		fa[i] = i;
	for (int i = 1; i <= m; i++)
	{
		cin >> type >> x >> y;
		if (type == 1)
			uio(x, y);
		else
			if (find(x) == find(y))
				cout << "Y" << endl;
			else
				cout << "N" << endl;
	}
	
	return 0;
}

树状数组

模板题链接：P3374 【模板】树状数组 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;

const int N =  5 * 1e5 + 10;

int n, m, a[N], bit[N];

int lowbit(int x)
{
	return x & (-x);
}

void add(int p, int x)
{
	while (p <= n)
		bit[p] += x, p += lowbit(p);
}

int sum(int p)
{
	int ans = 0;
	while (p)
		ans += bit[p], p -= lowbit(p);
	return ans;
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i], add(i, a[i]);
	for (int i = 1; i <= m; i++)
	{
		int type, x, y;
		cin >> type >> x >> y;
		if (type == 1)
			add(x, y);
		else
			cout << sum(y) - sum(x - 1) << endl;
	}
	
	return 0;
}