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

摘要

题目	知识点
P9230 [蓝桥杯 2023 省 A] 幸运数 - 洛谷	模拟
P9230 [蓝桥杯 2023 省 A] 有奖问答 - 洛谷	DFS
P9231 [蓝桥杯 2023 省 A] 平方差 - 洛谷	数学
P9232 [蓝桥杯 2023 省 A] 更小的数 - 洛谷	区间DP
P9234 [蓝桥杯 2023 省 A] 买瓜 - 洛谷	折半搜索
P9236 [蓝桥杯 2023 省 A] 异或和之和 - 洛谷	位运算，前缀和

幸运数

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

// 4430091
ll ans;

bool judge(ll x){
	ll len = 0;
	ll a[20];
	while(x){
		a[++len] = x % 10;
		x /= 10;
	}
	if(len % 2 != 0) return false;
	ll s1 = 0, s2 = 0;
	for(ll i = 1 ; i <= len ; i ++){
		if(i <= len/2) s1 += a[i];
		else s2 += a[i];
	}
	return s1 == s2;
}

int main(void){
	for(ll i = 1 ; i <= 100000000 ; i ++){
		if(judge(i)){
			ans++;
		}
	}
	cout<<ans;
	return 0;
}

有奖问答

#include<bits/stdc++.h>
using namespace std;

// 8335366
int ans;

void dfs(int dep, int sco){
	if(sco == 70){
		ans++;
	}
	if(dep > 30 || sco >= 100) return;
	dfs(dep+1, sco+10);
	dfs(dep+1, 0);
}

int main(void){
	dfs(1, 0);
	cout<<ans;
	return 0;
}

平方差

题目要求我们找[L,R]区间内所有能找到 (y + z)(y - z) == x 的x的个数。 设 t = y + z ; y - z = t - 2z

原条件等效于x = t*(t - 2*z)

对所有的奇数，都可以找到x = x*1；

对所有的偶数：

1）若x/2 == 偶数，都可以找到 x = (x/2)*(2);

2）若x/2 == 奇数，找不到解；

#include<bits/stdc++.h>
using namespace std;
using ll = long long;


// n == 1 -> 1*(1 - 0)
// n == 2 -> 无
// n == 3 -> 3*(3 - 2)
// n == 4 -> 2*(2 - 0)
// n == 5 -> 5*(5 - 4)
// n == 6 -> 无
// n == 7 -> 7*(7 - 6)
// n == 8 -> 4*(4 - 2)
// n == 10 -> 无
// n == 11 -> 11*(11 - 10)
// n == 12 -> 6*(6 - 4)
// n == 13 -> 13*(13 - 12)
// n == 14 -> 无

ll l, r;
ll ans;

int main(void){
	cin>>l>>r;
	for(ll i = l ; i <= r ; i ++){
		if(i % 2 == 0 && (i/2) % 2 != 0) continue;
		ans++;
	}
	cout<<ans;
	return 0;
}

更小的数

区间DP求最长回文子串的变形。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e3 + 10;

string s;
int dp[maxn][maxn];
// -1 -> l < r
//  0 -> l == r
//  1 -> l > r
int ans;

int main(void){
	cin>>s;
	int len = s.length();
	s = " " + s;
    // 初始化长度为1和2的情况
	for(int i = 1 ; i <= len ; i ++){
		dp[i][i] = 0;
		if(i+1 <= len){
			if(s[i] < s[i+1]) dp[i][i+1] = -1;
			else if(s[i] == s[i+1]) dp[i][i+1] = 0;
			else{
				dp[i][i+1] = 1;
				ans++;
			}
		}
	}
    // dp递归
	for(int t = 3 ; t <= len ; t ++){
		for(int i = 1 ; i + t - 1 <= len ; i ++){
			int l = i;
			int r = i+t-1;
			if(s[l] < s[r]) dp[l][r] = -1;
			else if(s[l] > s[r])dp[l][r] = 1;
			else if(s[l] == s[r]) dp[l][r] = dp[l+1][r-1];
			if(dp[l][r] == 1) ans++;
		}
	}
	cout<<ans;
	return 0;
}

买瓜

直接进行DFS搜索的时间复杂度为O(3^n)，这一复杂度是不可接受的。

进行折半搜索，复杂度为O(3^n/2)：先查找前一半的组合，存入哈希表，再查找后一半的组合。

此外，还要对原数组进行排序，以优化DFS的剪枝效率。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll maxn = 50;

ll n, nh, m, ans;
ll a[maxn];
unordered_map<ll, ll> mp;

// 找前一半的瓜的所有重量和
void dfs1(ll d, ll cnt, ll sum){
	if(cnt > ans || sum > m) return; // 剪枝
	if(sum == m){ // 若已经满足条件，更新ans
		ans = min(ans, cnt);
		return;
	}
	if(d == nh + 1){ // 若找完前一半还未满足条件，记录状态到mp
		if(mp.count(sum)){
			mp[sum] = min(mp[sum], cnt);
		}else{
			mp[sum] = cnt;
		}
		return;
	}
	dfs1(d+1, cnt, sum); // 拿，不劈
	dfs1(d+1, cnt, sum + a[d]); // 拿，劈
	dfs1(d+1, cnt+1, sum + a[d]/2); // 不拿
}

void dfs2(ll d, ll cnt, ll sum){
	if(cnt > ans || sum > m) return;
	if(sum == m){
		ans = min(ans, cnt);
		return;
	}
	if(d == n+1){ // 更新ans
		if(mp.count(m - sum)){
			ans = min(ans, mp[m-sum] + cnt);
		}
		return;
	}
	dfs2(d+1, cnt, sum);
	dfs2(d+1, cnt, sum + a[d]);
	dfs2(d+1, cnt+1, sum + a[d]/2);
}

int main(void){
	cin>>n>>m;
	m *= 2;
	nh = n/2;
	ans = INT_MAX;
	for(ll i = 1 ; i <= n ; i ++){
		cin>>a[i]; a[i] *= 2;
	}
	sort(a+1, a+1+n); // 排序，提高剪枝效率
	dfs1(1, 0, 0);
	dfs2(nh+1, 0, 0);
	cout<<(ans == INT_MAX ? -1 : ans);
	return 0;
}

异或和之和

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll maxn = 1e5 + 10;

ll n,ans;
ll a[maxn], pre[maxn], cnt[50][2];

int main(void){
	cin>>n;
	for(ll i = 1 ; i <= n ; i ++){
		cin>>a[i];
		pre[i] = pre[i-1]^a[i];
	}
    //	for(ll i = 1 ; i <= n ; i ++){
    //		for(ll j = 1 ; j <= i ; j ++){
    //			ans += pre[i]^pre[j-1];
    //		}
    //	}
    // 上式可以进行优化
    // 对于所有pre中第j位，它对结果的贡献为 所有第j位0的个数 * 所有第j位1的个数 * (2^i)
    // 即：共有多少种(i,j)组合，使得这一位的异或和为1
    // 累加所有位【0-20】，即可得到总和
	for(ll i = 0 ; i <= n ; i ++){
		for(ll j = 20 ; j >= 0 ; j --){
			cnt[j][(pre[i]>>j)&1]++;
		}
	}
	for(ll i = 0 ; i <= 20 ; i ++){
		ans += cnt[i][0]*cnt[i][1]*(1<<i);
	}
	cout<<ans;
	return 0;
}