写一下做题心得吧

注意数据范围，要用 long long

01背包和完全背包问题

之前一直都是二维数组来存储，所以不会存在这个考虑问题

  • 01背包是一个物品只可以拿一次
  • 完全背包一个背包可以拿无数次

通天之分组背包

自 $01$ 背包问世之后，小 A 对此深感兴趣。一天，小 A 去远游，却发现他的背包不同于 $01$ 背包，他的物品大致可分为 $k$ 组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。

输入格式

两个数 $m,n$，表示一共有 $n$ 件物品，总重量为 $m$。

接下来 $n$ 行，每行 $3$ 个数 $a_i,b_i,c_i$，表示物品的重量，利用价值，所属组数。

输出格式

一个数，最大的利用价值。

样例 #1

样例输入 #1

1
2
3
4
45 3
10 10 1
10 5 1
50 400 2

样例输出 #1

1
10

提示

$0 \leq m \leq 1000$，$1 \leq n \leq 1000$，$1\leq k\leq 100$，$a_i, b_i, c_i$ 在 int 范围内。

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
#include<bits/stdc++.h>
using namespace std;
#define N  1005

int a[N], b[N], c[N][N];
int group[N];// 记录每个组有多少个数
int t = 0; // 记录有多少个组
int n,m;
int ans[N];

int main() {
	cin >>  m >> n;
	int u;
	for (int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i] >> u;
		group[u]++;
		c[u][group[u]] = i;
		t = max(t, u);
	}
	for (int i = 1; i <= t; i++) {  // 组
		for (int j = m; j >= 0; j--) {  // 容量
			for (int k = 1; k <= group[i]; k++) {  // 针对组进行细化
				if (j >= a[c[i][k]]) {
					ans[j] = max(ans[j], ans[j - a[c[i][k]]] + b[c[i][k]]);
				}
			}
		}
	}
	cout << ans[m];
	return 0;
}


多重背包

image-20240319143805773

可以直接将 k 个相同的看成一个组

image-20240319143837464

image-20240319143850744

但是这样会超时

我们可以实现二进制拆分

image-20240319150844237

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
#include<bits/stdc++.h>
using namespace std;

const int N = 100010;

int n, p;
int dp[N]; 
int v[N], w[N], m[N];
int new_v[N], new_w[N], new_m[N];

int main() {
	cin >> n >> p;
	for (int i = 1; i <= n; i++) {
		cin >> v[i] >> w[i] >> m[i];
	}
	// 构造新的背包
	int new_n = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m[i]; j <<= 1) {
			new_v[++new_n] = v[i] * j;
			new_w[new_n] = w[i] * j;
			m[i] -= j;
		}
		if (m[i]) {
			new_v[++new_n] = v[i] * m[i];
			new_w[new_n] = w[i] * m[i];
		}
	}
	for (int i = 1; i <= new_n; i++) {
		for (int j = p; j >= new_w[i]; j--) {
			dp[j] = max(dp[j], dp[j - new_w[i]]+new_v[i]);
		}
	}
	cout << dp[p];
	return 0;
}

最长上升子序列

这是一个简单的动规板子题。

给出一个由 $n(n\le 5000)$ 个不超过 $10^6$ 的正整数组成的序列。请输出这个序列的最长上升子序列的长度。

最长上升子序列是指，从原序列中按顺序取出一些数字排在一起，这些数字是逐渐增大的。

输入格式

第一行，一个整数 $n$，表示序列长度。

第二行有 $n$ 个整数，表示这个序列。

输出格式

一个整数表示答案。

样例 #1

样例输入 #1

1
2
6
1 2 4 1 3 4

样例输出 #1

1
4

这是一个模版的题目

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

int dp[5005];
int f[5005];

int main() {
	int n;
	cin >> n;
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		cin >> dp[i];
		f[i] = 1;
		for (int j = 1; j < i; j++) {
			if (dp[j] < dp[i]) {
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
		ans = max(dp[i],ans);
	}
	cout << ans;
	return 0;
}

上升子序列拓展

image-20240320230052677

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
#include<bits/stdc++.h>
using namespace std;

const int N = 2005;

string sto[N];
int ans = 0;
int f[N];
int n;

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> sto[i];
		f[i] = 1;
		for (int j = 1; j < i; j++) {
			if (sto[i].find(sto[j]) == 0) {
				f[i] = max(f[i], f[j] + 1);
			}
		}
		ans = max(f[i], ans);
	}
	cout << ans;
	return 0;
}

滚动数组

image-20240314082931033

image-20240314083009071

注意输入方式

对于字符的输入考虑不周全的话会把换行符号输入导致麻烦

1
2
3
4
5
6
7
8
9
10
string s;
for (int i = 1; i <= n; i++) {
    cin >> s;
    for (int j = 1; j <= n; j++) {
        char a = s[j - 1];
        if (a == '0') { p[i][j] = 0; }
        else if (a == '1') p[i][j] = 1;
        else p[i][j] = 9;
    }
}

改用string更好

并查集

image-20240220151609877

image-20240220152720785

注意的是这个合并需要考虑谁大谁小

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
#include<bits/stdc++.h>
using namespace std;
const int N = 50;
int n, m;
int fa[N];

int find(int x) {
	if (fa[x] == x) return x;
	return fa[x] = find(fa[x]); // 顺带着压缩
}
void unionset(int x, int y) {  // x 的根指向 y 的根
	fa[find(x)] = find(y);
}

int main() {
	cin >> n >> m;
	int z, x, y;
	for (int i = 1; i <= n; i++)  fa[i] = i;
	while (m--)
	{
		cin >> z >> x >> y;
		if (z == 1) unionset(x, y);
		else {
			x = find(x), y = find(y);
			if (x == y) puts("Y");
			else puts("N");
		}
	}
	return 0;
}

这个代码中当z = 1 的时候插入，等于 2 的时候查找

线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#define lc p<<1    // 后续方便操作
#define rc p<<1 | 1
#define N 500005
int n, w[N];
struct node
{
	int l, r, sum;
}tr[N*4];

void build(int p, int l, int r) {
	tr[p] = { l,r,w[l] };
	if (l == r) return;
	int m = l + r >> 1;
	build(lc, l, m);
	build(rc, m + 1, r);
	tr[p].sum = tr[lc].sum + tr[rc].sum;
}

1
2
3
4
5
6
7
8
9
10
void update(int p, int x, int k) {
	if (tr[p].l == x && tr[p].r == x) {
		tr[p].sum += k;
		return;
	}
	int m = tr[p].l + tr[p].r >> 1;
	if (x <= m) update(lc, x, k);
	if (x > m) update(rc, x, k);
	tr[p].sum = tr[lc].sum + tr[rc].sum;
}

image-20240220161949607

1
2
3
4
5
6
7
8
int query(int p, int x, int y) {  // 区间查询
	if (x <= tr[p].l && tr[p].r <= y) return tr[p].sum;  // 能够覆盖就返回
	int m = tr[p].l + tr[p].r >> 1;   // 不能覆盖的话就裂开
	int sum = 0;
	if (x <= m) sum += query(lc, x, y);
	if (y > m) sum += query(rc, x, y);
	return sum;
}

image-20240220182824802

落谷 2097

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
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;

int n, m;
int p[100005];
int vis[100005];

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

void unionn(int x, int y) {
	int a = find(x), b = find(y);
	if (a == b) return;
	else p[b] = a;
}

int main() {
	cin >> n >> m;
	// 初始化
	for (int i = 1; i <= n; i++) {
		p[i] = i;
	} int a, b;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		unionn(min(a, b), max(a, b));
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		int a = find(i);
		if (vis[a] == 0) {
			ans++;
			vis[a] = 1;
		}
	}
	cout << ans;
}

并查集

image-20240411195259153

要学会按照倍数筛选 不要两个两个比较，复杂度太高了

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;

int a,b,p;
int sto[100005];
vector<int> prim; // 装在a到b之间的素数
int f[100005];

void ini(){ // 初始化 
	for(int i=1;i<=b;i++){
		f[i] = i;
	}
	for(int i=2;i<=b;i++){
		if(sto[i]==0){
			for(int j=2*i;j<=b;j+=i){
				sto[j] = 1;
			}
		}
	}
	// 存储大于p小于b的质数 
	for(int i=p;i<=b;i++){
		if(sto[i] == 0){
			prim.push_back(i);
		} 
	}
} 

int find(int x){
	if(f[x]==x) return x;
	else{
		f[x] = find(f[x]);
	}
	return f[x];
}

void nio(int y,int x){
	int fx = find(x),fy = find(y);
	if(fx==fy) return;
	f[fx] = fy;
	return;
}

int main(){
	cin >> a >> b >>p;
	ini();
	for(int i=0;i<prim.size();i++){
		int pp = prim[i];
		int cc = 0;
		while(cc*pp<a) cc++;
		while((cc+1)*pp<=b){
			nio(cc*pp,(cc+1)*pp);
			cc++;
		}
	}
	int ans = 0;
	for(int i=a;i<=b;i++){
		if(f[i] == i)  ans++;
	}
	cout << ans;
	return 0;
}