避风港
0%

2023蓝桥杯广东省赛个人题解

发表于 分类于

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

int a[101] = { 5,6,8,6,9,1,6,1,2,4,9,1,9,8,2,3,6,4,7,7,5,9,5,0,3,8,7,5,8,1,5,8,6,1,8,3,0,3,7,9,2,7,0,5,8,8,5,7,0,9,9,1,9,4,4,6,8,6,3,3,8,5,1,6,3,4,6,7,0,7,8,2,7,6,8,9,5,6,5,6,1,4,0,1,0,0,9,4,8,0,9,1,2,8,5,0,2,5,3,3 };
long long ans = 0;
int b[20];
int c[20] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
void dfs(int x, int pos) {
	if (pos == 1 && a[x] != 2) return;
	if (pos == 2 && a[x] != 0) return;
	if (pos == 3 && a[x] != 2) return;
	if (pos == 4 && a[x] != 3) return;
	b[pos] = a[x];
	if (pos != 8) {
		for (int i = x + 1; i < 100; i++) {
			dfs(i, pos + 1);
		}
	}
	else {

		int m = b[5] * 10 + b[6];
		int d = b[7] * 10 + b[8];

		if (m < 1 || m > 12) return;
		if (d < 1 || d > c[m]) return;

		cout << b[1] << b[2] << b[3] << b[4] << "-" << b[5] << b[6] << "-" << b[7] << b[8] << endl;


		ans++;

	}
}
int main() {

	for (int i = 0; i < 100; i++) {
		dfs(i, 1);
	}

	cout << ans << endl;

	return 0;
}

试题 B: 01 串的熵

暴力，记得处理四舍五入，11027421

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

int a = 23333333;

int main() {


	int mid = a / 2;

	for (int i = mid; i >= 0; i--) {
		double x = -1.0 * i / a * log2(1.0 * i / a);
		double y = -1.0 * (a - i) / a * log2(1.0 * (a - i) / a);
		long long ans = (x * i + y * (a - i)) * 100000;

		if (ans % 10 >= 5) ans = ans / 10 + 1;
		else ans = ans / 10;

		if (ans == 116259075798) cout << i << endl;
	}


	return 0;
}

试题 C: 冶炼金属

思维，注意处理边界情况

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

int n;

int main() {
	ios::sync_with_stdio(0);

	cin >> n;

	int maxx = -1;
	int minn = 1e9 + 7;

	int a, b;
	cin >> a >> b;


	if (a == b) {
		maxx = 1;
		minn = 1;
	}
	else {
		minn = a / (b + 1) + 1;
		maxx = a / b;
	}

	for (int i = 2; i <= n; i++) {
		cin >> a >> b;
		if (a == b) {
			maxx = 1;
			minn = 1;
		}
		else {
			minn = max(minn, a / (b + 1) + 1);
			maxx = min(maxx, a / b);
		}
	}

	cout << minn << " " << maxx << endl;

	return 0;
}

试题 D: 飞机降落

全排列处理，复杂度为10! * 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
using namespace std;

int n;

int a[12];
int t[12], d[12], l[12];
int main() {
	ios::sync_with_stdio(0);

	int T;
	cin >> T;
	while (T--) {
		cin >> n;
		for (int i = 1; i <= n; i++) a[i] = i;

		for (int i = 1; i <= n; i++) {
			cin >> t[i] >> d[i] >> l[i];
		}

		int flag = 0;

		do {

			int now = 0;

			for (int i = 1; i <= n; i++) {
				if (d[a[i]] + t[a[i]] < now) break;

				if (t[a[i]] > now) {
					now = t[a[i]] + l[a[i]];
				}
				else {
					now = now + l[a[i]];
				}

				if (i == n) flag = 1;
			}
			if (flag) break;

		} while (next_permutation(a + 1, a + 1 + n));


		if (flag) cout << "YES";
		else cout << "NO";

		if (T != 0) cout << endl;
	}

	return 0;
}

试题 E: 接龙数列

简单动态规划

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

int n;

int a[100010];
int dp[100010];
int h[100010];
int last[11];
int maxi[11];


int main() {
	ios::sync_with_stdio(0);

	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		int k = a[i];
		while (k) {
			if (k < 10) h[i] = k;
			k /= 10;
		}

	}

	for (int i = 0; i <= 9; i++) {
		last[i] = 0;
		maxi[i] = 0;
	}

	for (int i = 1; i <= n; i++) {
		dp[i] = maxi[h[i]] + 1;
		maxi[a[i] % 10] = max(maxi[a[i] % 10], dp[i]);
		last[a[i] % 10] = i;
	}

	int ans = n;
	for (int i = 0; i <= 9; i++) {
		ans = min(ans, n - maxi[i]);
	}

	cout << ans;

	return 0;
}

试题 F: 岛屿个数

首先bfs每个点，判断是否能通过0到达岛外，可以斜着走，无法到达就说明是子岛屿，记得剪枝。第二次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
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include<bits/stdc++.h>
using namespace std;

int n, m;
int a[60][60];
int flag;
int xi[8] = { 1, 0, -1, 0, 1, -1, 1, -1};
int yi[8] = { 0, 1, 0, -1, -1, 1, 1, -1};
int ans;
int ch[60][60];

int check(int x, int y) {
	if (x < 1 || x > n || y < 1 || y > m) return 0;
	return 1;
}

void init_bfs(int x, int y) {

	queue<pair<int, int>>q;
	q.push(make_pair(x, y));
	int c[60][60];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			c[i][j] = 0;
		}
	}
	c[x][y] = 1;

	while (!q.empty()) {
		auto p = q.front();
		q.pop();
		for (int i = 0; i < 8; i++) {
			int xn = p.first + xi[i];
			int yn = p.second + yi[i];
			if (check(xn, yn)) {
				if (c[xn][yn])continue;
				c[xn][yn] = 1;

				if (a[xn][yn] == 2) {

					flag = 2;
					break;
				}
				else if (a[xn][yn] == 1) {
					continue;
				}
				q.push(make_pair(xn, yn));
			}
			else {

				flag = 1;
				break;
			}
		}
		if (flag != 0) break;
	}

}

void bfs(int x, int y) {

	queue<pair<int, int>>q;
	q.push(make_pair(x, y));
	ch[x][y] = 1;

	while (!q.empty()) {
		auto p = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int xn = p.first + xi[i];
			int yn = p.second + yi[i];
			if (check(xn, yn)) {
				if (ch[xn][yn])continue;
				ch[xn][yn] = 1;

				if (a[xn][yn] == 0) {
					continue;
				}

				q.push(make_pair(xn, yn));
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);

	int T;
	cin >> T;
	while (T--) {
		cin >> n >> m;
		string s;
		for (int i = 1; i <= n; i++) {
			cin >> s;
			for (int j = 0; j < m; j++) {
				a[i][j + 1] = s[j] - '0';
				ch[i][j + 1] = 0;
			}
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (a[i][j] == 0) continue;
				flag = 0;
				init_bfs(i, j);

				if (flag != 1) a[i][j] = 2;
			}
		}

		ans = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (ch[i][j] == 1 || a[i][j] != 1) continue;
				ans++;
				bfs(i, j);

			}
		}

		cout << ans;
		if (T != 0) cout << endl;
		

	}


	return 0;
}

试题 G: 子串简写

前缀和，但这个位置的题目真的这么简单么，怀疑可能读错题。

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

int k;
string s;
char a, b;

int pre[1000010];

int main() {
	ios::sync_with_stdio(0);

	cin >> k;
	cin >> s >> a >> b;
	
	int n = s.length();
	long long ans = 0;

	for (int i = 0; i < n; i++) {
		if (i != 0) pre[i] = pre[i - 1];
		else pre[i] = 0;
		if (s[i] == a) pre[i]++;
		if (s[i] == b && i - k + 1 >= 0) ans += pre[i - k + 1];
	}
	
	cout << ans;

	return 0;
}

试题 H: 整数删除

维护链表和一个set，每次取出set中最小的，判断是否合法，并对链表节点和值进行修改。

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

int c[1000010];

int n, k;
long long a[500010];

int l[500010], r[500010];

set<pair<int, int>> s;

int main() {
	ios::sync_with_stdio(0);

	cin >> n >> k;

	int w = n - k;

	l[0] = r[0] = l[n + 1] = r[n + 1] = 0;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		l[i] = i - 1;
		r[i] = i + 1;
		s.insert(make_pair(a[i], i));
	}

	while (1) {
		if (k == 0) break;

		auto it = s.begin();
		auto p = *it;

		int val = p.first, pos = p.second;
		if (c[pos] || a[pos] != val) {
			s.erase(it);
			continue;
		}

		k--;
		c[pos] = 1;
		int pl = l[pos], pr = r[pos];
		if (pl > 0 && pl <= n) {
			a[pl] += a[pos];
			r[pl] = pr;
			s.insert(make_pair(a[pl], pl));
		}
		if (pr > 0 && pr <= n) {
			a[pr] += a[pos];
			l[pr] = pl;
			s.insert(make_pair(a[pr], pr));
		}
	}

	for (int i = 1; i <= n; i++) {
		if (c[i]) continue;
		cout << a[i];
		if (w != 0) cout << " ";
		w--;
	}
	

	return 0;
}

试题 I: 景区导游

最近公共祖先+简单容斥，LCA边想边敲，敲的很烂，思路应该问题不大。

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include<bits/stdc++.h>
using namespace std;

int pow2[21];
int n, k;
vector<pair<int, int>>edge[100010];
long long st[100010][21];
int stt[100010][21];
int fa[100010];
int dep[100010];
int kk[100010];

void init(int x, int f) {

	for (int i = 0; i < edge[x].size(); i++) {
		auto p = edge[x][i];
		int to = p.first;
		int val = p.second;

		if (to == f) continue;
		dep[to] = dep[x] + 1;
		fa[to] = x;
		st[to][0] = val;
		stt[to][0] = x;
		for (int j = 1; j <= 20; j++) {
			int now = x;
			st[to][j] = val;
			for (int k = j - 1; k >= 0; k--) {
				st[to][j] += st[now][k];
				now = stt[now][k];
			}
			stt[to][j] = now;
		}

		init(to, x);

	}

}

long long solve(int x, int y) {

	if (dep[x] > dep[y]) swap(x, y);

	int cha = dep[y] - dep[x];

	int now = y;
	long long ans = 0;
	for (int i = 20; i >= 0; i--) {
		if (pow2[i] <= cha) {
			ans += st[now][i];
			cha -= pow2[i];
			now = stt[now][i];
		}
	}

	int lpos = x, rpos = now;
	while (1) {
		if (lpos == rpos) break;
		if (stt[lpos][0] == stt[rpos][0]) {
			ans += st[lpos][0] + st[rpos][0];
			break;
		}

		for (int i = 20; i >= 0; i--) {
			if (stt[lpos][i] == stt[rpos][i]) continue;
			ans += st[lpos][i] + st[rpos][i];
			lpos = stt[lpos][i];
			rpos = stt[rpos][i];
		}
	}

	return ans;

}

int main() {
	ios::sync_with_stdio(0);

	pow2[0] = 1;
	for (int i = 1; i <= 20; i++) pow2[i] = pow2[i - 1] * 2;

	cin >> n >> k;
	for (int i = 1; i < n; i++) {
		int u, v, t;
		cin >> u >> v >> t;
		edge[u].push_back(make_pair(v, t));
		edge[v].push_back(make_pair(u, t));

	}
	dep[1] = 1;
	init(1, 0);

	for (int i = 1; i <= k; i++) cin >> kk[i];

	long long ans = 0;

	for (int i = 2; i <= k; i++) {
		ans += solve(kk[i - 1], kk[i]);
	}

	for (int i = 1; i <= k; i++) {
		long long ff = ans;
		if (i == 1) {
			ff -= solve(kk[i], kk[i + 1]);
		}
		else if (i == k) {
			ff -= solve(kk[i - 1], kk[i]);
		}
		else {
			ff -= solve(kk[i], kk[i + 1]);
			ff -= solve(kk[i - 1], kk[i]);
			ff += solve(kk[i - 1], kk[i + 1]);
		}
		cout << ff;
		if (i != k) cout << " ";
	}

	return 0;
}

试题 J: 砍树

正解没有想到，枚举砍掉的边，用LCA判断是否在一颗子树上，可以通过30%样例。

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<bits/stdc++.h>
using namespace std;

int pow2[21];
int n, k;
vector<int>edge[100010];
int stt[100010][21];
int fa[100010];
int dep[100010];
int kl[100010], kr[100010];
int ledge[100010], redge[100010];

void init(int x, int f) {

	for (int i = 0; i < edge[x].size(); i++) {
		int to = edge[x][i];

		if (to == f) continue;
		dep[to] = dep[x] + 1;
		fa[to] = x;
		stt[to][0] = x;
		for (int j = 1; j <= 20; j++) {
			int now = x;
			for (int k = j - 1; k >= 0; k--) {
				now = stt[now][k];
			}
			stt[to][j] = now;
		}

		init(to, x);

	}

}

int solve(int x, int y) {
	if (dep[x] > dep[y]) swap(x, y);

	int cha = dep[y] - dep[x];

	int now = y;
	for (int i = 20; i >= 0; i--) {
		if (pow2[i] <= cha) {
			cha -= pow2[i];
			now = stt[now][i];
		}
	}

	int lpos = x, rpos = now;


	while (1) {
		if (lpos == rpos) break;
		if (stt[lpos][0] == stt[rpos][0]) {
			lpos = stt[lpos][0];
			break;
		}

		for (int i = 20; i >= 0; i--) {
			if (stt[lpos][i] == stt[rpos][i]) continue;
			lpos = stt[lpos][i];
			rpos = stt[rpos][i];
		}
	}

	return lpos;

}

int main() {
	ios::sync_with_stdio(0);

	pow2[0] = 1;
	for (int i = 1; i <= 20; i++) pow2[i] = pow2[i - 1] * 2;

	cin >> n >> k;
	for (int i = 1; i < n; i++) {
		int u, v, t;
		cin >> u >> v;
		edge[u].push_back(v);
		edge[v].push_back(u);
		ledge[i] = u;
		redge[i] = v;

	}
	dep[1] = 1;
	init(1, 0);
	for (int i = 1; i <= k; i++) {
		cin >> kl[i] >> kr[i];
	}

	int ans = -1;

	for (int i = 1; i < n; i++) {
		if (dep[ledge[i]] < dep[redge[i]]) swap(ledge[i], redge[i]);

		int flag = 0;
		for (int j = 1; j <= k; j++) {
			int ansa = solve(kl[j], ledge[i]);
			int ansb = solve(kr[j], ledge[i]);

			if ((ansa == ledge[i] || ansb == ledge[i]) && ansa != ansb) continue;
			flag = 1;
			break;

		}
		if (!flag) ans = i;

	}
	cout << ans;


	return 0;
}
------ THEEND ------

欢迎关注我的其它发布渠道