许昌市做网站公司,交互式网站是什么意思,2022十大网络营销案例,河北大型网站建设提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 必看前言#xff01;#xff01;#xff01;#xff01;#xff01;一、试题A#xff1a;握手问题1.题意分析2.代码解答 二、试题B#xff1a;小球反弹1.题意… 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 必看前言一、试题A握手问题1.题意分析2.代码解答 二、试题B小球反弹1.题意分析2.代码解答3.关键点分析 三、试题C好数1.注意事项2.题意分析3.代码解答 四、试题DR格式1.备注2.题意分析3.个人思路解析4.代码解答 五、试题F数字接龙1.备注2.题意分析3.个人思路解析5.代码解答 六、试题H拔河(原省赛最后一题)1.备注2.题目3.知识点说明4.思路分析5.代码解答6.注意点 七、试题E: 宝石组合八、试题G: 爬山总结 必看前言
今天来解析一波蓝桥杯真题我会用我自己小白的视角去解析每一道题都是自己的亲身写题过程 以下题目少部分顺序不是官方比赛顺序我会进行标注 注意 题目如果需要某些算法和知识点我会提前标注出来请先学习后再看我的题解我不会讲解此知识点
题目肯定会有多种解答以下思路仅为个人思路有更好的思路的话请沿用自己的思路本人题解思路仅供参考
一、试题A握手问题 1.题意分析
这题我们直接暴力解答就行因为只需要提交一个答案相当于没有时间限制 所以我们怎么暴力怎么来
我们直接暴力for遍历每一个人能够与哪些人握手,但这题有个关键点 注意 A 和 B 握手的同时也意味着 B 和 A 握手了所以算作是一次握手 所以意味着我们在用两个for遍历的时候第二层for起点必须是第一层for的下一个人
2.代码解答
#includeiostream
using namespace std;
int ans0;//总共握手多少次
int main()
{for(int i8;i50;i)//从第八个人开始 每个人都能与其他人握手{for(int ji1;j50;j){ans;}}ans7*43;//这七个人可以分别与另外43个人握一次手coutans;return 0;
}第一层for表示的是每个人我们从第8个人开始这是因为有7个人是不能相互握手的所以我们先不统计他们的握手次数注意第一层for不能遍历到最后一个人因为前面所有人与最后一人握手导致最后一人的握手情况已经加了一次了
最后我们直接统计这7个人的握手情况就行因为这7个人分别能与剩下的43人握手所以直接7*43
二、试题B小球反弹 1.题意分析
我当时这题也没写出来现在我们一起来分析一下思路其实这题不难 我们先假设如果是一个正方形并且以45°角出发第一次碰到边界中点 那么第一次回到左上角应该是这样的运动轨迹 红色表示出发绿色表示返回的形成 -------------------------紫色d-------蓝色d 此时的总路程为dd(dd)4d 一来一回 那么如果我们把这个正方形一直延展呢 是不是会变成这样 红色还是表示第一张图的出发路径绿色表示返回的路径
是不是 恍然大悟我们并不需要一直反弹我们只需要一直向下走直到到达右下角就行那么这里的 总路程为 dd(dd)4d
那么现在问题转换为什么时候会到达右下角 题目中说了dx与dy的速率之比为15:17 然后知道速率之比为15:17 那么路程之比dx:dy也为1517 所以我们这里暴力枚举就行没一秒dx走15dy走17什么时候同时满足dx可以整除343710和dy可以整除233333的时候就到达了右下角
但是还有一个最重要的关键点别忘记了 我们这里求的路程出发的时候是d要变成2d返回的路径为d也要变成2d
2.代码解答
#includeiostream
#includealgorithm
#includeiomanip
using namespace std;
typedef long long ll;
ll dx0;
ll dy0;
long double sum0;
int main()
{while(1){dx15;dy17;if(dx%3437200dy%2333330)break;}cout setprecision(2) fixed sqrt(2*dy*2*dy2*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.代码解答
#includeiostream
#includealgorithm
using namespace std;
int n;
int ans0;//记录好数的个数bool check(int num)
{bool flag1;//奇数为真 偶数维假//我们一开始将flag设置为真while(num!0)//依次遍历num的每一位数{int tnum%10;num/10;//将这一位丢弃//当奇数位的数为偶数if(flagt%20)return false;//当偶数位的数为奇数if(!flagt%2!0)return false;flag!flag;//更新}return true;//前面都没有返回false 说明是好数 直接return true
}int main()
{cinn;for(int i1;in;i){if(check(i)){ans;}}coutans;return 0;
}四、试题DR格式 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.代码解答
#includeiostream
#includealgorithm
using namespace std;
int n,arr[1000005],len,dex;//len是当前数的总长度 dex记录小数点位置
string d;void kkkk()
{for(int i1;ilen;i)//注意这里是 len 注意细节噢{//每一位依次*2arr[i]*2;}//考虑进位for(int i1;ilen;i)//注意这里是 len 注意细节噢{arr[i1]arr[i]/10;arr[i]%10;}if(arr[len1])//一开始这个值是0 因为我们是全局变量默认为0 如果不是0说明进位导致位数变大{len;//所以要更新长度}
}int main()
{cinnd;//将字符串反转 便于存入arr数组中进行高精度乘法reverse(d.begin(),d.end());dexd.find(.);//此时dex下标为小数点的下标位置 但需要注意的是此下标是从0开始数的d.erase(dex,1);//将小数点删除 便于存入arr中//dex;//将其转换为下标从1开始数的小数点的位置lend.size();//此时已经把小数点删除这个长度就是整个数的长度//存入arr数组中 前面已经反转过了 相当于这里就是倒序存入for(int i0;ilen;i){arr[i1]d[i]-0;}for(int i1;in;i){kkkk();//高精度乘法 每次乘2}//此时已经乘完了所有2 但我们还需要判断一次进位 因为题目说的是输出四舍五入后的整数//这里我们只要判断小数点后第一位数是否大于等于5就可以了if(arr[dex]5){arr[dex1];}//进位更新for(int idex1;ilen;i){arr[i1]arr[i]/10;arr[i]%10;}//查看长度是否变化if(arr[len1]){len;}//输出整数部分for(int ilen;idex;i--){coutarr[i];}return 0;
}五、试题F数字接龙 1.备注
这题需要dfs的知识需要刷过类似于走迷宫的题目请了解后再看题解题解不会详细对此知识点进行教程
2.题意分析
这题当时我第一次提交是过了75%个人感觉这题就是迷宫的简单题 但是关键点就是这个路径不能交叉然后题意很明确题目中把每个条件都列出来了所以就不需要再将复杂题意翻译为简单题意了
3.个人思路解析
首先大致思路就是走迷宫 用dfs 因为结合题意并且看到地图最大为10*10我们直接上dfs 并且不需要剪枝也不需要记忆化搜索这么小直接暴力就行第一个条件就是从起点到终点这个不需要多少第二个条件我们设置一个值next就行表示下一个需要搜寻的值第三个条件我们一开始设置一个初始ans1然后到搜满的时候判断这个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.代码解答
#includeiostream
#includevector
using namespace std;
int n,m,mp[15][15],ans1;//ans表示走过多少格子 当走过格子数总格子数 说明全部格子都经过了
bool vis[15][15];//标记此路线是否走过
bool xvis[15][15][15][15];//对于走斜线进行标记 从位置i j到 位置 k l
bool flag0;//查看最终是否找到一条合适的线路
vectorintpath;//存储路线
//按照图例给的顺序进行此顺序的遍历方向
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(nextm)next0;//重置if(xn-1yn-1)//到达终点 {if(ansn*n!flag)//成功走满所有格子 并且还没有找到一条路线{for(int i0;ipath.size();i){coutpath[i];}flag1;}return;}//依次搜寻每一条方向for(int i0;i8;i){int xxxdx[i];int yyydy[i];if(xx0||yy0||xxn||yyn)continue;//越界if(mp[xx][yy]!next)continue;//不是正确的格子if(vis[xx][yy])continue;//走过了//只有斜着走会导致相交 这里我们判断一下即可if(i1)//向右上角走 所以要判断上面和右边的路线是否斜着走过{if(xvis[x][y1][x-1][y]||xvis[x-1][y][x][y1])continue;}else if(i3)//向右下角走 所以要判断右侧和下面这个路径是否走过{if(xvis[x][y1][x1][y]||xvis[x1][y][x][y1])continue;}else if(i5)//向左下角走 所以要判断左侧和下面这个路径是否走过{if(xvis[x][y-1][x1][y]||xvis[x1][y][x][y-1])continue;}else if(i7)//向左上角走 所以要判断左侧和上面这个路径是否走过{if(xvis[x-1][y][x][y-1]||xvis[x][y-1][x-1][y])continue;}//全部排除完后 这一步可以走if(i1||i3||i5||i7)//更新斜线{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,next1);ans--;vis[xx][yy]0;//重置标记path.pop_back();//重置路径//重置斜线if(i1||i3||i5||i7)//更新斜线{xvis[x][y][xx][yy]0;xvis[xx][yy][x][y]0;}}}int main()
{cinnm;//输入地图大小和Kfor(int i0;in;i){for(int j0;jn;j){cinmp[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 i1;in;i)//找到第一支队伍的起点i
{for(int ji;jn;j)//找到第一支队伍的终点j{for(int kj1;kn;k)//找到第二支队伍的起点k{for(int hk;hn;h)//找到第二支队伍的终点h{}}}
}但我们此时再看数据n最大是10的3次方这里四个for就到达了10的12次方了还没算其他判断的程序 此时我们就能想到用双指针来优化本人恰好也只会这个来优化 我们只用两个for去判断第一个队伍的起点和终点然后用双指针来判断第二个队伍的起点和终点使得复杂度大大降低 关于如何用双指针请看我之前发的如果你此时有这样的疑惑说明没学过或者没学懂双指针请先去学习 下面我们直接上代码
5.代码解答
#includeiostream
#includealgorithm
using namespace std;
typedef long long ll;
ll n,arr[1005],pre[1005],minn1e10;int main()
{cinn;for(int i1;in;i){cinarr[i];pre[i]pre[i-1]arr[i];}for(int i1;in;i)//第一组起点{for(int ji;jn;j)//第一组终点{ll sum1pre[j]-pre[i-1];int leftj1;//第二组起点int rightj1;//第二组终点while(rightnleftright)//双指针枚举起点和终点{ll sum2pre[right]-pre[left-1];ll tabs(sum1-sum2);if(tminn)minnt;//更新if(sum2sum1rightn)//拓宽{right;}else if(sum2sum1leftright){left;}else {if(rightn){right;if(leftright)left;}else{break;}}}}}coutminn;return 0;
}6.注意点
个人感觉双指针最容易错的地方就是在边界的时候怎么去移动要根据题目去判断这个点如果写错特别陷入死循环我经常出错还是练少了
七、试题E: 宝石组合
后续更新… . . … . . . . . . . . . … . .
八、试题G: 爬山
此题有争议这题不讲
总结
祝各位佬统统拿奖
