2021年第十二届蓝桥杯省赛CC++B组题解总结

2021年第⼗⼆届蓝桥杯省赛CC++B组题解总结前⼏天（2021.4.18）刚刚⽐完了2021年第⼗⼆届蓝桥杯省赛，本⼈参加的是软件组C++B组的⽐赛，本⽂包括了这⼀届C++B组的题⽬以及部分题解、感悟和总结。⽬录试题A.空间考查计算机基础知识，⼀字节等于8位，1MB=220B答案：67108864256*2^20/4试题B.卡⽚⼀道模拟题，注意题⽬要求求出能够拼到多少，⽽不是求不够拼出多少，最后结果要减1答案：3181#include<iostream>usingnamespacestd;intcnt[15];intmain(){for(inti=0;i<=9;i++)cnt[i]=2021;inti;for(i=1;;i++){intt=i;while(t){if(cnt[t%10]==0){cout<<i-1;return0;}cnt[t%10]--;t/=10;}}return0;}试题C.直线根据直线两点式推导转换成直线⼀般⽅程ax+by+c=0（见下图）这样就不⽤考虑斜率是否存在、避免除法的困扰了，通过除以公约数使a,b,c互质，放⼊set去重就⾏了，但是要重载操作符。答案：40257#include<iostream>#include<cmath>#include<set>usingnamespacestd;structnode{//点intx,y;}p[1000];structline{//直线inta,b,c;//直线⼀般⽅程的系数booloperator<(constline&p)const{if(a==p.a)returnb==p.b?c<p.c:b<p.b;returna<p.a;}booloperator==(constline&p)const{returna==p.a&&b==p.b&&c==p.c;}};intcnt;set<line>se;intgcd(inta,intb){returnb==0?a:gcd(b,a%b);}intgcdd(inta,intb,intc){returngcd(gcd(a,b),gcd(b,c));}intmain(){intn=20,m=21;for(inti=0;i<n;i++)for(intj=0;j<m;j++)p[++cnt]={i,j};for(inti=1;i<=cnt;i++){for(intj=i+1;j<=cnt;j++){inta=p[i].y-p[j].y;//系数intb=p[j].x-p[i].x;intc=p[i].y*(p[i].x-p[j].x)-p[i].x*(p[i].y-p[j].y);intt=gcdd(fabs(a),fabs(b),fabs(c));se.insert({a/t,b/t,c/t});}}cout<<se.size();return0;}试题D.货物摆放题⽬给的数很⼤，如果直接暴⼒两重循环会超时。转换思路，把n所有的约数求出来，发现2021041820210418只有128个约数，然后对这128个约数暴⼒枚举两重循环，计算出结果。可惜这题⽐赛的时候思路歪了想错了。答案：2430#include<iostream>#include<algorithm>usingnamespacestd;typedeflonglongLL;LLyue[101000],cnt;intmain(){LLn=2021041820210418;for(LLi=1;i<=n/i;i++){if(n%i==0){yue[++cnt]=i;if(i*i!=n)yue[++cnt]=n/i;}}//sort(yue+1,yue+cnt+1);//for(inti=1;i<=cnt;i++)cout<<yue[i]<<"";//cout<<cnt;intans=0;for(inti=1;i<=cnt;i++){for(intj=1;j<=cnt;j++){if(n%(yue[i]*yue[j])==0)ans++;}}cout<<ans;return0;}试题E.路径最短路径模版题，dijkstra跑⼀遍就⾏了。⽐赛的时候太赶时间了做完就直接把答案交上去了最后还忘记检查，太懊悔了，⽐赛结束发现我交的答案竟然是0x3f3f3f3f，我TM直接⼼态崩了。⼤家做完⼀定要好好检查答案：10266837#include<iostream>#include<algorithm>#include<cstring>#include<cmath>usingnamespacestd;constintN=2510;intg[N][N],dist[N],st[N];intn=2021;intgcd(inta,intb){returnb?gcd(b,a%b):a;}intlcm(inta,intb){returna*b/gcd(a,b);}intdijkstra(){memset(dist,0x3f,sizeofdist);dist[1]=0;for(inti=1;i<=n;i++){intt=-1;for(intj=1;j<=n;j++){if(!st[j]&&(t==-1||dist[j]<dist[t]))t=j;}st[t]=1;for(intj=1;j<=n;j++){dist[j]=min(dist[j],dist[t]+g[t][j]);}}returndist[n];}intmain(){for(inti=1;i<=n;i++)for(intj=1;j<=n;j++){if(i!=j){if(fabs(i-j)<=21){g[i][j]=lcm(i,j);g[j][i]=lcm(i,j);}else{g[i][j]=0x3f3f3f3f;g[j][i]=0x3f3f3f3f;}}}cout<<dijkstra();//cout<<0x3f3f3f3f;return0;}试题F.时间显⽰【样例输⼊1】46800999【样例输出1】13:00:00【样例输⼊2】1618708103123【样例输出2】01:08:23【评测⽤例规模与约定】对于所有评测⽤例，给定的时间为不超过1018的正整数。这算是⼀道相对⽐较简单的题了，也是唯⼀完整做出来的了，除法取模搞定,注意要⽤longlong。#include<iostream>#include<cstdio>usingnamespacestd;typedeflonglongLL;intmain(){LLn;cin>>n;n/=1000;inth=n/3600%24;n=n%3600;intm=n/60%60;n=n%60;ints=n%60;printf("%02d:%02d:%02d",h,m,s);return0;}试题G.砝码称重【样例输⼊】3146【样例输出】10【样例说明】能称出的10种重量是：1、2、3、4、5、6、7、9、10、11。1=1；2=664(天平⼀边放6，另⼀边放4)；3=41；4=4；5=61；6=6；7=1+6；9=4+61；10=4+6；11=1+4+6。【评测⽤例规模与约定】对于50%的评测⽤例，1≤N≤15。对于所有评测⽤例，1≤N≤100，N个砝码总重不超过100000。嗯？不对劲哦，第⼆题就不会了，01背包？太菜了想不明⽩。后补：闫⽒dp分析法#include<iostream>#include<algorithm>#include<cstring>usingnamespacestd;constintN=110,M=2e5+10;intn,m;//m记录最⼤重量inta[N];表⽰前个砝码，称出的集合，值为bool值，能称出就booldp[N][M];//dp[i][j]ijjtrue//砝码称重intmain(){cin>>n;for(inti=1;i<=n;i++)cin>>a[i],m+=a[i];dp[0][0]=true;for(inti=1;i<=n;i++)//前i个for(intj=0;j<=m;j++)//j称出dp[i][j]=dp[i-1][j]||dp[i-1][j+a[i]]||dp[i-1][abs(j-a[i])];//只要有⼀种情况为真，那么dp[i][j]intans=0;就真for(inti=1;i<=m;i++)if(dp[n][i])ans++;cout<<ans;return0;}试题H.杨辉三⾓形【样例输⼊】6【样例输出】13【评测⽤例规模与约定】对于20%的评测⽤例，1≤N≤10；对于所有评测⽤例，1≤N≤1000000000。这数据开的也太⼤了吧，109次⽅，没办法了暴⼒前⼗个骗分。试题I.双向排序【样例输⼊】33031202【样例输出】312【样例说明】原数列为(1,2,3)。第1步后为(3,2,1)。第2步后为(3,1,2)。第3步后为(3,1,2)。与第2步操作后相同，因为前两个数已经是降序了。【评测⽤例规模与约定】对于30%的评测⽤例，n,m≤1000；对于60%的评测⽤例，n,m≤5000；对于所有评测⽤例，1≤n,m≤100000，0≤ai≤1，1≤bi≤n。上来直接⽤sort，时间复杂度O(mnlogn)，⼀半分应该能拿到#include<iostream>#include<algorithm>usingnamespacestd;inta[101000];intmain(){intn,m;cin>>n>>m;for(inti=1;i<=n;i++)a[i]=i;while(m--){intp,q;cin>>p>>q;if(p==0){sort(a+1,a+q+1,greater<int>());}else{sort(a+q,a+n+1);}}for(inti=1;i<=n;i++)cout<<a[i]<<"";return0;}试题J.括号序列【样例输⼊】((()【样例输出】5【评测⽤例规模与约定】对于40%的评测⽤例，|s|≤200。对于所有评测⽤例，1≤|s|≤5000。好像也是⽤dp，不会做总结这次⽐赛感觉⽐想象的难