蓝桥杯软件赛C++A组省赛真题训练：2025年

蓝桥杯软件赛C++A组省赛真题训练：2025年

摘要

题目 知识点
P12138 [蓝桥杯 2025 省 A] 寻找质数 - 洛谷 质数筛
P12139 [蓝桥杯 2025 省 A] 黑白棋 - 洛谷 DFS
P12140 [蓝桥杯 2025 省 A] 抽奖 - 洛谷 模拟
P12141 [蓝桥杯 2025 省 A] 红黑树 - 洛谷 二叉树
P12142 [蓝桥杯 2025 省 A] 黑客 - 洛谷 组合数学
P12143 [蓝桥杯 2025 省 A] 好串的数目 - 洛谷 双指针/组合数
P12144 [蓝桥杯 2025 省 A] 地雷阵 - 洛谷 -
P12145 [蓝桥杯 2025 省 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
#include<bits/stdc++.h>
using namespace std;

// 17609
bool judge(int x){
	if(x < 2) return false;
	for(int i = 2 ; i*i <= x ; i ++){
		if(x % i == 0) return false;
	}
	return true;
}

int main(void){
	int cnt = 0;
	int x = 1;
	while(cnt < 2025){
		if(judge(x)){
			cnt++;
			cout<<cnt<<": "<<x<<"\n";
		}
		x++;
	}
	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
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
#include<bits/stdc++.h>
using namespace std;

string s[10];
bool vis[10][10];
// 101001010011101100010110011001100110

bool judge(){
	// 在每一行和每一列中，黑色棋子和白色棋子的数量必须相等。
	for(int i = 1 ; i <= 6 ; i ++){
		int row = 0, col = 0;
		for(int j = 1 ; j <= 6 ; j ++){
			if(s[i][j] == '1') row++;
			if(s[j][i] == '1') col++;
		}
		if(row != 3 || col != 3) return false;
	}
	// 在棋盘的任何一行或一列中，不能有超过两个相同颜色的棋子连续排列
	// （即不允许出现“黑黑黑”或“白白白”的情况）。
	for(int i = 1 ; i <= 6 ; i ++){
		for(int j = 1 ; j+2 <= 6 ; j ++){
			if(s[i][j] == s[i][j+1] && s[i][j] == s[i][j+2]){
				return false;
			}
			if(s[j][i] == s[j+1][i] && s[j][i] == s[j+2][i]){
				return false;
			}
		}
	}
	// 每一行的棋子排列方式必须是唯一的，不能与棋盘中的任何其他行完全相同。
	// 每一列的棋子排列方式必须是唯一的，不能与棋盘中的任何其他列完全相同。
	string res[10];
	for(int i = 1 ; i <= 6 ; i ++){
		res[i] = "";
		for(int j = 1 ; j <= 6 ; j ++){
			res[i] += s[j][i];
		}
	}
	for(int i = 1 ; i <= 6 ; i ++){
		for(int j = i+1 ; j <= 6 ; j ++){
			if(s[i] == s[j]) return false;
			if(res[i] == res[j]) return false;
		}
	}
	return true;
}

void dfs(int x, int y){
	if(x == 6 && y == 6){
		s[x][y] = '0';
		if(judge()){
			for(int i = 1 ; i <= 6 ; i ++){
				cout<<s[i].substr(1, s[i].length()-1);
			}
			cout<<"\n";
		}
		s[x][y] = '1';
		if(judge()){
			for(int i = 1 ; i <= 6 ; i ++){
				cout<<s[i].substr(1, s[i].length()-1);
			}
			cout<<"\n";
		}
		return;
	}
	if(x == 6){
		if(vis[x][y]){
			dfs(1, y+1);
		}else{
			s[x][y] = '1';
			dfs(1, y+1);
			s[x][y] = '0';
			dfs(1, y+1);
		}
	}else{
		if(vis[x][y]){
			dfs(x+1, y);
		}else{
			s[x][y] = '0';
			dfs(x+1, y);
			s[x][y] = '1';
			dfs(x+1, y);
		}
	}
}

int main(void){
	s[1] = " 103033";
	s[2] = " 333033";
	s[3] = " 333300";
	s[4] = " 333333";
	s[5] = " 331331";
	s[6] = " 303313";
	for(int i = 1 ; i <= 6 ; i ++){
		for(int j = 1 ; j <= 6 ; j ++){
			if(s[i][j] == '1' || s[i][j] == '0'){
				vis[i][j] = true;
			}
		}
	}
	dfs(1, 1);
	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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll maxn = 1e3 + 10;

ll n, m, ans;
ll a[4][maxn], cnt[4];

ll getPrice(){
	ll t[4];
	for(ll i = 1 ; i <= 3 ; i++){
		t[i] = a[i][cnt[i]];
	}
	// 三个相同的图案，积分 +200；
	if(t[1] == t[2] && t[1] == t[3]){
		return 200;
	}
	// 三个数字图案，从左到右连续（例如 1,2,3），积分 +200
	if(t[1] == t[2]-1 && t[2] == t[3]-1){
		return 200;
	}
	// 三个数字图案，经过顺序调整后连续（例如 2,1,3 或 3,2,1），积分 +100；
	sort(t+1, t+4);
	if(t[1] == t[2]-1 && t[2] == t[3]-1){
		return 100;
	}
	// 两个相同的图案，积分 +100；
	if(t[1] == t[2] || t[2] == t[3]){
		return 100;
	}
	return 0;
}

void solve(){
	for(ll i = 1 ; i <= 3 ; i ++){
		ll x; cin>>x;
		cnt[i] = (cnt[i] + x) % n;
	}
	ans += getPrice();
}

int main(void){
	cin>>n;
	for(ll i = 1 ; i <= 3 ; i ++){
		for(ll j = 0 ; j < n ; j ++){
			cin>>a[i][j];
		}
	}
	cin>>m;
	while(m--){
		solve();
	}
	cout<<ans;
	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
#include<bits/stdc++.h>
using namespace std;

int m;

void solve(){
	int n, k; cin>>n>>k;
	bool same = true;
	for(int i = n ; i > 1 ; i --){
		if(k % 2 == 0) same = !same;
		k = (k+1)/2;
	}
	if(same) cout<<"RED\n";
	else cout<<"BLACK\n";
}

int main(void){
	cin>>m;
	while(m--){
		solve();
	}
	return 0;
}

黑客

（30/100）

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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1000000007;
const ll maxn = 5e5 + 10;

ll n, nm;
ll a[maxn];
ll p[maxn], A, ans;
unordered_map<ll, ll> mp;

int main(void){
	cin.tie(0); cout.tie(0);
	ios::sync_with_stdio(false);
	cin>>n;
	nm = n-2;
	for(int i = 1 ; i <= n ; i ++){
		cin>>a[i];
		mp[a[i]]++;
		if(p[a[i]] == 0) p[a[i]] = 1;
		p[a[i]] *= mp[a[i]];
	}
	A = 1;
	for(int i = 1 ; i <= n-2 ; i ++){
		A = (A*i) % mod;
	}
	for(const auto & it : mp){
		ll num = it.first;
		if(nm % num == 0 && mp.count(nm/num) != 0){
			ll add = A;
			for(const auto & jt : mp){
				ll num2 = jt.first;
				ll k2 = jt.second;
				add /= p[num2];
				if(num2 == num || num2 == nm/num){
					add *= k2;
				}
			}
			ans += add;
		}
	}
	cout<<ans;
	return 0;
}

好串的数目

（80/100）区间DP

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

string s;
ll ans;

bool judge(char x, char y){
	int xv = x - '0';
	int yv = y - '0';
	return xv == yv || xv == yv - 1;
}

int main(void){
	cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
	cin>>s;
	vector<vector<bool> > dp(s.length(), vector<bool>(s.length()));
	for(int i = 0 ; i < s.length() ; i ++){
		dp[i][i] = true;
		ans++;
		if(i > 0){
			dp[i-1][i] = true;
			ans++;
		}
	}
	for(int len = 3 ; len <= s.length() ; len ++){
		for(int l = 0 ; l+len-1 < s.length() ; l ++){
			int r = l+len-1;
			dp[l][r] = (dp[l+1][r] && judge(s[l], s[l+1])) || (dp[l][r-1] && judge(s[r-1], s[r]));
			if(dp[l][r]) ans++;
			// cout<<l<<":"<<r<<" -> "<<dp[l][r]<<"\n";
		}
	}
	cout<<ans;
	return 0;
}

（100/100）组合数

好串可以分为两种：

A.本身就是连续上升序列；B.由两个连续上升序列合并而成；

首先，我们将原字符串按极大连续上升序列划分，得到预处理数组len。

对于每段长度为n的上升序列，A类好串的个数为 1 + 2 + ... + n，用等差数列求和公式即可。

然后枚举2段相邻的上升序列，假设长度分别为n和m，B类好串的个数为n*m。

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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e5;

string s;
ll len[maxn], cnt;
ll ans;

int main(void){
	cin>>s;
	ll p = 1;
	for(int i = 1 ; i < s.length() ; i ++){
		if(s[i] == s[i-1] || s[i] == s[i-1] + 1){
			p++;
		}else{
			len[cnt++] = p;
			p = 1;
		}
	}
	len[cnt++] = p;
	for(int i = 0 ; i < cnt ; i ++){
		ans += len[i] + len[i]*(len[i]-1)/2;
		if(i > 0) ans += len[i]*len[i-1];
	}
	cout<<ans;
	return 0;
}

（100/100）双指针

设指针L,R所代表的区间 [ L, R ]为以R结尾的，最多违反上升规则的一次的最长序列。

根据这个规则，每次在答案上累加R-L+1即可。

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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e5;

string s;
ll ans, cnt;

int main(void){
	cin>>s;
	ans = 1;
	for(int l = 0, r = 1 ; r < s.length() ; r ++){
		if(!(s[r] == s[r-1] || s[r] == s[r-1] + 1)){
			cnt++;
		}
		while(cnt > 1){
			if(!(s[l+1] == s[l] || s[l+1] == s[l] + 1)){
				cnt--;
			}
			l++;
		}
		ans += (r-l+1);
	}
	cout<<ans;
	return 0;
}
题解 > 蓝桥杯 > 真题模拟
#蓝桥杯
蓝桥杯软件赛C++A组省赛真题训练：2025年
https://czwcugb.github.io/题解/lanqiao/2025/
作者
ChenZhiwei
发布于
2025年4月23日
许可协议