【蓝桥备赛冲刺】2022年第十三届省赛模拟题题解C/C++

食用该篇博客前须知:

(0)第一次写博客，如有地方处理不好请见谅，后续会不断提高自己的写博客能力。

(1)在头文件处偷了懒，使用的都是万能头文件。（最好还是自己要记住常用头文件

(2)使用的是C++，如果是使用其他语言的同学，希望你们也能从中获取一定的思路

(3)博主本人也是处于备赛阶段，所以近几年的题解后续也会不断放出。

(4)该场模拟赛官方并没对题目名字做出限定，所以题名都是自己改编

目录

A题:找有多少个A

B题:最二数字

C题:变换为一

D题:螺旋矩阵

E题:结点深度

F题:和尚挑水

G题:金额表示

H题:插板插头

I题:约数个数

J题:汉诺塔游戏

A题:找有多少个A

问题描述

以下是一个 25 行 25 列的字母矩阵，全部由字母 A 和 B 组成。AAAAAAABABBAABABABAAAAAAAABBBBBABBAABBBBBABABBBBBAABAAABABBBABAABBBBABAAABAABAAABABBBBBAABAABABAAABAABAAABABBABABBABABABAAABAABBBBBABBBABAABBBBABBBBBAAAAAAAABABABABABABAAAAAAABBBBBBBBABAABABBBBBBBBBBBAABAABABBAAABBAAABABBBBBAABBABABBBABBAAAABBBBAAAABBBBBAAABABAABABAABBBAABBABBAABABABAAAABBBAABBAAAAAABABBBABAABAABABABABBBBBAAAAABBBBBABBBBAAABBBABBABAABAABAAABAAABAABABABAAAAABBBBBBBBABABBBBABAABBABAABBBAAABAAABBBAAAAAAABAABBBBBBBBBABBAAABAABBBABBABAAAAAAABBAAABBBBABABAABBAABBBBBABBAABABAAABBBABBAAABAAABABABBBAAAAAAAAAABAAABAAABABABABBBABBAABBABAAABAAABABBABBABABAABAABAAAABBBBBABABBBBBABBAAAABAAAAAAAAAABAABBBAABABABBABBA1

思路分析

暴力枚举，因为是填空题，可以手动在最后加一个1用来判断输入结束

题目代码

#include //万能头 using namespace std;int main(){    char t;    int res=0;    while(1)    {    cin>>t;    if(t=='A')    res++;    if(t=='1')//遇到手动添加的1就退出     break;    }cout<<res;}

题目答案

318

B题:最二数字

问题描述

如果一个整数的某个数位包含 2 ，则称这个数为一个“最2数字”。例如：102、2021 都是最2数字。请问在 1（含） 到 2021（含） 中，有多少个最2数字。

思路分析

进行枚举，然后拆数判断是否含2

题目代码

#include using namespace std;bool check(int x)//拆数判断{while(x){int t=x%10;if(t==2) return true;x/=10;}return false;}int main(){int res=0;for(int i=1;i<=2021;i++)//枚举if(check(i))res++;cout<<res;return 0;} 

题目答案

564

C题:变换为一

问题描述

有一个整数 A=2021，每一次，可以将这个数加 1 、减 1 或除以 2。其中除以 2 必须在数是偶数的时候才允许。例如，2021 经过一次操作可以变成 2020、2022。再如，2022 经过一次操作可以变成 2021、2023 或 1011。请问，2021 最少经过多少次操作可以变成 1。

思路分析

第一眼看到“最少”这个关键字，想到了二分、贪心、dp。初次尝试是贪心，认为肯定除2在可选集合中肯定优先级最高，然后减一可能更好，因为离1更近了，后面验证了一下，分别单独进行了＋1，-1操作。＋1需要15次操作，-1需要17次操作。后面猜想如果有时候+1，有时候-1是不是更好呢？所以贪心的想法在此失败（我不会贪了，hh）。后面使用了动态规划。

状态表示:f[i]代表所有方案中操作i所需要的最少操作次数

状态计算:子结构划分为i为偶数或奇数

f[i]=min ( f[i/2]+1 , min( f[(i-1)/2] , f[(i+1)/2] )+2)

题目代码(DP)

#include using namespace std;int f[2050];int main(){f[1]=0;//当i为1的时候不需要操作for(int i=2;i<=2021;i++){if(i%2==0)//偶数f[i]=f[i/2]+1;else//奇数f[i]=min(f[(i+1)/2],f[(i-1)/2])+2;}cout<<f[2021];return 0;}

题目代码(贪心)

#include using namespace std;int main(){int res=0;int n=2021;while(n!=1){if(n%2==0)//如果是偶数，直接除2{res++;n/=2;}if(n%10==3||n%10==7)//如果个位是3,7加1操作更好，加1之后变成4，8下降速度更快{n+=1;res++;} //这里要特别注意一下个位是1的情况，如果当n=1的时候这里会-1变成0，出不了循环if((n%10==1&&n>10)||n%10==5||n%10==9){n-=1;res++;}}cout<<res;return 0;} 

题目答案

14

D题:螺旋矩阵

问题描述

对于一个 n 行 m 列的表格，我们可以使用螺旋的方式给表格依次填上正整数。我们称填好的表格为一个螺旋矩阵。例如，一个 4 行 5 列的螺旋矩阵如下：1 2 3 4 514 15 16 17 613 20 19 18 712 11 10 9 8请问，一个 30 行 30 列的螺旋矩阵，第 20 行第 20 列的值是多少？

思路分析

这里将使用一种非常棒的螺旋数组实现方式，不再是传统的循环套循环，而是以dfs的思想+巧妙的判断条件

题目代码

#include using namespace std;int f[500][500];int d[5][3]={{0,1},{1,0},{0,-1},{-1,0}};//偏移量 int main(){    int n,m;    cin>>n>>m;    int x=1,y=1,ori=0;//ori用来记载当前走的方向     for(int i=1;in||t2>m||t1<=0||t2<=0||f[t1][t2])ori=(ori+1)%4; f[x][y]=i; x+=d[ori][0]; y+=d[ori][1];    }    for(int i=1;i<=n;i++)    { for(int j=1;j<=m;j++)     printf("%d ",f[i][j]); puts("");    }    return 0;}

题目答案

819

E题:结点深度

问题描述

一棵二叉树有2021个结点。该树满足任意结点的左子树结点个数和右子树的结点个数之差最多为1。定义根结点的深度为0，子结点的深度比父结点深度多1。请问，树中深度最大的结点的深度最大可能是多少？

思路分析

根据题目给出的性质”任意结点的左子树结点个数和右子树的结点个数之差最多为1“。

在草稿纸上画出这棵树，当然也可以直接使用公式计算，不过我还是喜欢画图，可能毕竟清晰明了

图画

比较懒，hh，所以没有继续画下去，读者可以自己试一试

题目答案

10

F题:和尚挑水

问题描述

问题描述一个和尚要挑水，每次最多能挑 a 千克，水缸最多能装 t 千克，开始时水缸为空。请问这个和尚最少要挑多少次可以将水缸装满？输入格式：输入一行包含两个整数 a, t，用一个空格分隔。输出格式：输出一行包含一个整数，表示答案。样例输入20 2021样例输出102评测用例规模与约定对于所有评测用例，1 <= a <= 100，1 <= t <= 10000。

思路分析

简单的模拟过程

题目代码

#include using namespace std;int main(){int a,t;cin>>a>>t;int res=0;int ans=0;while(ans<t)//还没装满或还没装的溢出{ans+=a;res++;}cout<<res;return 0;}

G题:金额表示

问题描述

问题描述在金融领域，通常将金额的百位和千位之间、十万位和百万位之间增加逗号（千分位分隔符）。以方便阅读。一般从个位开始，每三位之前增加一个逗号。例如：1234567890.00 通常写成 1,234,567,890.00。注意小数点后固定保留 2 位。给定一个包含千分位分隔符的数值，请读入后输出对应的不含千分位的数值，小数点仍然保留 2 位。输入格式输入一行包含一个由千分位分隔符的数值，恰好有 2 位小数。输出格式输出不含千分位分隔符的数值，保留 2 位小数。样例输入1,234,567,890.00样例输出1234567890.00评测用例规模与约定对于所有评测用例，给定的数值整数部分不超过12位。

思路分析

涉及到这种字符串处理的题目，嘟嘟嘟建议大家多掌握一些字符串的处理函数和字符串类型，常用的可能是scanf，string了，不要小看它，“格式化输入”面对一些类似题可是利器，保你嘎嘎乱杀

题目代码

#include using namespace std;int main(){string a;cin>>a;    //分段处理for(int i=0;i<a.size()-3;i++)//先处理小数点前面的数if(a[i]!=',') cout<<a[i];for(int i=a.size()-3;i<a.size();i++)//单独处理小数点及其后面的数cout<<a[i];return 0;}

H题:插板插头

问题描述

小蓝有一个插板，形状用一个 n * m 的01矩阵表示，0 表示板面，1 表示插孔。小蓝还有一个插头，形状用一个 r * c 的01矩阵表示。0 表示没有伸出的部分，1 表示伸出的部分。插头伸出的部分必须插在插孔里面。为了安全，插头插到面板上不能有任何部分超过插板边界（包括没有伸出的部分）。插头和插板都不能旋转，也不能翻转。请求出插头插入插板的合理位置。输入格式    输入的第一行包含两个整数 n, m。    接下来 n 行，每行一个长度为 m 的01串，表示插板的形状。    接下来一行包含两个整数 r, c。    接下来 r 行，每行一个长度为 c 的01串，表示插头的形状。输出格式　　如果插头没办法安全插入插板中，输出“NO”。否则输出两个数 a, b，表示插头的第 1 行第 1 列对应插板的第 a 行第 b 列。如果有多种情况满足要求，输出 a 最小的方案。如果 a 最小的方案有多个，输出在 a 最小的前提下 b 最小的方案。样例输入3 40110000000003 3000010000样例输出NO样例说明在插头不超出范围的前提下无法插入。样例输入4 711101001101111000111100000112 3111011样例输出2 4评测用例规模与约定对于 50% 的评测用例，2 <= n, m, r, c <= 20。对于所有评测用例，2 <= n, m, r, c <= 100。

思路分析

数据范围比较小，完全可以采用暴力枚举的方式，遍历所有方案。这里使用了一种不错的方法，即偏移量。巧妙的枚举每一种拼接方案

题目代码

#include using namespace std;char t1[110][110];//插板char t2[110][110];//插头typedef pair PII;vector res;bool cmp(PII a,PII b)//排序函数{if(a.first!=b.first)return a.first<b.first;elsereturn a.second>n>>m;for(int i=1;i<=n;i++)for(int j=1;j>t1[i][j];cin>>r>>c;for(int i=1;i<=r;i++)for(int j=1;j>t2[i][j];for(int dx=0;dx<=n-r;dx++)//枚举x的偏移量for(int dy=0;dy<=m-c;dy++)//枚举y的偏移量{int flag=0;//标记该种对接方案是否可行for(int i=1;i<=r;i++){for(int j=1;j<=c;j++){if(t2[i][j]=='1'&&t2[i][j]!=t1[i+dx][j+dy]) {flag=1;}}}if(!flag) res.push_back({1+dx,1+dy});//将可以方案对应的坐标储存}if(!res.size()) printf("NO\n");else if(res.size()==1) printf("%d %d",res[0].first,res[0].second);else{sort(res.begin(),res.end(),cmp);printf("%d %d",res[0].first,res[0].second);}return 0;}

给定正整数 a, b, c，请问有多少个正整数，是其中至少两个数的约数。输入格式输入一行包含三个正整数 a, b, c。输出格式输出一行包含一个整数，表示答案。样例输入30 70 35样例输出6样例说明1、2、5、7、10、35满足条件。评测用例规模与约定对于 50% 的评测用例，1 <= a, b, c <= 1000000。对于所有评测用例，a, b, c 不超过 10**12（10的12次方）。

#include using namespace std;typedef long long ll;vector t1,t2,t3;int main(){ll a,b,c;//会爆int，得用1ong longcin>>a>>b>>c;for(int i=1;i<=a/i;i++)//求解三个数的约数，这里其实不用写三个，完全可以封装一个函数if(a%i==0){t1.push_back(i);if(a/i!=i) t1.push_back(a/i);}for(int i=1;i<=b/i;i++)if(b%i==0){t2.push_back(i);if(b/i!=i) t2.push_back(b/i);}for(int i=1;i<=c/i;i++)if(c%i==0){t3.push_back(i);if(c/i!=i) t3.push_back(c/i);}vector res;for(auto q1:t1)for(auto q2:t2)for(auto q3:t3){if(q1==q2)res.push_back(q1);if(q2==q3)res.push_back(q2);if(q1==q3)res.push_back(q3);}sort(res.begin(),res.end());    //这里需要去重,因为上面写的判断条件将会把一些重复的数装进res容器里res.erase(unique(res.begin(),res.end()),res.end());cout<<res.size();return 0;}

小蓝很喜欢玩汉诺塔游戏。游戏中有三根柱子，开始时第一根柱子上有 n 个圆盘，从上到下圆盘的大小依次为 1 到 n。每次，可以将一个盘子从一根柱子上移动到另一根柱子上，这个盘子必须是柱子最上方的盘子，而且移到的柱子上的盘子必须比这个盘子大。小蓝的目标是将所有的盘子移动到第三根柱子上。汉诺塔是个经典问题，当盘子数量为 n 时，最少需要移动 2**n-1 步，其中 2**n 表示 2 的 n 次方。小蓝已经玩了一会儿（不一定按最优方案玩），他想知道，对于他目前的局面，最少还需要多少步可以到达目标。输入格式输入的第一行包含三个非负整数 a, b, c，分别表示目前每根柱子上的盘子数。在本题中，n=a+b+c。第二行包含 a 个整数，相邻的整数之间使用一个空格分隔，表示第一根柱子上的盘子，盘子按从上到下（从小到大）的顺序给出。第三行包含 b 个整数，相邻的整数之间使用一个空格分隔，表示第二根柱子上的盘子，盘子按从上到下（从小到大）的顺序给出。第四行包含 c 个整数，相邻的整数之间使用一个空格分隔，表示第三根柱子上的盘子，盘子按从上到下（从小到大）的顺序给出。输出格式输出一行包含一个整数，表示答案。样例输入1 2 312 34 5 6样例输出7评测用例规模与约定对于 30% 的评测用例，2 <= n <= 5。对于所有评测用例，2 <= n <= 60。