2023年第十四届蓝桥杯大赛软件类省赛C/C++大学A组真题

2023年第十四届蓝桥杯大赛软件类省赛C/C++大学A组部分真题和题解分享

文章目录 蓝桥杯2023年第十四届省赛真题-平方差思路题解 蓝桥杯2023年第十四届省赛真题-更小的数思路题解 蓝桥杯2023年第十四届省赛真题-颜色平衡树思路题解 蓝桥杯2023年第十四届省赛真题-买瓜思路题解

蓝桥杯2023年第十四届省赛真题-平方差

题目描述 给定 L, R，问 L ≤ x ≤ R 中有多少个数 x 满足存在整数 y,z 使得 x = y2 − z2。 输入格式 输入一行包含两个整数 L, R，用一个空格分隔。 输出格式 输出一行包含一个整数满足题目给定条件的 x 的数量。 样例输入 1 5 样例输出 4 提示 1 = 12 − 02 ； 3 = 22 − 12 ； 4 = 22 − 02 ； 5 = 32 − 22 。 对于 40% 的评测用例，LR ≤ 5000 ； 对于所有评测用例，1 ≤ L ≤ R ≤ 109 。

思路题解

解题思路:

规律：只有当x为奇数或4的倍数时才能拆分为两个数的平方差。 注意事项:刚开始用c++写循环的时候，有一个样例会超时，故进一步寻找规律：F(X)=x/4+(x+1)/2，该式代表不大于x的满足条件的数的个数，用F®-F(L-1)即为L-R之间（大于等于L，小于等于R）满足条件的数的个数。 #include<iostream> using namespace std; int F(int x) { return x / 4 + (x + 1) / 2;//不大于x的满足条件的数的个数 } int main() { int l = 0, r = 0; cin >> l >> r; cout << F(r)-F(l-1); return 0; } 蓝桥杯2023年第十四届省赛真题-更小的数

题目描述 输入格式 输入一行包含一个长度为 n 的字符串表示 num（仅包含数字字符 0 ∼ 9）， 从左至右下标依次为 0 ∼ n − 1。 输出格式 输出一行包含一个整数表示答案。 样例输入 210102 样例输出 8 提示 一共有 8 种不同的方案： 1）所选择的子串下标为 0 ∼ 1 ，反转后的 numnew = 120102 < 210102 ； 2）所选择的子串下标为 0 ∼ 2 ，反转后的 numnew = 012102 < 210102 ； 3）所选择的子串下标为 0 ∼ 3 ，反转后的 numnew = 101202 < 210102 ； 4）所选择的子串下标为 0 ∼ 4 ，反转后的 numnew = 010122 < 210102 ； 5）所选择的子串下标为 0 ∼ 5 ，反转后的 numnew = 201012 < 210102 ； 6）所选择的子串下标为 1 ∼ 2 ，反转后的 numnew = 201102 < 210102 ； 7）所选择的子串下标为 1 ∼ 4 ，反转后的 numnew = 201012 < 210102 ； 8）所选择的子串下标为 3 ∼ 4 ，反转后的 numnew = 210012 < 210102 ；

对于 20% 的评测用例，1 ≤ n ≤ 100 ； 对于 40% 的评测用例，1 ≤ n ≤ 1000 ； 对于所有评测用例，1 ≤ n ≤ 5000 。

思路题解

解题思路:

中心思想：s[l] > s[r]则满足条件，答案的个数+1。

详细解释：考虑s的所有子串[l,r], l即left，是子串的起始下标，r即right是子串的末尾下标，判断s[l] 和 s[r]的大小关系:

若s[l] > s[r]则该子串反转后，新串<原串，满足条件，答案数+1；

若s[l] = s[r]则将子串区间[l,r]缩小为[l+1,r-1],再判断s[l+1]和s[r-1]的大小关系；

若s[l] < s[r]则该子串反转后，新串>原串，不满足条件。

注意事项:

注意l和r的取值范围（详见代码注释）。 #include<iostream> #include<string> using namespace std; string s; int F(int l, int r) { while (l < r) { if (s[l] > s[r])return 1;//如果s[l] > s[r]，反转后满足条件 新字符串<原字符串。 else if (s[l] == s[r]) { l++;r--; }//如果s[l] == s[r]，两边同时缩小区间。 else break;//如果s[l] < s[r]，不用继续考虑，反转后一定不满足条件，直接退出循环 } return 0; } int main(){ cin >> s; int n = s.length();//n是字符串长度 int ans = 0;//记录答案 for (int l = 0;l <= n - 2;l++) {//l即left是子串的起始下标，从0开始到n-2（子串长度至少为2，最右侧的最小子串下标为[n-2,n-1],故l最多到n-2） for (int r = n - 1;r > l;r--) {//r即right是子串的末尾下标，从s的最末下标n-1到l+1。 if(F(l,r))ans++; } } cout << ans; return 0; } 蓝桥杯2023年第十四届省赛真题-颜色平衡树

题目描述 给定一棵树，结点由 1 至 n 编号，其中结点 1 是树根。树的每个点有一个颜色 Ci。 如果一棵树中存在的每种颜色的结点个数都相同，则我们称它是一棵颜色平衡树。 求出这棵树中有多少个子树是颜色平衡树。 输入格式 输入的第一行包含一个整数 n ，表示树的结点数。 接下来 n 行，每行包含两个整数 Ci , Fi，用一个空格分隔，表示第 i 个结点的颜色和父亲结点编号。 特别地，输入数据保证 F1 为 0 ，也即 1 号点没有父亲结点。保证输入数据是一棵树。 输出格式 输出一行包含一个整数表示答案。 样例输入 6 2 0 2 1 1 2 3 3 3 4 1 4 样例输出 4 提示 编号为 1, 3, 5, 6 的 4 个结点对应的子树为颜色平衡树。 对于 30% 的评测用例，n ≤ 200，Ci ≤ 200 ； 对于 60% 的评测用例，n ≤ 5000，Ci ≤ 5000 ； 对于所有评测用例，1 ≤ n ≤ 200000，1 ≤ Ci ≤ 200000，0 ≤ Fi < i 。

思路题解

思路：

要判断每个子树是否为平衡树，需要统计子树的每种颜色的节点的数量，并判断所有数量是否相等。

对于一颗树的根节点，若该树的所有子树的统计结果都得到了，就可以直接将子树的统计结果累加，并加上根节点的颜色。因此可以使用dfs对树进行搜索，在后序遍历位置得到子树的统计结果并累加，就可以计算出该树的统计结果，判断所有颜色数量是否相等即可。

注意：

统计结果cnt使用数组时，需要判断整颗树所有颜色的数量，而部分子树的颜色并不包含所有的颜色，每次判断的时间复杂度为O(num_c)，num_c为整棵树的颜色种数，这样会超时。因此可以使用map数据结构，这样每次只需判断子树所包含的颜色。 #include<iostream> #include<vector> #include<cstring> #include<map> using namespace std; const int N = 2e5+1; //最终结果 int ans=0; //将子树的计数结果cnt_nb累加到根节点的结果cnt上 void add(map<int,int>& cnt,map<int,int>& cnt_nb){ for(auto entry:cnt_nb){ int c=entry.first,count = entry.second; cnt[c] += count; } } /* 对树进行dfs搜索，树的根节点为i，并返回该子树的各节点颜色计数结果 */ map<int,int> dfs(vector<int>* g,int* c,int i){ int sz = g[i].size(); map<int,int> cnt; //记录子树的每个节点的各颜色节点的数量 /*如果为叶子节点，直接返回*/ if(sz==0){ cnt[c[i]] = 1; ans++; return cnt; } /*如果不是叶子节点*/ //将根节点的颜色加入cnt cnt[c[i]]=1; //遍历根节点的所有子树，并将子树的计数结果累加到cnt中 for(int j=0;j<sz;j++){ int nb = g[i][j]; map<int,int> cnt_nb = dfs(g,c,nb); add(cnt,cnt_nb); } //判断该子树的各种颜色节点的数量是否相等 int count = cnt[c[i]]; for(auto entry:cnt){ //存在一种颜色数量不等，直接返回 if(entry.second != count) return cnt; } //各颜色的数量相等，结果+1 ans++; //返回计数结果 return cnt; } int main() { int n; cin>>n; vector<int> g[N]; int c[N]; //每个节点的颜色 for(int i=0;i<n;i++){ int f; cin>>c[i]>>f; if(f>=1){ g[f-1].push_back(i); //记录节点f的子节点i（节点编号从0开始） } } dfs(g,c,0); cout<<ans; return 0; } 蓝桥杯2023年第十四届省赛真题-买瓜

题目描述 小蓝正在一个瓜摊上买瓜。瓜摊上共有 n 个瓜，每个瓜的重量为 Ai 。 小蓝刀功了得，他可以把任何瓜劈成完全等重的两份，不过每个瓜只能劈一刀。 小蓝希望买到的瓜的重量的和恰好为 m 。 请问小蓝至少要劈多少个瓜才能买到重量恰好为 m 的瓜。如果无论怎样小蓝都无法得到总重恰好为 m 的瓜，请输出 −1 。 输入格式 输入的第一行包含两个整数 n, m，用一个空格分隔，分别表示瓜的个数和小蓝想买到的瓜的总重量。 第二行包含 n 个整数 Ai，相邻整数之间使用一个空格分隔，分别表示每个瓜的重量。 输出格式 输出一行包含一个整数表示答案。 样例输入 3 10 1 3 13 样例输出 2 提示 对于 20% 的评测用例，∑n≤10； 对于 60% 的评测用例，∑n≤20； 对于所有评测用例，1 ≤n≤30，1≤ Ai ≤ 109 ，1 ≤ m ≤ 109

思路题解

对于每一个瓜有三种选择: 1)买整个瓜 2)买半个瓜，需要增加劈瓜次数 3)不买

则可以使用深度优先搜索解决, 对每个瓜的三种选择进行搜索, 解空间树是一颗完全三叉树, 时间复杂度为O(3^n), 肯定会超时, 故需要进行剪枝。

买半个瓜时需要将重量除2，会产生小数，故可以将重量数组都乘2，最大重量也乘2。

搜索时需要记录三个状态，当前层数pos，当前总重量sum，当前劈瓜的次数cnt，以下情况需要剪枝： 1）当前劈瓜次数大于已求得的最小次数，即cnt>ans 2）当前重量之和大于要求的重量，即sum>m

但是这样仍然会超时，还可以将重量数组降序排列，使得更快剪枝。还可以创建一个重量数组的后缀数组suf，这样在搜索时可以利用其剪枝：若当前重量加上剩余的所有瓜重量之和小于要求的重量，剪枝。

#include<iostream> #include<algorithm> using namespace std; const int N = 30; int INF = 100; int n,m; int v[N]; //重量数组 long suf[N+1]; //重量数组的后缀数组 int ans = INF; //将结果初始化为INF /* dfs搜索,参数分别表示当前层数,当前重量之和,切瓜的次数 */ void dfs(int pos,long sum,int cnt){ if(sum==m){ //找到了一个结果 ans = min(ans,cnt); return; } //剪枝 if(pos>=n || cnt>=ans || sum>m || sum+suf[pos]<m) return; //对三种选择进行搜索 dfs(pos+1,sum+v[pos],cnt); dfs(pos+1,sum+v[pos]/2,cnt+1); dfs(pos+1,sum,cnt); } int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin>>n>>m; m*=2; //总重量乘2 for(int i=0;i<n;i++) cin>>v[i],v[i]*=2; sort(v,v+n,greater<int>()); for(int i=n-1;i>=0;i--) suf[i] = suf[i+1]+v[i]; dfs(0,0,0); if(ans==INF) cout<<-1; else cout<<ans; return 0; }