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

2024.4.17

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

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

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

C题 好数

问题描述

思路简述

简单模拟

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

代码

#includeusing 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    int flag=0;    for(int i=0;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            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。

代码

#includeusing namespace std;typedef long long LL;const int maxn=1e5+5;const int inf=0x3f3f3f3f;int n,a[maxn],res[4];multisets;int main(){    scanf("%d",&n);    for(int i=1;i=1;i--)//枚举s    {        int cnt=0;        for(int j=i;j-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    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        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    int x,y,z;    node(){};    node(int xx,int yy,int zz) { x=xx; y=yy; z=zz;}    friend bool operator