蓝桥杯真题训练-2023年省赛A组

2023年省赛题目A组

A幸运数：

描述：小蓝认为如果一个数含有偶数个数位，并且前面一半的数位之和等于后面一半的数位之和，则这个数是他的幸运数字。例如 2314 是一个幸运数字，因为它有 44 个数位，并且 2+3=1+4。现在请你帮他计算从 1 至 100000000 之间共有多少个不同的幸运数字。
思路：10^8刚好是上界，可以直接进行模拟运算，首先计算数的位数，如果是奇数直接跳过，是偶数的话，再计算平分两部分的数值累积，如果相等计入答案。
代码：

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

int main(){
//	int ans = 0;
//	for(int i = 1; i <= 100000000; i++){
//		int cnt = 0;
//		for(int j = i; j != 0; j/=10){
//			cnt++;
//		}
//		if(cnt % 2 == 1) continue;
//		int now = 0, sum = 0;
//		for(int j = i;j != 0; j/=10){
//			now++;
//			if(now <= cnt/2) sum += j % 10;
//			else sum -= j % 10; 
//		}
//		if(sum == 0) ans++;
//	}	
//	cout<<ans<<endl;
	puts("4430091");
	return 0;
}

总结：第一道题一般都是直接模拟的题目，不用考虑太多时间复杂度，关键在于老老实实清晰模拟过程即可

B有奖问答

描述：
- 小蓝正在参与一个现场问答的节目。活动中一共有 30 道题目，每题只有答对和答错两种情况，每答对一题得 10 分，答错一题分数归零。小蓝可以在任意时刻结束答题并获得目前分数对应的奖项，之后不能再答任何题目。最高奖项需要 100 分，所以到达 100 分时小蓝会直接停止答题。已知小蓝最终实际获得了 70 分对应的奖项，请问小蓝所有可能的答题情况有多少种？

解法一：dfs

思路：采用dfs，不断向下深搜，返回结果条件为到达30题或100分，分支为当前题目做对或做错
代码：

#include<bits/stdc++.h>
using namespace std;
int ans;
void dfs(int step, int score){
	if(score == 70) ans++;
	if(step == 31 || score == 100) return;
	dfs(step + 1, score + 10);
	dfs(step + 1, 0); 
}
int main()
{
	dfs(1, 0);
	cout<<ans<<endl;
	puts("8335366");
	return 0;
}

总结：其实是很明显的dfs,还是不够熟悉，熟能生巧，很棒的一道基础题。

解法二：dp

思路：发现相关的前后状态是有联系的，可以采取dp解决。dp(i)(j)表示做了i道题得分为j的方案数，分数先统一/10。
- 那么当j！=10时，dp(i)(0) += dp(i-1)(j)，相当于此时最终得分为0，那么这i道题最后一道肯定是答错的，前i-1道题任意组合，那么就是dp(i-1)(j)的累加，但是j不能等于10，因为这表示已经满分了，不会再进行答题。
- 那么当j！=0时，dp(i)(j) = dp(i-1)(j-1),表示当前第i道题肯定是答对的，那么前i-1道题得分为j-1的方案数就是之前算出来的dp(i-1)(j-1)
- 总的来说，还是当前这第i道题是答对还是答错，答错就是之前的累加，答对就是左上角的方案数。列出对应的二维表会非常清晰
代码：

#include<bits/stdc++.h>
using namespace std;
int dp[35][15], ans; 
int main()
{
	dp[0][0] = 1;
	for(int i = 1; i <= 30; i++){
		for(int j = 0; j <= 10; j++){
			if(j != 10){
				dp[i][0] += dp[i-1][j];
			}
			if(j != 0){
				dp[i][j] = dp[i-1][j-1];
			}
		}
	}
	for(int i = 0; i<= 30; i++){
		ans+=dp[i][7];
	}
	cout<<ans<<endl;
	return 0;
}

总结：其实可以算是一道背包问题，只有一个特殊点就是分数到100就停止答题了。对于这类较为基础的dp还是有多多联系，是可以拿下的。

C平方差

描述：给定 L,R，问 L≤x≤R 中有多少个 x 满足存在整数 y,z，使得 x = y2 - z2。
思路：通过展开平方差即x = (y + z)*(y - z),可知x是奇数或是4的倍数，那么直接计算这两个的个数即可
代码1：

#include<bits/stdc++.h>
using namespace std;
int odd, four,l,r; 
int main()
{
	cin>>l>>r;
	int cnt = r - l + 1;
	if(cnt % 2 == 0) odd = cnt / 2;
	else if(l % 2 == 0) odd = cnt /2;
	else odd = cnt / 2 + 1;
	
	if(cnt % 4 == 0) four = cnt / 4;
	else{
		int yu = cnt % 4;
		for(int i = 1; i <= yu; i++){
			if((l + i - 1) % 4 == 0){
				four = 1;
			}
		}
		four += cnt / 4;
	}
	cout<< odd + four<<endl;
	return 0;
}

代码2：当计算分支比较多时，可以考虑反方向计算，可能会更加简单

#include<iostream>
using namespace std;
int main()
{
    int l, r, ans = 0; //ans为不满足的条件
    cin>>l>>r; 
    int x = r / 2 - (l-1) / 2; //2的倍数
    int y = r / 4 - (l-1) / 4; //4的倍数
    ans = x - y; //不满足条件
    //cout<<x<<" "<<y<<endl;
    cout<<(r - l + 1) - ans; //总数 - 不满足条件
    return 0;
}

总结：当时这道题目应该是做出来了的，只要认真分析题目所给条件并不难，或者通过找规律也可以找到解题线索。

D更小的数

描述：小蓝有一个长度均为 n 且仅由数字字符 0 ~ 9 组成的字符串，下标从 0 到 n - 1。
你可以将其视作是一个具有 n 位的十进制数字 num。
小蓝可以从 num 中选出一段连续的子串并将子串进行反转，最多反转一次。
小蓝想要将选出的子串进行反转后再放入原位置处得到的新的数字 numnew 满足条件numnew < num。
请你帮他计算下一共有多少种不同的子串选择方案。
只要两个子串在 num 中的位置不完全相同我们就视作是不同的方案。
注意，我们允许前导零的存在，即数字的最高位可以是 0 ，这是合法的

解法一：dp

思路：采取区间dp，发现若对任意的l,r，先比较的是s[l]和s[r],如果s[l]>s[r]则方案数加1，等于则看是s[l + 1]和s[r - 1],小于就是0。可以看到是存在子问题重叠的，子问题的最优解能代表整个问题的最优解。另外，这种二维dp的遍历方式一般都是先遍历长度再遍历左节点。
代码：

#include<bits/stdc++.h>
using namespace std;
int dp[5050][5050],ans; 
int main()
{
	string s;
	cin>>s;
	int n = s.size();
	for(int len = 2; len <= n; len ++){
		for(int l = 0; l + len - 1 < n; l++){
			int r = l + len - 1;
			if(s[l] > s[r]) dp[l][r] = 1;
			else if(s[l] == s[r]) dp[l][r] = dp[l + 1][r-1];
			ans += dp[l][r];
		}
	}
	cout<<ans<<endl;
	return 0;
}

总结：并不是很负责的区间dp,需要仔细分析通用情况，要多多熟练这种题型呀~

解法二：常规

思路：双重循环遍历，相等的情况直接算不行，但是当产生一个可行时，由里向外检查相同的情况，也算是可行方案，时间复杂也是O(N^2)。
代码：

#include<bits/stdc++.h>
using namespace std;
string s;
int ans;
int main()
{
	cin>>s;
	int n = s.size();
	for(int i = 0; i < n; i++){
		for(int j = i + 1; j < n;j++){
			if(s[i] <= s[j]) continue;
			ans++;
			for(int k = 1; i - k >=0 && j + k <=n; k++){
				if(s[i - k] == s[j + k]) ans++;
				else break; //剪枝
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

总结：也是很巧妙的做法，尤其是由里向外扩展检查这一步，时间复杂度应该也是O(N^2)，空间复杂度相对较低，为O(1)。

H异或和之和

描述：给定一个数组 A[i]，分别求其每个子段的异或和，并求出它们的和。或者说，对于每组满足 1≤L≤R≤n 的 L*,R，求出数组中第 L 至第 R 个元素的异或和。然后输出每组L,*R得到的结果加起来的值。
思路：连续异或具有前缀和的性质，即S[l,r]表示l到r的异或和等于S[r]^S[l-1],另外异或是针对位来说的，可以把每个数字都按位拆解。按照类似前缀和的方式求出每个S[i],那么它们要么是0，要么是1，进行任意组合的方案数就是0的个数乘以1的个数，再乘回当前位的权重累加就是最终结果了。注意计算0，1个数要从0开始。
代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int n, a[100050], cnt[2], sum, s[100050];
signed main()
{
	cin>>n;
	for(int i = 1; i <= n; i++) cin>>a[i];
	for(int i = 0; i <= 20; i++){
		for(int j = 1; j <= n; j++){
			if((a[j]>>i) & 1) s[j] = s[j - 1] ^ 1;
			else s[j] = s[j - 1];
		}
		cnt[0] = cnt[1] = 0;
		for(int k = 0; k <= n; k++){ //参考前缀和，s[0]也要包括进来，因为s[i]和s[j]的异或实际表示的是a[i+1]到a[j]的异或和
			cnt[s[k]]++; 
		}
		sum += (1ll << i) * cnt[0] * cnt[1];
	}
	cout<<sum<<endl;
	
	return 0;
}

总结：针对位运算的一道题，异或性质和前缀和的性质竟然是类似的，很有意思，一个全新的视角解决了这道题。

F买瓜

描述：小蓝正在一个瓜摊上买瓜。瓜摊上共有 n 个瓜，每个瓜的重量为Ai。小蓝刀功了得，他可以把任何瓜劈成完全等重的两份，不过每个瓜只能劈一刀。小蓝希望买到的瓜的重量的和恰好为 m。

请问小蓝至少要劈多少个瓜才能买到重量恰好为 m 的瓜。如果无论怎样小蓝都无法得到总重恰好为 m 的瓜，请输出 −1。

解法一：暴力dfs+剪枝

思路：每种瓜都有三种可能，不买，劈了买，不劈买，遍历三种可能然后不断往下递归，直到越界或者找到正确答案。由于0.5不好计算，可以把所有重量均乘以2。
代码：

#include<bits/stdc++.h>
using namespace std;
int n, a[35], ans = 35;
long long m; 
void dfs(int step, int status, int cnt, long long sum){
	if(sum > m) return;
	if(step > n){
		if(sum == m) ans = min(ans, cnt);
		return;
	} 
	if(status == 0) sum += 2 * a[step];
	else if(status == 1) sum += a[step], cnt++;
	for(int i = 0; i < 3; i++) dfs(step + 1, i, cnt, sum);
	return;
}
int main()
{
	cin>>n>>m;
	m = m * 2;
	for(int i = 1; i <= n; i++){
		cin>>a[i];
	}
	for(int i = 0; i < 3; i++){
		dfs(1, i, 0, 0);
	}
	cout<<ans<<endl;
	
	return 0;
}

总结：暴力的本质就是递归，其实就是先遍历当前瓜的所有可能，然后再往下递归下一个瓜的所有可能，对于这种暴力模拟做法还是要掌握的。

E颜色平衡树

描述：给定一棵树，结点由 1至 n 编号，其中结点 1 是树根。树的每个点有一个颜色 Ci。

如果一棵树中存在的每种颜色的结点个数都相同，则我们称它是一棵颜色平衡树。

求出这棵树中有多少个子树是颜色平衡树。
思路：dfs深度递归每一棵树，先cnt(u)(x) = p,表示根节点为u的子树颜色为x的有p个，然后sum(u)(cnt(u)(k)) = q表示以u为根节点的子树下颜色个数为cnt(u)(k)的有q组，如果最终sum(u)的大小为1，表示所有颜色的个数都是相同的。cnt和sum都是三维结构，采用unordered_map存储。
代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, c[N], ans;
vector<int> g[N];
unordered_map<int, int> cnt[N], sum[N];
void dfs(int u){
	cnt[u][c[u]] = 1;
	sum[u][1] = 1;
	for(auto &v : g[u]){
		dfs(v);
		for(auto &it : cnt[v]){
			int x = it.first, y = it.second;
			if(cnt[u].count(x)){
				sum[u][cnt[u][x]]--;
				if(sum[u][cnt[u][x]] == 0){
					sum[u].erase(cnt[u][x]);
				}
			}
			sum[u][cnt[u][x]+=y]++;
		}
	}
	if(sum[u].size() == 1) ans++;
}
int main()
{
	cin>>n;
	for(int i = 1, x; i <= n; i++){
		cin >> c[i] >> x;
		g[x].emplace_back(i);
	}
	dfs(1);
	cout<<ans; 
	
	return 0;
}

总结：很厉害的写法，尤其是sum的增加使得原先需要遍历所有的cnt判断颜色个数是否一致可以O(1)的时间复杂度判断出来，而对sum的递推是直接内嵌在dfs里的，太厉害了。还有unordered_map对于三维数组的应用也非常熟练，太厉害了！而且这个dfs也没有一般的终结条件，即叶节点，相当于隐式的方式了。很棒的一道题，考场上要是能模拟出这种暴力真的就太棒了！~

G网络稳定性：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int dp[5005][5005]; 
int n, m, q;
signed main()
{
	memset(dp,-1,sizeof(dp));
	cin>>n>>m>>q;
	int u,v,x;
	while(m--){
		cin>>u>>v>>x;
		dp[u][v] = max(dp[u][v], x);
		dp[v][u] = max(dp[v][u], x);
	}
	for(int k = 1; k <= n; k++){
		for(int i = 1; i <= n ;i++){
			for(int j = 1; j <= n; j++){
				if(i != j && i != k && j != k){
					dp[i][j] = max(dp[i][j], min(dp[i][k],dp[k][j]));
				}
			}
		}
	}
	while(q--){
		cin>>u>>v;
		cout<<dp[u][v]<<endl;
	}
	return 0;
}

算法

#蓝桥杯

蓝桥杯真题训练-2023年省赛A组

http://example.com/2024/03/02/蓝桥杯省赛备赛/蓝桥杯真题训练/

作者

jhxxxxx

发布于

2024年3月2日

许可协议

蓝桥杯真题训练-2023年省赛B组上一篇

力扣链表部分题目总结---基本完结~ 下一篇