蓝桥杯第十四届蓝桥杯大赛软件赛省赛C/C++ 大学 A 组题解

1.幸运数

题目链接：0幸运数 - 蓝桥云课 (lanqiao.cn)

#include<bits/stdc++.h>
using namespace std;
bool deng(string& num){int n = num.size();int qian = 0,hou = 0;for(int i=0;i<n/2;i++) qian += (num[i]-'0');for(int i=n/2;i<n;i++) hou += (num[i]-'0');return qian == hou;
}
int main()
{// 请在此输入您的代码// int ans = 0;// for(int i=1;i<=100000000;i++){//   string num = to_string(i);//   if(num.size()%2==0){//     if(deng(num))//       ans++;//   }// }cout<<4430091<<endl;return 0;
}

2.有奖问答

题目链接：0有奖问答 - 蓝桥云课 (lanqiao.cn) 

这段代码使用动态规划（DP）来解决一个特定的问题，涉及到一系列的题目，每道题目答对可以获得10分，答错分数归零。目标是计算所有可能的得分方式中，最终得分为70分的总方案数。下面是代码的逐行解释：

1. int dp[31][100]; 这行代码声明了一个二维数组 dp，其中 dp[i][j] 用于存储在完成第 i 题后，累计得分为 j 的所有可能的方案数。数组的大小为31行（考虑到0到30题）和100列（考虑到分数从0到90，每10分一个区间）。

2. int res=0; 初始化结果变量 res，这个变量将用来存储所有得分为70的方案总数。

3. dp[1][0]=dp[1][10]=1; 设置初始条件，表示第一题答错和答对的方案数都是1。这是动态规划的基础，从这些初始条件开始，可以计算出后续所有的情况。

4. 循环 for(int i=2 ; i<=30 ; i++) 遍历从第2题到第30题的每一题。

5. 内层循环 for(int j=0 ; j<=90 ; j+=10) 遍历所有可能的得分情况，即0到90分（每隔10分遍历一次）。这里不包括100分，因为题目设定中，一旦得分达到100分，游戏/测试就会结束。

6. if(j==0) 这个条件处理的是第 i 题答错的情况，即得分归零的情况。在这种情况下，dp[i][0]（即在第 i 题后得分为0的方案数）等于在完成第 i-1 题后所有可能得分（0到90分，每隔10分）的方案数之和。

7. else 部分处理的是第 i 题答对的情况。在这种情况下，如果在第 i-1 题后得分为 j-10，则在第 i 题答对后，得分会变为 j。因此，dp[i][j] 等于 dp[i-1][j-10]。

8. if(j == 70) res+=dp[i][j]; 如果在第 i 题后得分为70分，则将这些方案数加到 res 上，因为题目要求计算所有得分为70分的方案数。

最终，通过动态规划填充 dp 数组，所有得分为70分的方案数被累加到 res 中。最后，cout<<res; 输出这个总方案数。这种使用动态规划的方法高效地遍历了所有可能的答题方案，计算出了满足条件的总方案数。

#include<bits/stdc++.h>
using namespace std;
int dp[31][100];
int main(){int res = 0;dp[1][0] = dp[1][10] = 1;for(int i=2;i<=30;i++){for(int j=0;j<=90;j+=10){if(j==0){for(int k=0;k<=90;k+=10)dp[i][0] += dp[i-1][k];}else{dp[i][j] = dp[i-1][j-10];if(j==70) res+=dp[i][j];}}}cout<<res<<endl;return 0;
}

3.平方差

题目链接：0平方差 - 蓝桥云课 (lanqiao.cn)

居然还有负的输入数据，居然还有大整数乘大整数！

死活过不了的代码，开摆：

#include<bits/stdc++.h>
using namespace std;
vector<int> add(vector<int> &A, vector<int> &B) {vector<int> C;int t = 0;for (int i = 0; i < A.size() || i < B.size(); i++) {if (i < A.size()) t += A[i];if (i < B.size()) t += B[i];C.push_back(t % 10);t /= 10;}if (t > 0) C.push_back(t);  // 处理最后的进位return C;
}
bool cmp(vector<int> &A,vector<int> &B){if(A.size()!=B.size()) return A.size()>B.size();for(int i=A.size()-1;i>=0;i--){if(A[i]!=B[i]) return A[i]>B[i];}return true;
}
vector<int> sub(vector<int> &A,vector<int> &B){vector<int> C;int t = 0;for(int i=0;i<A.size();i++){t = A[i] - t;if(i<B.size()) t-=B[i];C.push_back((t+10)%10);if(t<0) t = 1;else t = 0;}while(C.size()>1&&C.back()==0) C.pop_back();return C;
}
vector<int> mul(vector<int>& A, vector<int>& B) {vector<int> C(A.size() + B.size(), 0);  // 乘积的最大可能位数为两乘数位数之和// 逐位相乘for (size_t i = 0; i < A.size(); ++i) {for (size_t j = 0; j < B.size(); ++j) {C[i + j] += A[i] * B[j];  // 累加到对应的位置}}// 处理进位int carry = 0;for (size_t i = 0; i < C.size(); ++i) {C[i] += carry;carry = C[i] / 10;C[i] %= 10;}// 移除前导0while (C.size() > 1 && C.back() == 0) {C.pop_back();}return C;
}int main()
{// 请在此输入您的代码string a;string b;cin>>a;cin>>b;vector<int> A,B,add_C,sub_C,mul_C;for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');add_C = add(A,B);bool flag = false;if(cmp(A,B)) sub_C = sub(A,B);else{flag = true;sub_C = sub(B,A);}sub_C = sub(A,B);mul_C = mul(add_C,sub_C);if(flag) cout<<"-";for(int i=mul_C.size()-1;i>=0;i--) cout<<mul_C[i];return 0;
}

4.更小的数

题目链接：0更小的数 - 蓝桥云课 (lanqiao.cn)

思路：双层循环遍历所有情况，外层枚举起点，内层枚举终点，查看反转当前字符串能否使得结果更小。

#include<bits/stdc++.h>
using namespace std;
int seek(string s,int i,int j){if(j-i<3) return 0;if(s[i+1]>s[j-1]) return 1;else if(s[i+1]==s[j-1]) return seek(s,i+1,j-1);else return 0;
}
int main()
{// 请在此输入您的代码string s;cin>>s;int n = s.size();int ans = 0;for(int i=0;i<=n-2;i++){for(int j=i+1;j<=n-1;j++){if(s[i] > s[j]) ans++;if(s[i] == s[j]) ans += seek(s,i,j);}}cout<<ans<<endl;return 0;
}

5.颜色平衡树

题目链接：0颜色平衡树 - 蓝桥云课 (lanqiao.cn)

考场上打死我也做不出来，略。

6.买瓜

题目链接：0买瓜 - 蓝桥云课 (lanqiao.cn)

思路：dfs，枚举三种情况，不选当前瓜，选当前瓜的一半，选当前瓜。代码妙在将需要求的目标和每个瓜的值先乘2，免去了整除的尴尬。还使用了倒着的前缀和来剪枝。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,ans = 50;
ll m,a[50],sum[50];
void dfs(ll S,int i,int cnt){if(cnt>=ans) return;if(S==m) ans = cnt;if(i>n||S>m||S+sum[i]<m) return;dfs(S,i+1,cnt);dfs(S+a[i],i+1,cnt);dfs(S+a[i]/2,i+1,cnt+1);
}
int main(){cin>>n>>m;m<<=1;for(int i=0;i<n;i++){cin>>a[i];a[i]>>=1;}sort(a,a+n,greater<>());for(int i=n-1;i>=0;i--){sum[i] = sum[i+1] + a[i];}dfs(0,0,0);if(ans==50){cout<<-1<<endl;}else{cout<<ans<<endl;}return 0;
}

7.网络稳定性

题目链接：0网络稳定性 - 蓝桥云课 (lanqiao.cn)

什么是LCA，不会。

8.异或和之和

题目链接：0异或和之和 - 蓝桥云课 (lanqiao.cn)

完全不会啊。

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], cnt[25][5], n; //cnt[i][j]: 第i位j的个数
long long ans;int main()
{scanf("%d", &n);for(int i = 1; i <= n; i++){scanf("%d", &a[i]);//异或前缀和a[i] ^= a[i - 1];}//[i, j]的异或和 = a[j] ^ a[i - 1]，因为 a ^ b = c，a ^ c = bfor(int i = 1; i <= n; i++)for(int j = i; j <= n; j++)ans += a[j] ^ a[i - 1];//下面就是优化这个步骤// //遍历二进位每一位// for(int i = 0; i <= 20; i++)//   //遍历每一个数，j=0就是左右区间相等的情况//   for(int j = 0; j <= n; j++)//     cnt[i][(a[j] >> i) & 1]++;// //乘法原理，把所有情况乘起来// for(int i = 0; i <= 20; i++){//   ans += (long long)cnt[i][0] * cnt[i][1] * (1 << i);// }printf("%lld", ans);return 0;
}

9.像素放置

题目链接：0像素放置 - 蓝桥云课 (lanqiao.cn)

极少的能看懂的代码。

#include<bits/stdc++.h>
using namespace std;
int f[12][12];
char d[12][12];
int n,m;
bool check(int x,int y){if(d[x][y]=='_') return true;int cnt = 0;for(int i=-1;i<=1;i++){for(int j=-1;j<=1;j++){cnt+=f[x+i][y+j];}}if(cnt==d[x][y]-'0')return true;return false;
}
void dfs(int x,int y){if(x==n+1){for(int y=1;y<=m;y++){if(!check(n,y))return;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cout<<f[i][j];}cout<<endl;}return;}if(y==m){f[x][y] = 0;if(x==1 || (y==1 && check(x-1,y)) || (check(x-1,y-1) && check(x-1,y)))dfs(x+1,1);f[x][y] = 1;if(x==1 || (y==1 && check(x-1,y)) || (check(x-1,y-1) && check(x-1,y)))dfs(x+1,1);}else{f[x][y] = 0;if(x==1 || y==1 || check(x-1,y-1))dfs(x,y+1);f[x][y] = 1;if(x==1 || y==1 || check(x-1,y-1))dfs(x,y+1);}
}
int main()
{// 请在此输入您的代码cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>d[i][j];}}dfs(1,1);return 0;
}

10.翻转硬币

题目链接：0翻转硬币 - 蓝桥云课 (lanqiao.cn)

完全不会。