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

2024.4.17

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

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

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

C题 好数

问题描述

思路简述

简单模拟

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

代码

#include
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
    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。

代码

#include
using 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