蓝桥杯国赛算法复习

复习内容

1.spfa
2.背包问题
3.动态规划其他常考问题
4.dfs
5.bfs
6.并查集

一、基础题回顾

1.spfa

问题描述
蒜头君准备去参加骑车比赛，比赛在 n 个城市间进行，编号从 1 到 n。选手们都从城市 1 出发，终点在城市 n。
已知城市间有 m 条道路，每条道路连接两个城市，注意道路是双向的。现在蒜头君知道了他经过每条道路需要花费的时间，他想请你帮他计算一下，他这次比赛最少需要花多少时间完成。
输入格式
第一行输入两个整数\n,m（\1≤n≤1,000,1≤m≤5,000），分别代表城市个数和道路总数。接下来输入 m 行，每行输入三个数字 a,b,c（1≤a,b≤n,1≤c≤200），分别代表道路的起点和道路的终点，以及蒜头君骑车通过这条道路需要花费的时间。保证输入的图是连通的。
输出格式
输出一行，输出一个整数，输出蒜头君完成比赛需要的最少时间。
样例输入
5 6
1 2 2
2 3 3
2 5 5
3 4 2
3 5 1
4 5 1
样例输出
6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

题解

#include
#include
#include
using namespace std;
const int N = 1e4+9;
const int M = 1e5+9;
struct edge{
	int u;
	int w;
	int next;
	edge(){
	}
	edge(int uu,int ww,int nn){
		u = uu;
		w = ww;
		next = nn;
	}
}e[N << 1];
int head[N],size;
void init(){
	memset(head,-1,sizeof(head));
	size = 0;
}
void add(int u,int v,int w){
	e[size] = edge(u,w,head[v]);
	head[v] = size++;
}
void add2(int u,int v,int w){
	add(u,v,w);
	add(v,u,w);
}
int n,m;
int dis[N];
bool vis[N];
void spfa(int u){
	memset(dis,0x3f,sizeof(dis));
	dis[u] = 0;
	memset(vis,false,sizeof(vis));
	vis[u] = true;
	queue<int> q;
	q.push(u);
	while(!q.empty()){
		u = q.front();
		q.pop();
		vis[u] = false;
		for(int j = head[u];~j;j = e[j].next){
			int v = e[j].u;
			int w = e[j].w;
			if(dis[v] > dis[u] + w){
				dis[v] = dis[u] + w;
				if(!vis[v]){
					q.push(v);
					vis[v] = true;
				}
			}
		}
	}
}
int main(){
	init();
	int u,v,w;
	cin >>n>>m;
	while(m--){
		cin >>u>>v>>w;
		add2(u,v,w);
	}
	spfa(1);
	cout <<dis[n]<<endl;
	return 0;
}
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
62
63
64
65
66
67
68
69
70

2.背包问题
01背包

问题描述：
有N件物品和一个容积为M的背包。第i件物品的体积为volume[i]，价值为worth[i]。求解将哪些物品装入背包可使价值总和最大。每种物品只有一件，可以选择放或者不放。（N<=3500,M<=13000）

输入格式：
第一行为物品数量N和背包容积M

每行依次输入第i件物品的价值和体积

样例输入：
3 10

3 4

2 6

6 7

样例输出：
6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#include
#include
using namespace std;
int dp[100][100];
int v[100],w[100];
int n,m;
int main(){
	cin >>n>>m;
	int maxs = -1;
	for(int i = 0;i<n;i++){
		cin >>v[i]>>w[i];
	}
	for(int i = 0;i<n;i++){
		for(int j = 0;j<m;j++){
			if(j < w[i]){
				dp[i][j] = dp[i-1][j];
			}else{
				dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
			}
			maxs = max(maxs,dp[i][j]);
		}
	}
	cout <<maxs<<endl;
	return 0;
}
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

多重背包

题目描述：
有N种物品，第i种物品的体积是c[i]，价值是w[i]，每种物品的数量都是有限的，为n[i]。现有容量为V的背包，请你放入若干物品，在总体积不超过V的条件下，使总价值尽可能大。
1
2

#include
#include
using namespace std;
int dp[21][1010];
int w[21],c[21],n[21];
int main()
{
	int N,V;
	cin>>N>>V;
	for(int i=1;i<=N;++i)
		cin>>w[i]>>c[i]>>n[i];
	for(int i=1;i<=N;++i)
	{
		for(int j=0;j<=V;++j)
		{
			for(int k=0;k<=n[i];++k)
			{
				if(j>=c[i]*k)
					dp[i][j]=max(dp[i-1][j-c[i]*k]+w[i]*k,dp[i][j]);
			}
		}
	}
	cout<<dp[N][V]<<endl;
	return 0;
}
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

完全背包

问题描述：
当前有N种物品，第i种物品的体积是c[i]，价值是w[i]。
每种物品的数量都是无限的，可以任意选择若干件。
现有容量为V的背包，请你放入若干物品，在总体积不超过V的条件下，使总价值尽可能大。
与01背包问题的区别就是物品有无限多个.
1
2
3
4
5

#include
#include
using namespace std;
int dp[21][1010];
int w[21],c[21];
int main()
{
	int N,V;
	cin>>N>>V;
	for(int i=1;i<=N;++i)
		cin>>w[i]>>c[i];
	for(int i=1;i<=N;++i)
	{
		for(int j=0;j<=V;++j)
		{
			if(j>=c[i])
				dp[i][j]=max(dp[i][j-c[i]]+w[i],dp[i-1][j]);
			else 
				dp[i][j]=dp[i-1][j];
		}
	}
	cout<<dp[N][V]<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

3.动态规划其他常考问题

楼梯问题
略

贪心
略

最大字段和

给定N个数A1, A2, ... An，从中选出k（k不固定）个连续的数字 Ai, Ai+1, ... Ai+k-1，使得∑i+k−1iAt 达到最大，求该最大值。
1

#include
#include
using namespace std;
int dp[100];
int a[100];
int n;
int main(){
	cin >>n;
	int maxs = -1;
	for(int i = 1;i<=n;i++){
		cin >>a[i];
		dp[i] = a[i];
	}
	for(int i = 2;i<=n;i++){
		dp[i] = max(dp[i],dp[i-1]+a[i]);
		maxs = max(maxs,dp[i]);
	}
	cout <<maxs<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

最长上升子序列

#include
#include
using namespace std;
int dp[100];
int a[100];
int n;
int main(){
	cin >>n;
	int maxs = -1;
	for(int i = 1;i<=n;i++){
		cin >>a[i];
	}
	for(int i = 1;i<=n;i++){
		dp[i] = 1;
		for(int j = 1;j<=i;j++){
			if(a[j] < a[i]){
				dp[i] = max(dp[i],dp[j]+1);
			}
		}
		maxs = max(maxs,dp[i]);
	}
	cout <<maxs<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

数塔问题
在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的：

有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？

Output
对于每个测试实例，输出可能得到的最大和，每个实例的输出占一行。

Sample Input
1 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5

Sample Output
30

#include
#include
using namespace std;
int dp[100][100];
int a[100][100];
int n,m;
int main(){
	cin >>n>>m;
	for(int i = 0;i<n;i++){
		for(int j = 0;j<m;j++){
			cin >>a[i][j];
		}
	}
	for(int i = 0;i<n;i++){
		dp[n][i] = a[n][i];
	}
	for(int i = n-1;i>1;i--){
		for(int j = 0;j<=i;j++){
			dp[i][j] = max(dp[i+1][j],dp[i+1][j+1])+a[i];
		}
	} 
	cout <<dp[0][0]<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

4 dfs

问题描述
　　n个人参加某项特殊考试。
　　为了公平，要求任何两个认识的人不能分在同一个考场。
　　求是少需要分几个考场才能满足条件。
输入格式
　　第一行，一个整数n(1<n<100)，表示参加考试的人数。
　　第二行，一个整数m，表示接下来有m行数据
　　以下m行每行的格式为：两个整数a，b，用空格分开 (1<=a,b<=n) 表示第a个人与第b个人认识。
输出格式
　　一行一个整数，表示最少分几个考场。
样例输入
5
8
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5
样例输出
4
样例输入
5
10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
样例输出
5
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

#include
using namespace std;
const int MAXN = 1e2+2;
int g[MAXN][MAXN];//用邻接矩阵存储关系
int room[MAXN][MAXN]; //room[i][j]表示当前i号教室第j个人为room[i][j]
int MIN ;//优化一：当前状态下的最小教室
int n,m;//点数，边数

void dfs(int v,int c){
    if(c>=MIN)return;//剪枝
    if(v>n){
        MIN=MIN>c?c:MIN;
        return;
    }
    for(int i=1;i<=c;++i){
        //循环判断每个教室的每个人是否与v有关系
        int k =0;
        while(room[i][k]&&g[v][room[i][k]]==0){
            //如果当前教室i,第k个人的编号room[i][k]与v有关系退出
            k++;
        }
        if(room[i][k]==0){
            //有当前教室i的所有人无关系，可加入教室
            room[i][k]=v;
            dfs(v+1,c);//把v+1加入到教室
            room[i][k]=0;//回溯
        }
    }
    room[c+1][0]=v;//或者新开一间教室放该v,(注不是所有教室不满足条件)
    dfs(v+1,c+1);
    room[c+1][0]=0;

}

int main(){
    //相当于图的着色问题，用dfs 
    scanf("%d%d",&n,&m);
    MIN = n;//易知最多教室为n
    int a,b;
    for(int i=0;i<m;++i){
        scanf("%d%d",&a,&b);
        g[a][b]=g[b][a]=1;
    }
    dfs(1,0);
    printf("%d",MIN);
    return 0;
}

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

A - 滑雪 POJ - 1088
Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
1 2 3 4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-…-3-2-1更长。事实上，这是最长的一条。

Input
输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。

Output
输出最长区域的长度。

Sample Input
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

Sample Output
25
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
#include
using namespace std;
int n,m;
int mp[100][100];
int ansm = -1;
int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
int dfs(int x,int y){
	int ans = -1;
	if(ans > 0){
		return ans;
	}
	ans = 1;
	for(int i = 0;i<4;i++){
		int tx = x + dir[i][0];
		int ty = y + dir[i][1];
		if(tx >= 0 && tx < n && ty >= 0 && ty < m && mp[tx][ty] < mp[x][y]){
			int temp = dfs(tx,ty) + 1;
			ans = max(ans,temp);
		} 
	}
	return ans; 
}
int main(){
	cin >>n>>m;
	for(int i = 0;i<n;i++){
		for(int j = 0;j<m;j++){
			cin >>mp[i][j];
		}
	}
	
	for(int i = 0;i<n;i++){
		for(int j = 0;j<m;j++){
			int t = dfs(i,j);
			ansm = max(ansm,t);
		}
	}
	cout <<ansm<<endl;
} 
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

5.bfs

迷宫最短路

#include
#include
using namespace std;
struct node{
	int x,y,s;
	node(){
	}
	node(int xx,int yy,int ss){
		x = xx;
		y = yy;
		s = ss;
	}
};
int n,m;
char mp[100][100];
bool vis[100][100];
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int bfs(int x,int y){
	queue<node> q;
	q.push(node(x,y,0));
	vis[x][y] = true;
	while(!q.empty()){
		node now = q.front();
		q.pop();
		for(int i = 0;i<4;i++){
			int tx = x + dir[i][0];
			int ty = y + dir[i][1];
			if(tx >= 0 && tx < n && ty >= 0 && ty < m && !vis[tx][ty] && mp[tx][ty] != '#'){
				if(mp[tx][ty] == 'T'){
					return now.s + 1;
				}else{
					vis[tx][ty] = true;
					q.push(node(tx,ty,now.s+1));
				}
			}
		}
	}
}
int main(){
	cin >>n>>m;
	for(int i = 0;i<n;i++){
		cin >>mp[i];
	}
	int sx,sy;
	for(int i = 0;i<n;i++){
		for(int j = 0;j<m;j++){
			if(mp[i][j] == 'S'){
				 sx = i;
				 sy = j;
			}
		}
	}
	cout <<bfs(sx,sy)<<endl;
	return 0;
}
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

拓展
dfs与bfs的抽象问题

例1：给定n nn个整数，要求选出K KK个数，使得选出来的K KK个数的和为s u m sumsum
1

#include 
using namespace std;
int a[40];
int n, k, sum, ans;
//i表示选择第i个数，cnt记录选择的个数，s表示选取数的和
void dfs(int i, int cnt, int s) {
	if (i == n) {
		if (cnt == k && s == sum) {
			ans++;
		}
		return;
	}
	dfs(i + 1, cnt, s); //不选该数
	dfs(i + 1, cnt + 1, s + a[i]); //选择该数
}
int main() {
	cin >> n >> k >> sum;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	ans = 0;
	dfs(0, 0, 0);
	cout << ans << endl;
	return 0;
}

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

例2：取木棍：
有4个木棍输入每个木棍长度；
判断是否可以拼成三角形：
比如 1 2 3 3可以拼成三角形：
输出yes；
1
2
3
4
5

#include 
using namespace std;
int n,m,sum;
int a[10010];
bool vis[10010];
bool f;
void dfs(int p,int s,int st)
{
	if(f)
	{
		return ;
	}
	if(p==3)
	{
		f=true;
		return ;
	}
	if(s=sum/3)//当前的边正好可以构成三角形的一个边 
	{
		dfs(p+1,0,0);
		return ;	
	}
	for(int i=0;i<n;++i)
	{
		if(!vis[i])
		{
			vis[i]=true;
			dfs(p,s+a[i],i+1);
			vis[i]=false;
		}
	}
}
int main()
{
	cin>>n;
	for(int i=0;i<n;++i)
	{
		cin>>a[i];
		sum+=a[i];
	}
	if(sum%3!=0)//如果不是3的倍数的话就已经明摆着不可以成功 
	{
		cout<<"no"<<endl;
		return 0;
	}
	else dfs(0,0,0);
	if(f) cout<<"yes"<<endl;
	else cout<<"no"<<endl;
	return 0; 
	 
 } 

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