2021年第十二屆藍橋杯省賽CC++B組題解總結(jié)

2021年第??屆藍橋杯省賽CC++B組題解總結(jié)前?天（2021.4.18）剛剛?完了2021年第??屆藍橋杯省賽，本?參加的是軟件組C++B組的?賽，本?包括了這?屆C++B組的題?以及部分題解、感悟和總結(jié)。?錄試題A.空間考查計算機基礎(chǔ)知識，?字節(jié)等于8位，1MB=220B答案：67108864256*2^20/4試題B.卡??道模擬題，注意題?要求求出能夠拼到多少，?不是求不夠拼出多少，最后結(jié)果要減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.直線根據(jù)直線兩點式推導(dǎo)轉(zhuǎn)換成直線?般?程ax+by+c=0（見下圖）這樣就不?考慮斜率是否存在、避免除法的困擾了，通過除以公約數(shù)使a,b,c互質(zhì)，放?set去重就?了，但是要重載操作符。答案：40257#include<iostream>#include<cmath>#include<set>usingnamespacestd;structnode{//點intx,y;}p[1000];structline{//直線inta,b,c;//直線?般?程的系數(shù)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;//系數(shù)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.貨物擺放題?給的數(shù)很?，如果直接暴?兩重循環(huán)會超時。轉(zhuǎn)換思路，把n所有的約數(shù)求出來，發(fā)現(xiàn)2021041820210418只有128個約數(shù)，然后對這128個約數(shù)暴?枚舉兩重循環(huán)，計算出結(jié)果。可惜這題?賽的時候思路歪了想錯了。答案：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跑?遍就?了。?賽的時候太趕時間了做完就直接把答案交上去了最后還忘記檢查，太懊悔了，?賽結(jié)束發(fā)現(xiàn)我交的答案竟然是0x3f3f3f3f，我TM直接?態(tài)崩了。?家做完?定要好好檢查答案：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【評測?例規(guī)模與約定】對于所有評測?例，給定的時間為不超過1018的正整數(shù)。這算是?道相對?較簡單的題了，也是唯?完整做出來的了，除法取模搞定,注意要?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?！驹u測?例規(guī)模與約定】對于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【評測?例規(guī)模與約定】對于20%的評測?例，1≤N≤10；對于所有評測?例，1≤N≤1000000000。這數(shù)據(jù)開的也太?了吧，109次?，沒辦法了暴?前?個騙分。試題I.雙向排序【樣例輸?】33031202【樣例輸出】312【樣例說明】原數(shù)列為(1,2,3)。第1步后為(3,2,1)。第2步后為(3,1,2)。第3步后為(3,1,2)。與第2步操作后相同，因為前兩個數(shù)已經(jīng)是降序了?！驹u測?例規(guī)模與約定】對于30%的評測?例，n,m≤1000；對于60%的評測?例，n,m≤5000；對于所有評測?例，1≤n,m≤100000，0≤ai≤1，1≤bi≤n。上來直接?sort，時間復(fù)雜度O(mnlogn)，?半分應(yīng)該能拿到#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【評測?例規(guī)模與約定】對于40%的評測?例，|s|≤200。對于所有評測?例，1≤|s|≤5000。好像也是?dp，不會做總結(jié)這次?賽感覺?想象的難