蓝桥杯（1）

蓝桥杯（1）

写在前面：去年裸考，想着今年好好准备一下，这几周天天被OS和OO折磨，一直拖到现在。看了一下往年题，填空题只要时间复杂度不是特别离谱，直接暴力模拟就行，编程题我主要总结一下常考的算法，由于现在还没上过算法课，好多东西也都不会，写这篇博客就当边学习边总结了。

最短路径 Floyd算法和Dijkstra算法

Dijkstra主要用于求两点最短距离和最短路径，而且只能求出一条最短路径。

  • 首先初始化，我们用edge [2022] [2022]二维数组存储边的权值，本题中无边则权值为一个较大数；定义dis[2022]存储第一个点到各个点的最短距离，初始化为edge[1]；haveFind [2022] 记录是否找到从1到i的最短路径；path[2022]记录从1到此点的前一点
  • 遍历dis从当前尚未找到最短路径的点中找到最小值，记此点为index，更新haveFind[index] = 1。
  • 以flag为中间点，遍历如果(dis[index] + edge [index] [i] <= dis[i])那么记dis[i] = dis[index] + edge [index] [i], 并且更新前继节点path[i] = index
  • 直到index为路径终点结束循环
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
71
72
73
#include<vector>
#include<algorithm>
using namespace std;
long long int edge[2022][2022] = {0};
int gcd(int a, int b) {
	if (a < b) {
		int c = a;
		a = b;
		b = c;
	}
	return (b == 0) ? a : gcd(b, a % b);
}
long long int dis[2022];       // 存储着1到各个点最小距离
int haveFind[2022];       //如果找到了1到某个点的最小距离则该点记为1
int path[2022];        //比如path[2] = 3,那么改最短路径的前继节点为3

void printPath(int flag) {    //打印路径
	if (flag == 1) {
		printf("1");
		return;
	}
	else {
		int lastFlag = path[flag];
		printPath(lastFlag);
		printf("-%d", flag);
		return;
	}
}

int main() {
	for (int i = 1; i <= 2021; i++) {        //初始化edge  
		for (int j = 1; j <= 2021; j++) {
			if (abs(i - j) > 21) {
				edge[i][j] = edge[j][i] = 1145140000;
			}
			else if (i == j) {
				edge[i][j] = 0;
			}
			else {
				edge[i][j] = edge[j][i] = i * j / gcd(i, j);
			}
		}
	}

	for (int i = 1; i <= 2021; i++) {          //初始化dis
		dis[i] = edge[1][i];
	}
	int nowNode = 1;
	while (nowNode != 2021) {
		int minDis = 1145140000;
		int index = -1;
		for (int i = 1; i <= 2021; i++) {
			if (haveFind[i] != 1 && dis[i] <= minDis) {
				minDis = dis[i];
				index = i;
			}
		}
		nowNode = index;
		haveFind[index] = 1;
		for (int i = 1; i <= 2021; i++) {
			if (haveFind[i] != 1) {
				if (dis[index] + edge[index][i] <= dis[i]) {
					dis[i] = dis[index] + edge[index][i];
					path[i] = index;
				}
			}
		}
	}

	printf("%lld\n", dis[2021]);
	printPath(2021);
	return 0;
}

Floyd算法更加暴力，可以求任意两点最短距离和路径

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
#include<vector>
#include<algorithm>
using namespace std;
long long int edge[2022][2022];
int path[2022][2022];
int gcd(int a, int b) {
	if (a < b) {
		int c = a;
		a = b;
		b = c;
	}
	return (b == 0) ? a : gcd(b, a % b);
}
int main() {
	for (int i = 1; i <= 2021; i++) {
		for (int j = 1; j <= 2021; j++) {
			if (abs(i - j) > 21) {
				edge[i][j] = edge[j][i] = 1145140000;
			}
			else if (i == j) {
				edge[i][j] = 0;
			}
			else {
				edge[i][j] = edge[j][i] = i * j / gcd(i, j);
			}
		}
	}

	for (int i = 1; i <= 2021; i++) {
		for (int j = 1; j <= 2021; j++) {
			for (int k = 1; k <= 2021; k++) {
				if (edge[j][i] + edge[i][k] <= edge[j][k]) {
					edge[j][k] = edge[j][i] + edge[i][k];
					path[j][k] = path[k][j] = i;
				}
			}
		}
	}
	printf("%lld", edge[1][2021]);
}

DFS深度搜索

例题一

其中N<=100000

题中认为子节点是无序的，因此才有得到的二叉树不同，例如2放到左边和右边

graph TB
subgraph 二叉树2 left
1a((1))
1a-->2a((2))
2a-->5a((5))
2a-->3a((3))
3a-->4a((4))
end
subgraph 多叉树2 left
1((1))
1-->2((2))
1-->3((3))
1-->4((4))
2-->5((5))
end
subgraph 二叉树2 right
1d((1))
1d-->3d((3))
3d-->4d((4))
4d-->2d((2))
2d-->5d((5))
end
subgraph 多叉树2 right
1b((1))
1b-->3b((3))
1b-->4b((4))
1b-->2b((2))
2b-->5b((5))
end

得到规律，在第二层中，如题中共有2,3,4三个子节点，只要让贡献高度最大的即2排在最右边，此时第二层子节点值为3（子节点个数）+1（第二层子节点各自下一层子节点的最大值）。我们用vector的二维数组，其中tree[i] 中存放着以i节点为父节点的节点标号

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<stdio.h>
#include<vector>
#define maxn 1e6+5
using namespace std;
vector<int> tree[(int)maxn];

int dfs(int node) {
	int max = 0;
	for (int i = 0; i < tree[node].size(); i++) {
		int value = dfs(tree[node][i]);
		max = (max < value) ? value : max;
	}
	return max + tree[node].size();
}
int main() {
	int n;
	scanf_s("%d", &n);
	int j;
	for (int i = 2; i <= n; i++) {
		scanf_s("%d", &j);
		tree[j].push_back(i);
	}
	printf("%d", dfs(1));

}

例题二 受伤的皇后

有一个 n×n 的国际象棋棋盘（n 行 n 列的方格图），请在棋盘中摆放 n 个受伤的国际象棋皇后，要求：

任何两个皇后不在同一行。
任何两个皇后不在同一列。
如果两个皇后在同一条 45 度角的斜线上，这两个皇后之间行号的差值至少为 3 。
请问一共有多少种摆放方案。

输入描述
输入的第一行包含一个整数 n。

其中，1≤n≤10。

输出描述
输出一个整数，表示答案。

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
#include<stdio.h>
int line[15]; //代表某一行在第几列
int row[15];  // row[i] 代表第i列是否被放置
int n, sum;
void dfs(int deep) {      //deep 代表当前在存第几行
	if (deep == n+1) {
		sum++;
	}
	else {
		for (int i = 1; i <= n; i++) {
			if (row[i] == 1) continue;      //第i列已经被放置了
			if ((deep >= 2 && line[deep - 1] == i + 1) || (deep >= 3 && line[deep - 2] == i + 2))continue;
            // 看一看副对角线（斜率为1的对角线）是否符合条件
			if ((deep >= 2 && i >= 2 && line[deep - 1] == i - 1) || (deep >= 3 && i >= 3 && line[deep - 2] == i - 2))continue;   // 看一看主对角线（斜率为-1的对角线）是否符合条件
			row[i] = 1;    //deep行存储到第i列
			line[deep] = i;
			dfs(deep + 1);
			row[i] = 0;     //还原
		}
	}
}

int main() {
	scanf_s("%d", &n);
	dfs(1);
	printf("%d", sum);
}
蓝桥杯
蓝桥杯（1）
https://etherialize.github.io/2023/04/02/蓝桥杯（1）-1/
作者
HZY
发布于
2023年4月2日
许可协议