第十五届蓝桥杯----B组cpp----真题解析(小白版本)

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

必看前言！！！！！

今天来解析一波蓝桥杯真题，我会用我自己小白的视角去解析每一道题，都是自己的亲身写题过程
以下题目少部分顺序不是官方比赛顺序，我会进行标注
注意！！！： 题目如果需要某些算法和知识点，我会提前标注出来，请先学习后再看我的题解，我不会讲解此知识点！！！！！！

题目肯定会有多种解答，以下思路仅为个人思路，有更好的思路的话请沿用自己的思路，本人题解思路仅供参考！！！！

一、试题A：握手问题

1.题意分析

这题我们直接暴力解答就行，因为只需要提交一个答案，相当于没有时间限制
所以我们怎么暴力怎么来

我们直接暴力for遍历每一个人能够与哪些人握手,但这题有个关键点
注意 A 和 B 握手的同时也意味着 B 和 A 握手了，所以算作是一次握手
所以意味着我们在用两个for遍历的时候，第二层for起点必须是第一层for的下一个人

2.代码解答

#include<iostream>
using namespace std;
int ans=0;//总共握手多少次
int main()
{for(int i=8;i<50;i++)//从第八个人开始 每个人都能与其他人握手{for(int j=i+1;j<=50;j++){ans++;}}ans+=7*43;//这七个人可以分别与另外43个人握一次手cout<<ans;return 0;
}

第一层for表示的是每个人，我们从第8个人开始，这是因为有7个人是不能相互握手的，所以我们先不统计他们的握手次数，注意，第一层for不能遍历到最后一个人，因为前面所有人与最后一人握手，导致最后一人的握手情况已经加了一次了

最后我们直接统计这7个人的握手情况就行，因为这7个人分别能与剩下的43人握手，所以直接7*43

二、试题B：小球反弹

1.题意分析

我当时这题也没写出来，现在我们一起来分析一下思路，其实这题不难
我们先假设，如果是一个正方形，并且以45°角出发，第一次碰到边界中点
那么第一次回到左上角应该是这样的运动轨迹
红色表示出发，绿色表示返回的形成

-------------------------紫色d-------蓝色d
此时的总路程为（d+d）+(d+d)=4d 一来一回
那么如果我们把这个正方形一直延展呢？
是不是会变成这样
红色还是表示第一张图的出发路径，绿色表示返回的路径

是不是 恍然大悟？我们并不需要一直反弹，我们只需要一直向下走，直到到达右下角就行！！！！！那么这里的 总路程为 （d+d）+(d+d)=4d

那么现在问题转换为什么时候会到达右下角？
题目中说了dx与dy的速率之比为15:17
然后知道速率之比为15:17 那么路程之比dx:dy也为15：17
所以我们这里暴力枚举就行，没一秒，dx走15，dy走17，什么时候同时满足dx可以整除343710和dy可以整除233333的时候，就到达了右下角

但是还有一个最重要的关键点别忘记了！！！
我们这里求的路程出发的时候是d要变成2d，返回的路径为d，也要变成2d

2.代码解答

#include<iostream>
#include<algorithm>
#include<iomanip>
using namespace std;
typedef long long ll;
ll dx=0;
ll dy=0;
long double sum=0;
int main()
{while(1){dx+=15;dy+=17;if(dx%343720==0&&dy%233333==0)break;}cout << setprecision(2) << fixed <<sqrt(2*dy*2*dy+2*dx*2*dx);return 0;
}

3.关键点分析

关于最后的dy变成2倍，dx变成2倍，可能有人不理解
因为我们现在求出来的dx和dy是总路程为2d的时候的dx和dy，但总路程是4d不是2d，当斜边*2以后，两条直角边都要 *2
那我就画个图来表示一下

到这我们就成功拿下两道填空题啦！！！！鼓掌！

三、试题C：好数

1.注意事项！

当我们拿到一道非填空题的时候，首先看题，其次最重要的就是看这个评测用例规模与约定
总结为一句话
当你的程序在保证对的情况下并且使用c++打竞赛，如果到达10的8次方的复杂度，此程序可能会超时
那么当到达10的9次方的时候，此程序必超时

2.题意分析

其实也没啥好分析的，题目已经说的很简单了，就一个个奇偶判断就行，下面我直接上代码

3.代码解答

#include<iostream>
#include<algorithm>
using namespace std;
int n;
int ans=0;//记录好数的个数bool check(int num)
{bool flag=1;//奇数为真  偶数维假//我们一开始将flag设置为真while(num!=0)//依次遍历num的每一位数{int t=num%10;num/=10;//将这一位丢弃//当奇数位的数为偶数if(flag&&t%2==0)return false;//当偶数位的数为奇数if(!flag&&t%2!=0)return false;flag=!flag;//更新}return true;//前面都没有返回false  说明是好数 直接return true
}int main()
{cin>>n;for(int i=1;i<=n;i++){if(check(i)){ans++;}}cout<<ans;return 0;
}

四、试题D：R格式

1.备注！！！！

这题说白了就是一个高精度*单精度的板子题目，看我的这篇题解前请先学会此知识点！

2.题意分析

这里意思就是给一个浮点数d，然后让这个d去乘n个2，然后得到一个四舍五入的整数，这就是题目要我们做的事情，但我们看评测范围，n最大有1000，那我请问你，2的1000次方，long long能装的下吗？？？？？显然不能啊，单从这点我们就可以立马想到，要用高精度，既然要用高精度，是不是要用字符串呢？？？

这题我们可以用高精度*高精度，就是用字符串表示2的n次方，然后用字符串表示这个d，但完全没必要！！！！！！
我们直接用高精度*单精度即可，第一因为简单一点，第二也不会超时，因为最多就1000个2，每次让d*2，也就1000次，根本不会超时

3.个人思路解析

首先将浮点数d用字符串存储，然后将字符串反转后存入数组中(如果这里要问为什么反转存入，说明你没懂高精度乘法，回去学完再往下看)
然后用for依次高精度*2
用一个dex记录小数点的位置，这样在最后四舍五入的时候就只判断小数点后的那位数就行
大致思路就这样
主要注意点就是len长度的更新还有进位
下面我直接上代码，我在代码中每一步都做了详细说明

4.代码解答

#include<iostream>
#include<algorithm>
using namespace std;
int n,arr[1000005],len,dex;//len是当前数的总长度  dex记录小数点位置
string d;void kkkk()
{for(int i=1;i<=len;i++)//注意这里是 <=len 注意细节噢{//每一位依次*2arr[i]*=2;}//考虑进位for(int i=1;i<=len;i++)//注意这里是 <=len 注意细节噢{arr[i+1]+=arr[i]/10;arr[i]%=10;}if(arr[len+1])//一开始这个值是0 因为我们是全局变量默认为0 如果不是0说明进位导致位数变大{len++;//所以要更新长度}
}int main()
{cin>>n>>d;//将字符串反转  便于存入arr数组中进行高精度乘法reverse(d.begin(),d.end());dex=d.find('.');//此时dex下标为小数点的下标位置 但需要注意的是此下标是从0开始数的d.erase(dex,1);//将小数点删除  便于存入arr中//dex++;//将其转换为下标从1开始数的小数点的位置len=d.size();//此时已经把小数点删除，这个长度就是整个数的长度//存入arr数组中  前面已经反转过了 相当于这里就是倒序存入for(int i=0;i<len;i++){arr[i+1]=d[i]-'0';}for(int i=1;i<=n;i++){kkkk();//高精度乘法 每次乘2}//此时已经乘完了所有2 但我们还需要判断一次进位 因为题目说的是输出四舍五入后的整数//这里我们只要判断小数点后第一位数是否大于等于5就可以了if(arr[dex]>=5){arr[dex+1]++;}//进位更新for(int i=dex+1;i<=len;i++){arr[i+1]+=arr[i]/10;arr[i]%=10;}//查看长度是否变化if(arr[len+1]){len++;}//输出整数部分for(int i=len;i>dex;i--){cout<<arr[i];}return 0;
}

五、试题F：数字接龙

1.备注！！！！

这题需要dfs的知识，需要刷过类似于走迷宫的题目，请了解后再看题解，题解不会详细对此知识点进行教程

2.题意分析

这题当时我第一次提交是过了75%，个人感觉这题就是迷宫的简单题 但是关键点就是这个路径不能交叉，然后题意很明确，题目中把每个条件都列出来了，所以就不需要再将复杂题意翻译为简单题意了

3.个人思路解析

首先大致思路就是走迷宫 用dfs 因为结合题意，并且看到地图最大为10*10，我们直接上dfs 并且不需要剪枝，也不需要记忆化搜索，这么小直接暴力就行，第一个条件就是从起点到终点，这个不需要多少，第二个条件我们设置一个值next就行，表示下一个需要搜寻的值，第三个条件我们一开始设置一个初始ans=1，然后到搜满的时候，判断这个ans是否等于地图方块总数的时候就行，第四个条件是最关键的点就是不能交叉，大家仔细想一下，怎么样会导致交叉，是不是只有斜着走的时候呢？？？？，因为路线不能重复走，所以如果上下左右走的话就不可能导致交叉，那么斜着走会导致交叉，所以这个关键点就被我们抓住了

我这里单独开一个xvis四维度的一个数组bool xvis[15][15][15][15];//对于走斜线进行标记 从位置i j到 位置 k l 表示 (i,j) 这个坐标到 (k,l) 这个坐标，这条路线走过，我画个图打个比方

(i,j)到(k,l)这个路线被走过了，大家觉得我还能这样斜着从A到B吗？
显然是不能的，因为已经走过了，但是这里也有一个关键点！！ 我们将
xvis[i][j][k][l]变为1的时候，虽然表示的是从(i,k)到(k,l)这条路走过，但是不是也要将xvis[k][l][i][j]变为1，表示从(k,l)到(i,j)这条路走过，大家想一下是不是这个道理？？？？？？？？

题目中还有一个关键点，就是要我们找到这条路径的时候，按字典序输出！
这个其实很简单，因为题目中把每个方向表示的顺序告诉了我们，我们在遍历方向的时候，按从小到大的顺序遍历即可

到此为止我们把所有条件都翻译出来了，下面我们直接上代码！！！！

5.代码解答

#include<iostream>
#include<vector>
using namespace std;
int n,m,mp[15][15],ans=1;//ans表示走过多少格子 当走过格子数==总格子数 说明全部格子都经过了
bool vis[15][15];//标记此路线是否走过
bool xvis[15][15][15][15];//对于走斜线进行标记  从位置i j到 位置 k l
bool flag=0;//查看最终是否找到一条合适的线路
vector<int>path;//存储路线
//按照图例给的顺序进行此顺序的遍历方向
int dx[]={-1,-1,0,1,1,1,0,-1};
int dy[]={0,1,1,1,0,-1,-1,-1};
int p[]={0,1,2,3,4,5,6,7};//每个方向路线代表的数字void dfs(int x,int y,int next)
{if(next==m)next=0;//重置if(x==n-1&&y==n-1)//到达终点 {if(ans==n*n&&!flag)//成功走满所有格子 并且还没有找到一条路线{for(int i=0;i<path.size();i++){cout<<path[i];}flag=1;}return;}//依次搜寻每一条方向for(int i=0;i<8;i++){int xx=x+dx[i];int yy=y+dy[i];if(xx<0||yy<0||xx>=n||yy>=n)continue;//越界if(mp[xx][yy]!=next)continue;//不是正确的格子if(vis[xx][yy])continue;//走过了//只有斜着走会导致相交 这里我们判断一下即可if(i==1)//向右上角走 所以要判断上面和右边的路线是否斜着走过{if(xvis[x][y+1][x-1][y]||xvis[x-1][y][x][y+1])continue;}else if(i==3)//向右下角走 所以要判断右侧和下面这个路径是否走过{if(xvis[x][y+1][x+1][y]||xvis[x+1][y][x][y+1])continue;}else if(i==5)//向左下角走  所以要判断左侧和下面这个路径是否走过{if(xvis[x][y-1][x+1][y]||xvis[x+1][y][x][y-1])continue;}else if(i==7)//向左上角走  所以要判断左侧和上面这个路径是否走过{if(xvis[x-1][y][x][y-1]||xvis[x][y-1][x-1][y])continue;}//全部排除完后 这一步可以走if(i==1||i==3||i==5||i==7)//更新斜线{xvis[x][y][xx][yy]=1;xvis[xx][yy][x][y]=1;}vis[xx][yy]=1;//更新标记path.push_back(p[i]);//压入路径ans++;dfs(xx,yy,next+1);ans--;vis[xx][yy]=0;//重置标记path.pop_back();//重置路径//重置斜线if(i==1||i==3||i==5||i==7)//更新斜线{xvis[x][y][xx][yy]=0;xvis[xx][yy][x][y]=0;}}}int main()
{cin>>n>>m;//输入地图大小和Kfor(int i=0;i<n;i++){for(int j=0;j<n;j++){cin>>mp[i][j];//给地图填数}}vis[0][0]=1;//起点走过dfs(0,0,1);//初始位置 下一个位置要找1 if(!flag){cout<<"-1";}return 0;
}

六、试题H：拔河(原省赛最后一题)

1.备注

虽然这题是省赛最后一题并且在洛谷为绿题，但个人觉得这题比那个宝石组合要简单，可能由于我数学比较差并且正好最近又学了一下双指针优化，所以宝石组合那道题对于我来说比较难，我放到最后讲

2.题目

3.知识点说明

此题需要用到 前缀和+双指针进行优化，请大家先学习后再看此题解，关于双指针我之前发了一篇讲解，请大家可以点击这进行学习双指针(滑动窗口)学习！！！

4.思路分析

首先我们分析题意将题目翻译为人话就是给你一条很长的数组，然后分别选两条连续的子数组，这两条子数组不能重叠，然后让这两个子数组的差最小，大概就是这么个意思

Question1：为什么会想到前缀和？
因为我们发现，如果我们找到了两个数组，那我们需要分别求出两个数组的和，然后进行差运算，既然要求一段数组的和，我们自然就想到了前缀和

Question2：为什么会想到用双指针优化？
前面我们想到了用前缀和来记录前n个数组的长度，我一开始的思路是，用for去遍历，找到第一组队伍的起点和终点，然后用for去遍历，找到第二组队伍的起点和终点，就像这样

for(int i=1;i<n;i++)//找到第一支队伍的起点i
{for(int j=i;j<n;j++)//找到第一支队伍的终点j{for(int k=j+1;k<=n;k++)//找到第二支队伍的起点k{for(int h=k;h<=n;h++)//找到第二支队伍的终点h{}}}
}

但我们此时再看数据，n最大是10的3次方，这里四个for就到达了10的12次方了，还没算其他判断的程序
此时我们就能想到用双指针来优化（本人恰好也只会这个来优化）
我们只用两个for去判断第一个队伍的起点和终点，然后用双指针来判断第二个队伍的起点和终点，使得复杂度大大降低！
关于如何用双指针请看我之前发的，如果你此时有这样的疑惑，说明没学过或者没学懂双指针，请先去学习
下面我们直接上代码！！！

5.代码解答

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll n,arr[1005],pre[1005],minn=1e10;int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>arr[i];pre[i]=pre[i-1]+arr[i];}for(int i=1;i<n;i++)//第一组起点{for(int j=i;j<n;j++)//第一组终点{ll sum1=pre[j]-pre[i-1];int left=j+1;//第二组起点int right=j+1;//第二组终点while(right<=n&&left<=right)//双指针枚举起点和终点{ll sum2=pre[right]-pre[left-1];ll t=abs(sum1-sum2);if(t<minn)minn=t;//更新if(sum2<sum1&&right<n)//拓宽{right++;}else if(sum2>sum1&&left<right){left++;}else {if(right<n){right++;if(left<right)left++;}else{break;}}}}}cout<<minn;return 0;
}

6.注意点

个人感觉双指针最容易错的地方就是在边界的时候怎么去移动，要根据题目去判断，这个点如果写错，特别陷入死循环，我经常出错，还是练少了

七、试题E: 宝石组合

后续更新… . . … . . . . . . . . . … . .

八、试题G: 爬山

此题有争议，这题不讲！！！！！！

总结

祝各位佬统统拿奖！！！！！！！！！