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

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

摘要

题目 知识点
P8770 [蓝桥杯 2022 省 A] 填空问题 - 洛谷 找规律
P8770 [蓝桥杯 2022 省 A] 填空问题 - 洛谷 博弈论
P8772 [蓝桥杯 2022 省 A] 求和 - 洛谷 前缀和
P8773 [蓝桥杯 2022 省 A] 选数异或 - 洛谷 ST表
P8775 [蓝桥杯 2022 省 A] 青蛙过河 - 洛谷 前缀和，二分
P8778 [蓝桥杯 2022 省 A] 数的拆分 - 洛谷 数论

裁纸刀

无论哪种裁法，需要的次数都相同。

从一张无界的纸上上裁剪出n行m列等大的正方形，需要至少裁剪4 + (n-1) + n*(m-1)次。

1
2
3
4
5
6
7
8
9
10
11
#include<bits/stdc++.h>
using namespace std;

int n, m;
// 443

int main(void){
	cin>>n>>m;
	cout<<4 + (n-1) + n*(m-1);
	return 0;
}

灭鼠先锋

分析情况1

1
2
X000
0000

枚举后手下两个的所有情况，都必输

1
2
XXX0 X0XX X000 X000
0000 0000 0XX0 XX00

枚举后手下一个的所有情况，都必输

1
2
XX00 X0X0 X00X X000 X000 X000 X000
0000 0000 0000 X000 0X00 00X0 000X

后续情况依次类推，得到结果为LLLV

1
2
3
4
5
6
7
#include<bits/stdc++.h>
using namespace std;

int main(void){
	cout<<"LLLV";
	return 0;
}

求和

给定 n 个整数 a1,a2,⋯,an, 求它们两两相乘再相加的和。

相当于从2遍历到n，结果累加a[i]依次乘上a[1 - i-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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e5 + 10;

ll a[maxn],pre[maxn];
ll n,sum;

// a1*a[2-n]
// a2*a[3-n]
// an*a[n-n]

int main(void){
	cin>>n;
	for(int i = 1 ; i <= n ; i ++){
		cin>>a[i];
		pre[i] = pre[i-1] + a[i];
	}
	for(int i = 1 ; i < n ; i ++){
		sum += a[i]*(pre[n] - pre[i]);
	}
	cout<<sum;
	return 0;
}

选数异或

设 a^b = x，可得 b = a^x

设f[i] 表示 [1, i] 区间内最大的 b 下标。

在遍历a[i]数组时，更新这个值，后续只要查询f[r] 是否 >= l，即可判断是否存在a[i]^a[j] = x。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e5 + 10;
unordered_map<ll, ll> mp;

ll n, m, x;
ll a[maxn], f[maxn];

int main(void){
	cin>>n>>m>>x;
	for(int i = 1 ; i <= n ; i ++){
		cin>>a[i];
		f[i] = max(f[i-1], mp[a[i]^x]);
		mp[a[i]] = i;
	}
	while(m--){
		ll l, r; cin>>l>>r;
		cout<<(f[r] < l ? "no\n":"yes\n");
	}
	return 0;
}

青蛙过河

若直接使用二分法，check遍历判断会导致超时，只能拿到部分分。

但可以用前缀和对二分法的check函数进行优化。

首先，青蛙 从左岸到右岸 和 从右岸到左岸 没有区别；青蛙跳的2*x条路径的顺序也不影响结果。

因此，可以将原题看作是2x只青蛙同时从左岸跳到右岸。

然后，可以进一步看作是 2*x 只青蛙依次从[1, y]区间移动到[2, y+1], 再依次移动到[n-y, n-1]。

等效于：每个[i, y+i-1] 的高度和 >= 2*x。

暴力解法（60/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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;

int n, x;
int h[maxn],t[maxn],mh;

bool check(int jp){
	memcpy(t,h,sizeof(h));
	for(int i = 1 ; i <= x ; i ++){
		int now = 0;
		while(now + jp < n){
			int nex = now + jp;
			while(nex > now && t[nex] == 0) nex--;
			if(nex <= now) return false;
			now = nex;
			t[now]--;
		}
	}
	return true;
}

int main(void){
	cin>>n>>x;
	x *= 2;
	for(int i = 1 ; i < n ; i ++){
		cin>>h[i];
	}
	int l = 0;
	int r = n;
	while(l+1 != r){
		int mid = (l+r)/2;
		if(check(mid)) r = mid;
		else l = mid;
	}
	cout<<r;
	return 0;
}

前缀和优化（100/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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;

int n, x;
int h[maxn], pre[maxn];

bool check(int jp){
	for(int i = 1 ; i+jp-1 < n ; i ++){
		if(pre[i+jp-1] - pre[i-1] < x){
			return false;
		}
	}
	return true;
}

int main(void){
	cin>>n>>x;
	x *= 2;
	for(int i = 1 ; i < n ; i ++){
		cin>>h[i];
		pre[i] = pre[i-1] + h[i];
	}
	int l = 0;
	int r = n;
	while(l+1 != r){
		int mid = (l+r)/2;
		if(check(mid)) r = mid;
		else l = mid;
	}
	cout<<r;
	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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

ll t;
vector<ll> is_prime, prime;

// 判断 x 是否为 立方数 / 平方数
bool judge(ll x){
	ll a = pow(x, 1.0/2);
	ll b = pow(x, 1.0/3);
	if(a*a == x || (a+1)*(a+1) == x || (a-1)*(a-1) == x) return true;
	if(b*b*b == x || (b+1)*(b+1)*(b+1) == x || (b-1)*(b-1)*(b-1) == x) return true;
	return false;
}

// 求[1-n]内的质数
void init_prime(ll n){
	is_prime.resize(n+1, true);
	is_prime[0] = is_prime[1] = false;
	for(int i = 2 ; i <= n ; i ++){
		if(is_prime[i]){
			prime.push_back(i);
			for(int j = i*i ; j <= n ; j += i){
				is_prime[j] = false;
			}
		}
	}
}

bool check(ll x){
	// 情况1：x^2*y^3
	// 所有 > 1 的整数都可表示为 2A + 3B
	// 因此，原题可规约为 x^2*y^3；
	for(auto it : prime){
		ll cnt = 0;
		while(x % it == 0){
			x /= it;
			cnt++;
		}
		if(cnt == 1) return false;
	}
	// 情况2：x^2 * 1 或者 x^3 * 1
	if(judge(x)) return true;
	return false;
}

int main(void){
	// x^2*y^3中，x, y 的最小值为 10^(18/5) < 4000
	init_prime(4000);
	cin>>t;
	while(t--){
		ll x; cin>>x;
		cout<<(check(x) ? "yes":"no")<<"\n";
	}
	return 0;
}
题解 > 蓝桥杯 > 真题模拟
#蓝桥杯
蓝桥杯软件赛C++A组省赛真题训练：2022年
https://czwcugb.github.io/题解/lanqiao/2022/
作者
ChenZhiwei
发布于
2025年4月11日
许可协议