Czj's Blog

第二讲-搜索与优化

发表于 更新于 分类于 ，
本文字数： 8.8k 阅读时长 ≈ 8 分钟

作业链接

[蓝桥杯] 第二讲：搜索与优化 - 题单 - 洛谷 | 计算机科学教育新生态

AC 代码

B3642 二叉树的遍历 - 洛谷

某序遍历，指中/根所在的位置：

  • 前序遍历：中左右
  • 中序遍历：左中右
  • 后序遍历：左右中
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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 9;
int n;
typedef struct Node {
	int l, r;
} node;
node tr[N];

void dfs(int k, int u) {
	if (u == 0)return ;
	node t = tr[u];
	if (k == 1) {
		cout << u << " ";
		dfs(k, t.l);
		dfs(k, t.r);

	}
	if (k == 2) {
		dfs(k, t.l);
		cout << u << " ";
		dfs(k, t.r);
	}
	if (k == 3) {
		dfs(k, t.l);
		dfs(k, t.r);
		cout << u << " ";

	}

}


int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> tr[i].l >> tr[i].r;
	}
	dfs(1, 1);
	puts("");

	dfs(2, 1);
	puts("");

	dfs(3, 1);
	puts("");
	return 0;
}

P1219 [USACO1.5] 八皇后 Checker Challenge - 洛谷

主对角线（左下右上）上的点满足：横纵坐标 x-y 为定值 副对角线（左上右下）上的点满足：横纵坐标 x+y 为定值

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 <bits/stdc++.h>
using namespace std;
int n, ans;
const int N = 20;
bool g[N][N], col[N], deg[N], udeg[N];

void  dfs(int u) {
	if (u == n) {
		if (ans < 3) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j <= n; j++) {
					if (g[i][j]) cout << j + 1 << " ";
				}
			}
			cout << endl;
		}
		ans++;

		return ;
	}

	for (int i = 0; i < n; i++) {
		if (!col[i] && !deg[i + u] && !udeg[i - u + n]) {
			col[i] = deg[i + u] = udeg[i - u + n] = 1;
			g[u][i] = 1;
			dfs(u + 1);
			g[u][i] = 0;
			col[i] = deg[i + u] = udeg[i - u + n] = 0;
		}
	}
}

int main() {
	cin >> n;
	dfs(0);

	cout << ans;

	return 0;
}

P8604 [蓝桥杯 2013 国 C] 危险系数 - 洛谷

背景知识

在一个无向图中，如果删除某个顶点以及与该顶点相关联的所有边后，图的连通分量数增加，那么这个顶点就被称为割点。

题意理解

在本题中，要求的关键点定义为：对于给定的两个顶点 \(x\) 和 \(y\)，如果删除某个顶点 \(z\) 后，\(x\) 和 \(y\) 不再连通，那么 \(z\) 就是关于 \(x\) 和 \(y\) 的关键点。此处 \(x\) 和 \(y\) 不再连通等价于图的连通分量数增加，因此 \(z\) 满足割点的定义。本题退化为求 \(x\) 和 \(y\) 的点之间的割点数量。

具体求法

如果一个点是两点间的割点，则两点之间的联通路径数应该均经过这个点，否则删去这个点后两个点依旧联通，与定义矛盾。因此我们只需要记录每一条通路使用了哪些点，则使用次数等于通路数的点就是点间割点。（图上割点需要用 tarjan 算法求解）

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;
int n, m, a, b, u, v, ans, sum;
const int N = 1e3 + 9;
vector<int> g[N];
bool vis[N];
int cnt[N];
void dfs(int u) {
	if (u == v) {
		sum++;// 可联通的路径
		for (int i = 1; i <= n; i++) {
			if (vis[i])cnt[i]++;
		}
		return;
	}
	for (auto t : g[u]) {
		if (!vis[t]) {
			vis[t] = 1;
			dfs(t);
			vis[t] = 0;
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	cin >> u >> v;
	vis[u] = 1;
	dfs(u);
	if (sum) {
		for (int i = 1; i <= n; i++) {
			if (sum == cnt[i])ans++;
		}
		cout << ans - 2;
	} else cout << -1;

	return 0;
}

P1443 马的遍历 - 洛谷

等权图最短路可以用 BFS 的洪泛策略求解

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
#include <bits/stdc++.h>
using namespace std;
const int N = 403;
int n, m, x, y, g[N][N];
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2}, dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
typedef pair<int, int> PII;

bool check(int x, int y) {
	return x >= 1 && x <= n && y >= 1 && y <= m && g[x][y] == -1;
}

void bfs(int x, int y) {
	//下标从(1,1)开始
	queue<PII> q;
	q.push({x, y});
	g[x][y] = 0;
	while (q.size()) {
		auto t = q.front();
		q.pop();
		for (int i = 0; i < 8; i++) {
			int tx = t.first + dx[i], ty = t.second + dy[i];
			if (check(tx, ty)) {
				g[tx][ty] = g[t.first][t.second] + 1;
				q.push({tx, ty});
			}
		}
	}
}

int main() {
	cin >> n >> m >> x >> y;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			g[i][j] = -1;
		}
	}
	bfs(x, y);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cout << g[i][j] << " ";
		}
		cout << "\n";
	}
	return 0;
}

P8662 [蓝桥杯 2018 省 AB] 全球变暖 - 洛谷

题意理解

淹没的定义：陆地只要沿海就会被淹没。岛屿被完全淹没的定义：岛屿的所有陆地都被淹没。结合两个定义可以得到：岛屿的所有陆地都沿海则会被完全淹没。

具体做法

求一块岛屿等价于用 bfs 找连通块，同时记录边界的陆地数 cnt 和连通块总数 sum，如果 cnt == sum，说明连通块的所有陆地都沿海，即这个岛屿会被完全淹没

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 9;
char g[N][N];
int n, ans;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
typedef pair<int, int> PII;
bool vis[N][N];

// 越界检查
bool check(int x, int y) {
	return x >= 1 && x <= n && y >= 1 && y <= n;
}

void bfs(int x, int y) {
	queue<PII> q;
	vis[x][y] = 1;
	q.push({x, y});
	int cnt = 0, sum = 0;
	while (q.size()) {
		auto t = q.front();
		q.pop();
		sum++;
		bool flg = 0;
		for (int i = 0; i < 4; i++) {
			auto tx = t.first + dx[i], ty = t.second + dy[i];
			if (check(tx, ty) && !vis[tx][ty]) {
				if (g[tx][ty] == '.')flg = 1;
				else {
					vis[tx][ty] = 1;
					q.push({tx, ty});
				}
			}
		}
		if (flg) cnt++;
	}
	if (cnt == sum)ans++;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> g[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (g[i][j] == '#' && !vis[i][j]) {
				// 检查这个大陆是否会被淹没
				bfs(i, j);
			}
		}
	}
	cout << ans;
	return 0;
}

P8658 [蓝桥杯 2017 国 A] 填字母游戏 - 洛谷

记忆化已经得到结果的局面，避免重复计算

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
74
75
76
77
78
79
80
81
82
83
84
#include<bits/stdc++.h>
using namespace std;
int n, len;
string s;
// mp 值的意义：0 未计算，1 小明败，2 平局，3 小明胜
unordered_map<string, int> mp;

void dfs(int k) { // k = 0 表示小明在下棋，k = 1 表示 K 大师在下棋
	if (mp[s])return;

	// 检查是否还需要填字

	if ((int)s.find("LOL") != -1) {
		// 当前的局面已经出现了 LOL，上一手已经结束了
		mp[s] = (k == 0 ? 1 : 3); // 如果当前是小明，则说明 K 大师之前已经赢了，因此结果是小明败
		return;
	}

	if ((int)s.find("*") == -1) {
		// 不存在可以填的位置了，平局结束了
		mp[s] = 2;
		return;
	}

	int tmp = (k == 1 ? 3 : 1); // 谁在下认为谁输了

	for (int i = 0; i < len; i++) {
		if (s[i] == '*') {
			// 可以填

			s[i] = 'L';

			dfs(1 - k); // 交替手：0 变 1，1 变 0

			if (k == 0) {
				// 小明在下
				tmp = max(mp[s], tmp); // 选最好的情况
			} else { // 反之，K 大师在下的话，选最坏情况
				tmp = min(mp[s], tmp);
			}

			/*
			最优解剪枝
			如果现在是小明在下 k = 0 且胜利了 tmp = 3，则不用继续下了
			如果现在是 K 大师在下 k = 1 且失败了 tmp = 1，判为小明胜利，也不用再下了
			*/
			if ((k == 0 && tmp == 3) || (k == 1 && tmp == 1)) {
				s[i] = '*';// 恢复状态
				mp[s] = tmp;
				return;
			}

			s[i] = 'O';

			dfs(1 - k);

			if (k == 0) {
				tmp = max(mp[s], tmp);
			} else {
				tmp = min(mp[s], tmp);
			}

			if ((k == 0 && tmp == 3) || (k == 1 && tmp == 1)) {
				s[i] = '*';// 恢复状态
				mp[s] = tmp;
				return;
			}
			s[i] = '*'; // 状态复原
		}
	}
	mp[s] = tmp;
}

int main() {
	scanf("%d", &n);
	while (n--) {
		cin >> s;
		mp.clear();
		len = s.size();
		dfs(0);
		printf("%d\n", mp[s] - 2);
	}
	return 0;
}

P10386 [蓝桥杯 2024 省 A] 五子棋对弈 - 洛谷

先按任意顺序模拟下棋过程，得到满盘局面后再判断是否合法

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
using namespace std;
const int N = 6;

/*
  直接先 dfs 得到所有下满棋盘的棋局（包括不合法的），因为题目说明不同落子得到的同一局面视为一种情况
  棋局的合法性判断：由于要求两人是交替放棋子的，且白子先走
  因此记白子个数为 x，黑子为 y，则 x-y == 1 为合法
  可以证明，当下满棋盘且两种颜色棋子满足这个数量关系时，必然有对应的合法落子顺序
  下面则检测是否有人胜利即可
 */
int ans = 0, g[N][N];

bool check() {
	bool tmp;
	// 判断是否轮流落子
	int cnt1 = 0, cnt2 = 0;
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			if (g[i][j] == 1)cnt1++;
			if (g[i][j] == 2) cnt2++;
		}
	}
//	if (cnt1 + cnt2 != 25)cout << cnt1 << " " << cnt2 << endl;
	// 棋局不满足白棋先手且轮流落子，不合法
	if (cnt1 - cnt2 != 1)return 0;
	// 横向判断
	for (int i = 0; i < 5; i++) {
		tmp = 1;
		for (int j = 0; j < 5; j++) {
			if (g[i][j] != g[i][0])tmp = 0;
		}
		if (tmp)return 0;
	}
	// 竖向判断
	for (int i = 0; i < 5; i++) {
		tmp = 1;
		for (int j = 0; j < 5; j++) {
			if (g[j][i] != g[0][i])tmp = 0;
		}
		if (tmp)return 0;
	}
	// 斜线判断
	tmp = 1;
	for (int i = 0; i < 5; i++) {
		if (g[i][i] != g[0][0])tmp = 0;
	}
	if (tmp)return 0;// 有人赢了，不是平局
	tmp = 1;
	for (int i = 4, j = 0; i >= 0 && j < 5; i--, j++) {
		if (g[i][j] != g[4][0]) tmp = 0;
	}
	if (tmp)return 0;

	return 1;

}

void dfs(int x, int y) {

	// 先按行下，下满了换下一行，行下满了检查

	if (y == 5) {
		dfs(x + 1, 0);// 下一行
		return;
	}

	if (x == 5) {// 下满了
		if (check()) {
			ans++;
		}
		return;
	}

	g[x][y] = 1;
	dfs(x, y + 1);
	g[x][y] = 0;

	g[x][y] = 2;
	dfs(x, y + 1);
	g[x][y] = 0;
}
int main() {
	dfs(0, 0);
	cout << ans;
	return 0;
}

P9234 [蓝桥杯 2023 省 A] 买瓜 - 洛谷

排序优化、最优性剪枝、合法性剪枝、除法改乘法

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
#include <iostream>
#include<algorithm>
#define int long long
using namespace std;
int ans = 50; //ans维护最小劈瓜数  先设为一个大值
int a[50];//存瓜 原数组
int sum[50];//表示的是从第 i 个瓜到第 n 个瓜的总质量
int n, m;
int min(int a, int b) {
	return a > b ? b : a;
}

void dfs(int S, int i, int cnt) { //总和，下标，劈瓜计数器
	if (cnt >= ans)return; //剪枝
	if (S == m) ans = min(ans, cnt); //如果相等，说明劈瓜劈够了，返回已经劈了几次瓜
	if (i >= n || S >= m || S + sum[i] < m) return ; //递归结束条件
	dfs(S + a[i], i + 1, cnt); //买一个瓜
	dfs(S + a[i] / 2, i + 1, cnt + 1); //买半个瓜，计数器+1
	dfs(S, i + 1, cnt); //不买当前瓜，跳到下一个瓜
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	m <<= 1; //总质量也要*2才能保证结果不受影响
	for (int i = 0; i < n; i++) cin >> a[i], a[i] <<= 1; //为了防止劈瓜出现小数，将其左移一位*2倍
	sort(a, a + n, greater<>()); //让质量大的在前面，争取最小劈瓜次数可以满足条件


	//遍历所有的瓜
	for (int i = n - 1; i >= 0; i--) {
		sum[i] = sum[i + 1] + a[i]; //当前瓜及其之后所有瓜的总质量=从1到下一个瓜的总质量+当前瓜的质量
	}
	dfs(0, 0, 0);
	if (ans == 50)cout << -1; //最终 ans 仍然为初始值 50，则表示无法通过劈瓜的方式满足要求
	else cout << ans;

	return 0;
}