2024第十五届蓝桥杯 C/C++B组真题题解

wx__ 2024-06-22 15:05:11 阅读 61

2024.4.17

今天看到C语言网题库里有了蓝桥杯真题,可惜好像还没出研究生组的,就顺着刷了一下B组的,写了这篇题解。

交题链接: C语言网-蓝桥杯2024真题

思路和代码仅通过C语言网评测,并不代表绝对正确。


C题 好数

问题描述

在这里插入图片描述

思路简述

简单模拟

枚举从 1 1 1到 n n n每一个数,对每一个数按位判断是否为好数

代码

#include<bits/stdc++.h>using namespace std;typedef long long LL;const int maxn=1e5+5;const int inf=0x3f3f3f3f;int n,cnt;bool check(int x) //判断x是否为好数{ int tmp=0; while(x) { int now=x%10; x/=10; tmp++; if(tmp%2!=now%2) return 0; } return 1;}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) cnt+=check(i); printf("%d\n",cnt); return 0;}

##过题记录

在这里插入图片描述



D题 R格式

问题描述

在这里插入图片描述

思路简述

模拟高精度

要求出 r e s = f ∗ 2 n res=f*2^n res=f∗2n,即求 n n n次 f = f ∗ 2 f=f*2 f=f∗2,也可以写成 f = f + f f=f+f f=f+f

注意数据溢出需要用到高精度,写高精度的时候需要注意小数点,记录小数点的位置。

记小数点的位置为 f d fd fd,小数的位数是不变的,比如初始是 3.14 3.14 3.14,不论乘几次 2 2 2,答案的小数位数一定还是 2 2 2位。

四舍五入的时候需要注意诸如 999.5 999.5 999.5这种情况,四舍五入之后应该是 1000 1000 1000。

代码

//模拟高精度,要求f乘2的n次方,即模拟n次f=f*2#include<bits/stdc++.h>using namespace std;typedef long long LL;const int maxn=1e6+5;const int inf=0x3f3f3f3f;int n,f[maxn],fd,lenf;char s[maxn];void add(){ int flag=0; for(int i=0;i<lenf;i++) { f[i]=f[i]+f[i]+flag; flag=(f[i]>=10); f[i]%=10; } if(flag) f[lenf++]=flag;}int main(){ scanf("%d %s",&n,s); int len=strlen(s); for(int i=len-1;i>=0;i--)//将字符串s转换成高精度数组f if(s[i]!='.') f[lenf++]=s[i]-'0'; else fd=len-1-i;//代表有fd位小数 while(n--) add();//f=f*2或者说f=f+f; if(f[fd-1]>=5) //四舍五入 { int flag=1; for(int i=fd;i<lenf;i++) { f[i]=f[i]+flag; flag=(f[i]>=10); f[i]%=10; } if(flag) f[lenf++]=flag; } for(int i=lenf-1;i>=fd;i--) printf("%d",f[i]); printf("\n"); return 0;}

过题记录

在这里插入图片描述



E题 宝石组合

问题描述

在这里插入图片描述

思路简述

先整理简化 S S S

为方便起见用 a a a代表 H a H_a Ha​, b b b代表 H b H_b Hb​, c c c代表 H c H_c Hc​

则有:

S = a b c ∗ l c m ( a , b , c ) l c m ( a , b ) l c m ( a , c ) l c m ( b , c ) S=abc*\frac{lcm(a,b,c)}{lcm(a,b)lcm(a,c)lcm(b,c)} S=abc∗lcm(a,b)lcm(a,c)lcm(b,c)lcm(a,b,c)​

二元 l c m lcm lcm计算公式为 l c m ( a , b ) = a b g c d ( a , b ) lcm(a,b)=\frac{ab}{gcd(a,b)} lcm(a,b)=gcd(a,b)ab​

但题目中出现了三元 l c m ( a , b , c ) lcm(a,b,c) lcm(a,b,c),怎么计算呢?

我的第一反应是 l c m ( a , b , c ) = l c m ( l c m ( a , b ) , c ) lcm(a,b,c)=lcm(lcm(a,b),c) lcm(a,b,c)=lcm(lcm(a,b),c),但大概推了一下发现简化的 s s s还是很复杂。

所以手写了三组样例 ( 2 , 3 , 5 ) , ( 2 , 3 , 10 ) , ( 2 , 6 , 10 ) (2,3,5),(2,3,10),(2,6,10) (2,3,5),(2,3,10),(2,6,10),尝试推导,加上推测 (瞎猜)可以得到:

l c m ( a , b , c ) = a b c ∗ g c d ( a , b , c ) g c d ( a , b ) ∗ g c d ( a , c ) ∗ g c d ( b , c ) lcm(a,b,c)=\frac{abc*gcd(a,b,c)}{gcd(a,b)*gcd(a,c)*gcd(b,c)} lcm(a,b,c)=gcd(a,b)∗gcd(a,c)∗gcd(b,c)abc∗gcd(a,b,c)​

带入整理一下 s s s就是

S = a b c ∗ a b c ∗ g c d ( a , b , c ) g c d ( a , b ) ∗ g c d ( a , c ) ∗ g c d ( b , c ) a ∗ a ∗ b ∗ b ∗ b ∗ c ∗ c g c d ( a , b ) ∗ g c d ( a , c ) ∗ g c d ( b , c ) = g c d ( a , b , c ) S=abc*\frac{\frac{abc*gcd(a,b,c)}{gcd(a,b)*gcd(a,c)*gcd(b,c)}}{\frac{a*a*b*b*b*c*c}{gcd(a,b)*gcd(a,c)*gcd(b,c)} }=gcd(a,b,c) S=abc∗gcd(a,b)∗gcd(a,c)∗gcd(b,c)a∗a∗b∗b∗b∗c∗c​gcd(a,b)∗gcd(a,c)∗gcd(b,c)abc∗gcd(a,b,c)​​=gcd(a,b,c)

这时候观察数据范围 N = 1 e 5 N=1e5 N=1e5。

a b c abc abc三个变量分别枚举肯定超时, O ( N 3 ) O(N^3) O(N3)只能拿到30%的分。但观察到 H i H_i Hi​本身比较小 ( 1 e 5 ) (1e5) (1e5),所以我们可以直接枚举 S S S。但枚举每个 S S S,每次怎么检查 S S S是否满足条件呢?

这时需要引入set(可能有重复的所以需要multiset),对于枚举的每个 S S S,再枚举其倍数 k S kS kS,用multiset查 k S kS kS是否存在,注意检查的同时满足字典序最小的条件。

总结一下时间复杂度: O ( H ∗ l o g H ∗ l o g n ) = 4 e 7 O(H*logH*logn)=4e7 O(H∗logH∗logn)=4e7。

代码

#include<bits/stdc++.h>using namespace std;typedef long long LL;const int maxn=1e5+5;const int inf=0x3f3f3f3f;int n,a[maxn],res[4];multiset<int>s;int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]),s.insert(a[i]); for(int i=maxn-5;i>=1;i--)//枚举s { int cnt=0; for(int j=i;j<=maxn&&cnt<=2;j+=i)//枚举其倍数 for(int k=1;k<=s.count(j)&&cnt<=2;k++) res[++cnt]=j; if(cnt==3) break; } printf("%d %d %d\n",res[1],res[2],res[3]); return 0;}

过题记录

在这里插入图片描述



F题 数字接龙

问题描述

在这里插入图片描述

思路简述

模拟+搜索,没什么好说的

好久没写了,熟悉的在垒屎山的感觉。

代码

//F#include<bits/stdc++.h>using namespace std;typedef long long LL;const int maxn=1e5+5;const int inf=0x3f3f3f3f;int f[15][15][8],a[15][15],vis[15][15],res[105],n,k,flag;int move1[8]={ -1,-1, 0, 1, 1, 1, 0,-1};int move2[8]={ 0 , 1, 1, 1, 0,-1,-1,-1};bool check(int x,int y){ if(x<1||y<1||x>n||y>n||vis[x][y]) return 0; return 1;}void biaoji(int x,int y,int fx,int v){ if(fx==1) f[x][y+1][7]+=v,f[x-1][y][3]+=v; if(fx==3) f[x][y+1][5]+=v,f[x+1][y][1]+=v; if(fx==5) f[x][y-1][3]+=v,f[x+1][y][7]+=v; if(fx==7) f[x][y-1][1]+=v,f[x-1][y][5]+=v;}void dfs(int x,int y,int cnt){ if(x==n&&y==n&&cnt==n*n) { flag=1; for(int i=1;i<cnt;i++) printf("%d",res[i]); printf("\n"); } if(flag) return; for(int i=0;i<=7;i++) { int nx=x+move1[i],ny=y+move2[i]; if( check(nx,ny) && f[x][y][i]==0 && a[nx][ny]==((a[x][y]+1)%k) ) { res[cnt]=i; biaoji(x,y,i,1); vis[nx][ny]=1; dfs(nx,ny,cnt+1); biaoji(x,y,i,-1); vis[nx][ny]=0; } }}int main(){ scanf("%d %d",&n,&k); if(n==1) return 0*printf("-1\n");//特判n=1的情况 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&a[i][j]); vis[1][1]=1; dfs(1,1,1); if(flag==0) printf("-1\n");//无解的情况 return 0;}

过题记录

在这里插入图片描述

真坑啊

这个倒数第三个点好坑,一直就卡着这一个点过不去,我查了半天思路和代码都觉着没问题,。。。结果看着数据范围构造数据的时候,突然发现n=1的时候有问题,需要特判,此时应该是没路径的吧,直接输出-1,就能ac了。



G题 爬山(不会做,可以跳过不看)

问题描述

在这里插入图片描述

思路简述(不会,可以跳过)

打表可以得到

在这里插入图片描述

分析打表数据:山的高度是1的情况使用第二种魔法 H / 2 H/2 H/2,高度是2到5的时候使用两种魔法相同,大于等于6的时候优先使用第一种魔法 s q r t ( H ) sqrt(H) sqrt(H)

但这么写贪心可以很轻松的hack掉

给出两组hack数据

3 3 3

3 3 3

答案是0

2 1 1

8 9

答案是 9 2 + s q r t ( 8 ) = 4 + 2 = 6 \frac{9}{2}+sqrt(8)=4+2=6 29​+sqrt(8)=4+2=6

写了个优先队列加贪心,但贪心贪的明显有问题

所以…没想出正解,不会

下面的代码倒是把这俩样例过了,但这个面向hack数据编程

像在垒屎,且连C语言网都没AC

未AC代码

#include<bits/stdc++.h>using namespace std;typedef long long LL;const int maxn=1e5+5;const int inf=0x3f3f3f3f;int n,cnt1,cnt2,cnt3,ycnt1,ycnt2;struct node{ int x,y,z; node(){ }; node(int xx,int yy,int zz) { x=xx; y=yy; z=zz;} friend bool operator < (node a,node b) { int mida1=a.x-a.y,mida2=a.x-a.z; int mxa=max(mida1,mida2); int midb1=b.x-b.y,midb2=b.x-b.z; int mxb=max(midb1,midb2); if(mxa==mxb) { if(mida1==0&&mida2==1) return 1; if(midb1==0&&midb2==1) return 0; if(mida1==midb1) { if(mida2==midb2) return a.x<b.x; return mida2>midb2; } return mida1<midb1; } return mxa<mxb; }};priority_queue<node>q;void ps(int x){ q.push(node(x,sqrt(x),x/2));}int main(){ scanf("%d%d%d",&n,&ycnt1,&ycnt2); for(int i=1,x;i<=n;i++) { scanf("%d",&x); ps(x); } while( cnt1+cnt2+cnt3<ycnt1+ycnt2 &&!q.empty()) { node qq=q.top(); q.pop(); int now=qq.x; int mid1=qq.y; int mid2=qq.z; if(cnt2==ycnt2) ps(mid1),cnt1++; else if(cnt1==ycnt1) ps(mid2),cnt2++; else//两种魔法都可以使用 { if(mid1>mid2) ps(mid2),cnt2++; else if(mid1<mid2) ps(mid1),cnt1++; else ps(mid1),cnt3++; } } LL res=0;//注意答案最大1e10,爆int while(!q.empty()) { res+=q.top().x; q.pop(); } printf("%lld\n",res); return 0;}

得分记录

在这里插入图片描述



H题 拔河

问题描述

在这里插入图片描述

思路简述

思维题,主要的限制是:

(1)拉出来的队伍需要连续

(2)且有 l 1 ≤ r 1 < l 2 ≤ r 2 l_1\le r_1 <l_2\le r_2 l1​≤r1​<l2​≤r2​,字面理解就是拉出来的两队人不能有重合(不能有相同的人)

在这两个限制下,求两队伍力量值之和差距最小,第一个限制明显指向了前缀和,但第二个限制明显不好处理,暴力的话就是枚举四个数 l 1 , r 1 , l 2 , r 2 l_1,r_1,l_2,r_2 l1​,r1​,l2​,r2​,前缀和优化之后暴力枚举时间复杂度是 O ( n 4 ) O(n^4) O(n4),但其实第二个限制完全没有用,因为是求差值,所以即使有重合的人也不影响结果(比如第一个队伍选1-4,第二个队伍选3-6,这俩队伍的差值其实和选1-2和5-6是一样的,因为3-4是重合的,对结果没有影响。

那么这个题就可以简化为:

给你n个数字,让你任选两个连续子序列(不完全相同),使俩子序列之和的差值最小,最小是多少。

解:O(n^2)预处理任意两点从i到j的连续子序列和s[i][j],再把求出来的这些和排序,相邻相减取最小值即可。

注意开long long,爆int

代码

#include<bits/stdc++.h>using namespace std;typedef long long LL;const int maxn=1e3+15;const int inf=0x3f3f3f3f;LL n,a[maxn],sum[maxn],mn=inf*inf;vector<LL>v;int main(){ scanf("%lld",&n); for(LL i=1;i<=n;i++) scanf("%lld",&a[i]),sum[i]=sum[i-1]+a[i]; for(LL i=1;i<=n;i++) for(LL j=1;j<=i;j++) v.push_back(sum[i]-sum[j-1]); sort(v.begin(),v.end()); for(int i=1;i<v.size();i++) mn=min(mn,v[i]-v[i-1]); printf("%lld\n",mn); return 0;}

过题记录

在这里插入图片描述

以上是C++B组的题,往下翻的时候看到了一道研究生组的题,顺道就做了,所以附带一道吊坠(暴力匹配+最小生成树)。


吊坠

问题描述

在这里插入图片描述

思路简述

暴力匹配+最小生成树(或者说最大生成树)

用 i , j i,j i,j两两枚举字符串,求 i i i到 j j j的边权值,然后跑最小生成树算法就行。

求边权值的时候,可以直接暴力匹配,思路就是你可以想象你现在枚举的这两个字符串变成两个环,然后一个不动,一个逐渐转圈,然后求匹配的权值,模拟的时候把每个字符串从后面复制一遍就可以。

时间复杂度 O ( n ∗ n ∗ 2 m ∗ 2 m ) = 1 e 8 O(n*n*2m*2m)=1e8 O(n∗n∗2m∗2m)=1e8

代码

#include<bits/stdc++.h>using namespace std;int n,m,f[205];;char s[205][205];struct node{ int u,v,w; node(int uu,int vv,int ww) { u=uu; v=vv;w=ww;}};bool cmp(node a,node b){ return a.w>b.w;}vector<node>g;int pp(int x,int y,int st){ int cnt=0,mx=0; for(int i=1;i<=m;i++) if(s[x][i]==s[y][i+st-1]) mx=max(++cnt,mx); else cnt=0; for(int i=1;i<=m;i++) if(s[x][i]==s[y][i+st-1]) mx=max(++cnt,mx); else cnt=0; return min(m,mx);}int solve(int x,int y){ int mx=0; for(int i=1;i<=m;i++) mx=max(mx,pp(x,y,i)); return mx;}int find(int x){ if(x==f[x]) return x; return f[x]=find(f[x]);}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%s",s[i]+1),f[i]=i; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) s[i][j+m]=s[i][j]; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) g.push_back(node(i,j,solve(i,j))); sort(g.begin(),g.end(),cmp); int cnt=0,ans=0; for(int i=0;i<g.size();i++) { int u=g[i].u,v=g[i].v,w=g[i].w; if(find(u)==find(v)) continue; f[find(u)]=find(v); cnt++;ans+=w; if(cnt==n-1) break; } printf("%d\n",ans); return 0;}

过题记录

在这里插入图片描述



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。