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

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

摘要

题目 知识点
P8740 [蓝桥杯 2021 省 A] 填空问题 - 洛谷（卡片） 模拟
P8740 [蓝桥杯 2021 省 A] 填空问题 - 洛谷（直线） 计算几何
P8740 [蓝桥杯 2021 省 A] 填空问题 - 洛谷（货物摆放） 数学
P8740 [蓝桥杯 2021 省 A] 填空问题 - 洛谷（路径） Floyd最短路
P8740 [蓝桥杯 2021 省 A] 填空问题 - 洛谷（回路计数） 状压DP
P8742 [蓝桥杯 2021 省 AB] 砝码称重 - 洛谷 背包问题
P8743 [蓝桥杯 2021 省 A] 异或数列 - 洛谷 博弈论，位运算

卡片

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 a[10];
// ans = 3181

int main(void){
	for(int i = 0 ; i <= 9 ; i ++){
		a[i] = 2021;
	}
	for(int i = 1 ; ; i ++){
		int x = i;
		while(x){
			if(a[x%10] == 0){
				cout<<i-1;
				return 0;
			}
			a[x%10]--;
			x /= 10;
		}
	}
	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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

// y1 = k*x1 + b;
// y2 = k*x2 + b;
// k = (y1 - y2)/(x1 - x2);
// b = y1 - k*x1;

vector<pair<double, double> > v;
// 40257

void solve(ll x1, ll y1, ll x2, ll y2){
	if(x1 == x2 || y1 == y2) return; // x = t 和 y = t的情况单独计算
	double k = 1.0*(y1 - y2)/(x1 - x2);
	double b = 1.0*y1 - k*x1;
	for(auto it : v){ // 去重
		double ki = it.first;
		double bi = it.second;
		if(fabs(ki - k) <= 1e-8 && fabs(bi - b) <= 1e-8){
			return;
		}
	}
	v.push_back({k, b});
}

int main(void){
	for(ll x1 = 0 ; x1 < 20 ; x1 ++){
		for(ll y1 = 0 ; y1 < 21 ; y1 ++){
			for(ll x2 = 0 ; x2 < 20 ; x2 ++){
				for(ll y2 = 0 ; y2 < 21 ; y2 ++){
					solve(x1, y1, x2, y2);
				}
			}
		}
	}
	cout<<v.size() + 20 + 21;
	return 0;
}

货物摆放

\(O（\sqrt{n}*n^{1/4}）\)的时间复杂度是可以接受的，暴力遍历所有组合即可。注意用排序和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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

// n = 1 -> 1x1x1 -> 1种
// n = 2 -> 2x1x1, 1x2x1, 1x1x2 -> 3种
// n = 3 -> 3x1x1, 1x3x1, 1x1x3 -> 4种
// n = 4 -> 4*1*1, 1*4*1, 1*1*4; 2*2*1, 2*1*2, 1*2*2 -> 6种
// n = 5 -> 5*1*1, 1*5*1, 1*1*5; -> 3种
// n = 6 -> 5*1*1, 1*5*1, 1*1*5; 2*3*1, 2*1*3, 1*2*3(+3) -> 9种

ll ans; // 2430
set<pair< pair<ll, ll>, ll > > st;

void add(ll x, ll y, ll z){
	ll a[3]; a[0] = x; a[1] = y; a[2] = z;
	sort(a, a+3); // 对输入的x, y, z排序, 去重
	st.insert({{a[0], a[1]}, a[2]});
}


int main(void){
	ll n = 2021041820210418;
	for(ll x = 1 ; x*x <= n; x ++){
		if(n % x == 0){
			ll y = n/x;
			for(ll z = 1 ; z*z <= x ; z ++){
				if(x % z == 0){
					add(z, x/z, y);
				}
			}
			for(ll z = 1 ; z*z <= y ; z ++){
				if(y % z == 0){
					add(z, y/z, x);
				}
			}
		}
	}
	for(auto it : st){
		ll x = it.first.first;
		ll y = it.first.second;
		ll z = it.second;
		// cout<<x<<" * "<<y<<" * "<<z<<" == "<<n<<"\n";
		if(x == y && y == z){
			ans += 1; // 1
		}else if(x == y || y == z || x == z){
			ans += 3; // Cn^1
		}else{
			ans += 6; // A3^3
		}
	}
	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
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;
using ll = long long;
const ll inf = 0x3f3f3f3f3f3f3f3f;

// 对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21
// 则两个结点 之间没有边相连；
// 如果 a 和 b 的差的绝对值小于等于 21
// 则两个点之间有一条 长度为 a 和 b 的最小公倍数的无向边相连。

ll gcd(ll x, ll y){
	return y == 0 ? x : gcd(y, x%y);
}

ll lcm(ll x, ll y){
	return x*y/gcd(x,y);
}

ll e[3000][3000];
// ans = 10266837
int main(void){
	ll n = 2021;
	for(ll i = 1 ; i <= n ; i ++){
		for(ll j = 1 ; j <= n ; j ++){
			e[i][j] = inf;
		}
	}
	for(ll i = 1 ; i <= n ; i ++){
		for(ll j = i+1 ; j <= n ; j ++){
			ll gap = llabs(i-j);
			if(gap <= 21){
				e[i][j] = e[j][i] = lcm(i,j);
			}
		}
	}
	// floyd
	for(ll k = 1 ; k <= n ; k ++){
		for(ll i = 1 ; i <= n ; i ++){
			if(e[i][k] == inf) continue;
			for(ll j = 1 ; j <= n ; j ++){
				e[i][j] = min(e[i][j], e[i][k] + e[k][j]);
			}
		}
	}
	cout<<e[1][2021];
	return 0;
}

回路计数

状态压缩DP求最短哈密顿回路（TSP）。

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;
using ll = long long;
const int maxn = 22;

ll dp[maxn+1][1<<(maxn)];
ll n,ans;
vector<ll > e[maxn];
// ans = 881012367360

ll gcd(ll x, ll y){
	return y == 0 ? x : gcd(y, x%y);
}

int main(void){
	cin>>n;
	for(ll i = 1 ; i <= n ; i ++){
		for(ll j = i+1 ; j <= n ; j ++){
			if(gcd(i, j) == 1){
				e[i].push_back(j);
				e[j].push_back(i);
			}
		}
	}
	dp[1][1] = 1;
	for(ll s = 0; s <= (1<<n)-1 ; s ++){
		for(ll i = 1 ; i <= n ; i ++){
			if((s >> (i-1)) & 1){
				for(auto it : e[i]){
					dp[i][s] += dp[it][s & ~(1<<(i-1))];
				}
			}
		}
	}
	for(auto it : e[1]){
		ans += dp[it][(1<<n)-1];
	}
	cout<<ans;
	return 0;
}

砝码称重

DFS(7/15)

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 = 200;
const int maxm = 2e5;

int a[maxn];
int n, ans;
bool vis[maxm];

void dfs(int l, int d){
	if(d == n+1){
		if(l > 0 && !vis[l]){
			vis[l] = true;
			ans++;
		}
		return;
	}
    // 朴素枚举3种状态
	dfs(l+a[d], d+1);
	dfs(l, d+1);
	dfs(l-a[d], d+1);
}

int main(void){
	cin>>n;
	for(int i = 1 ; i <= n ; i ++){
		cin>>a[i];
	}
	sort(a+1, a+1+n);
	dfs(0, 1);
	cout<<ans;
	return 0;
}

DP(15/15)

设\(dp[i][j]\)为使用[1, i]区间内的砝码，能不能称出重量j。

状态转移方程： \[ dp[i][j] = dp[i-1][j] \space | \space dp[i-1][j+a[i]] \space | \space dp[i-1][abs(j-a[i])] \] 三种状态分别为：不使用砝码i | j为i砝码i和之前某一重量之和 | j为砝码i的之前某一重量之差。

这里用 |j-a[i]| 的原因是，虽然j-a[i]为负，但 |j-a[i]| 仍然合法，将第i个砝码作为较重的一侧即可。

此外，这里不能用一维数组优化的原因是，涉及到 j+a[i] 和 j-a[i]。因此，无论j从m到1，还是i到m，都会导致第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
26
27
#include<bits/stdc++.h>
using namespace std;
const int maxn = 200;
const int maxm = 2e5;

bool dp[maxn][maxm];
int a[maxn];
int n, sum, ans;

int main(void){
	cin>>n;
	dp[0][0] = true;
	for(int i = 1 ; i <= n ; i ++){
		cin>>a[i];
		sum += a[i];
	}
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 0 ; j <= sum ; j ++){
			dp[i][j] = dp[i-1][j] | dp[i-1][j+a[i]] | dp[i-1][abs(j-a[i])];
		}
	}
	for(int i = 1 ; i <= sum ; i ++){
		if(dp[n][i]) ans++;
	}
	cout<<ans;
	return 0;
}

异或数列

将一个X用异或运算拆分为A和B，A和B的大小取决于它们的最高非零位；

这可以理解成一个贪心问题，我们需要从高位到地位依次判断：

设bits[i] 为所有数的第i位一共包含几个1。

若bits[i] == 1， 那么Alice的这一位一定为1，Bob这一位一定为0，Alice胜；

若bit[i] != 1 且为奇数，先手必胜。但还需要考虑0位的个数，0位可以改变先后手顺序。若0位个数为偶数，Alice胜，否则Bob胜；

若bits[i] 为偶数，那么该位无论怎么划分，Alice和Bob的这一位一定相同，考虑下一位；

若所有bits[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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;

int t;
int a[maxn];
int bits[30]; // 第i位一共包含几个1

// 统计 x 的每个为1的二进制位
void getBits(int x){
	int bit = 1;
	while(x){
		if(x & 1) bits[bit]++;
		bit++;
		x >>= 1;
	}
}

void solve(){
	memset(bits,0,sizeof(bits));
	int n; cin>>n;
	for(int i = 1 ; i <= n ; i ++){
		cin>>a[i];
		getBits(a[i]);
	}
	for(int i = 21; i >= 1 ; i --){
		if(bits[i] == 1){
			cout<<"1\n";
			return;
		}
		if(bits[i] & 1){
			if((n - bits[i]) & 1) cout<<"-1\n";
			else cout<<"1\n";
			return;
		}
	}
	cout<<"0\n";
}

int main(void){
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}
题解 > 蓝桥杯 > 真题模拟
#蓝桥杯
蓝桥杯软件赛C++A组省赛真题训练：2021年
https://czwcugb.github.io/题解/lanqiao/2021/
作者
ChenZhiwei
发布于
2025年4月13日
许可协议