当前位置：主页 > 查看内容

第十二届蓝桥杯 C/C++A组真题赛后回顾

发布时间：2021-08-11 00:00| 有位朋友查看

简介：整体来说比赛到一半的时候感觉还好也就是填空时间用的挺多感觉代码量挺大的可能是我思路太复杂但到了后面心态挺炸的脑子里乱乱的集中不了注意力可能还是因为最近没怎么刷题吧呜呜呜最后留了俩题基本没做。回忆一下题目手里没题面也没代码只能靠回忆想一下赛……

整体来说，比赛到一半的时候感觉还好，也就是填空时间用的挺多，感觉代码量挺大的，可能是我思路太复杂？但到了后面心态挺炸的，脑子里乱乱的，集中不了注意力，可能还是因为最近没怎么刷题吧，呜呜呜，最后留了俩题基本没做。回忆一下题目，手里没题面也没代码，只能靠回忆想一下赛中的思路、代码和题目，做的代码、答案可能也是错的，反正仅供参考吧。

更新了题面

A 卡片

题目描述

分别给出2021个0-9，问从一开始最多能拼到几。
在这里插入图片描述

思路简述

简单模拟

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
const int inf=0x3f3f3f3f;
const int maxn=1e5+5;
const int N=6e6+5;
const LL mod=998244353;
const double pi=acos(-1);
int n,ans,cnt[15],f=1;
int main() // 3181
{
    scanf("%d",&n); //2021
    for(int i=0;i<=9;i++) cnt[i]=n;
    for(int i=1;i<=inf&&f;i++)
    {
        int now=i;
        while(now)
        {
            if(cnt[now%10]) cnt[now%10]--;
            else f=0;
            now/=10;
        }
        if(f) ans=i;
    }
    printf("%d\n",ans);
    return 0;
}

参考结果

3181

B 直线

题目描述

二维平面给出20*21个点，问构成的直线数。
在这里插入图片描述

思路简述

我是两两枚举点，再用set去重记录y=kx+b，x=a，这两种直线，最后结果就是s.size();
赛后写的代码输出结果 48953；赛中 57561…
我感觉写的一模一样的。可能都错了？估计是爆精度了吧。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
const int inf=0x3f3f3f3f;
const int maxn=5e6+5;
const int N=1e7+15;
const LL mod=998244353;
const double eps=1e-7;
const double pi=acos(-1);
int n,m;
struct node{
    double k,b;
    node(double kk,double bb) { k=kk,b=bb; }
    friend bool operator < (node x,node y){
        if(fabs(x.k-y.k)<eps) return x.b<y.b;
        return x.k<y.k;
    }
};
set<node>s;
void solve(int a,int b,int c,int d)
{
    if(a==c&&b==d) return;
    if(a==c)//x=a;
    {
        if(s.find(node(1.0*inf,1.0*a))!=s.end()) return;
        s.insert(node(1.0*inf,1.0*a));
    }
    else //y=kx-ka+b;
    {
        double kk=1.0*(d-b)/(c-a);
        double bb=1.0*kk*a-b;
        if(s.find(node(kk,bb))!=s.end()) return;
        s.insert(node(kk,bb));
    }
}
int main() //20 21
{
    scanf("%d%d",&n,&m);
    for(int a=0;a<n;a++)
        for(int b=0;b<m;b++)
            for(int c=0;c<n;c++)
                for(int d=0;d<m;d++)
                    solve(a,b,c,d);
    printf("%d\n",s.size());
    return 0;
}

参考结果

48953 ？应该错了

C 货物摆放

题目描述

给定n=2021041820210418（队友提醒才知道是日期），求分成 $a ? b ? c$ 的方案数
比如 n=4的时候
1 1 4；1 4 1；1 1 4；1 2 2；2 1 2；2 2 1 六种分法
在这里插入图片描述

思路简述

刚拿到这题，感觉数好大，但想了一下分解之后应该没什么很大的质数，就写了因数分解，分解之后是
2021041820210418
2 3 3 3 17 131 2857 5882353
那后面就是写搜索了，还需要写个set去重。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
const int inf=0x3f3f3f3f;
const int maxn=5e6+5;
const int N=1e7+15;
const LL mod=998244353;
const double pi=acos(-1);
struct node{
    int a,b,c;
    node(int aa,int bb,int cc) { a=aa,b=bb,c=cc; }
    friend bool operator < (node x,node y){
        if(x.a==y.a)
        {
            if(x.b==y.b)
                return x.c<y.c;
            return x.b<y.b;
        }
        return x.a<y.a;
    }
};
set<node>s;
LL n,x[5];
int cnt,prime[maxn],res;
bool is_prime[N],f[maxn];
vector<LL>mid;
void __prime()
{
    for(int i=1;i<=N-5;i++) is_prime[i]=1; is_prime[1]=0;
    for(int i=2;i<=N-5;i++)
        if(is_prime[i])
        {
            prime[++cnt]=i;
            for(int j=i;j<=N-5;j+=i) is_prime[j]=0;
        }
}
/*
2021041820210418
2 3 3 3 17 131 2857 5882353
*/
void fen(){
    LL now=n;
    for(int i=1;i<=cnt;i++)
        while(n%prime[i]==0)
            n/=prime[i],mid.push_back(1LL*prime[i]);
}
void dfs(int ff,int now,LL mul)
{

    if(now==mid.size())
    {
        x[ff]=mul;
        if(ff==1)
        {
            x[2]=n/x[1]/x[0];
            if(s.find(node(x[0],x[1],x[2]))!=s.end()) return;
            s.insert(node(x[0],x[1],x[2]));
            res++;
        }
        else dfs(ff+1,0,1);
        return;
    }
    if(f[now]==0)
    {
        f[now]=1;
        dfs(ff,now+1,mul*mid[now]);
        f[now]=0;
        dfs(ff,now+1,mul);
    }
    else dfs(ff,now+1,mul);
}
int main()
{
    __prime();
    scanf("%lld",&n);
    fen();
    for(int i=0;i<mid.size();i++) printf("%d ",mid[i]); printf("\n");
    dfs(0,0,1);
    printf("%d\n",res);
    return 0;
}

参考结果

2430

D 路径

问题描述

两数绝对值之差小于等于21有边，边权为lcm(i,j)；
一共有2021一个点
问从1到2021的最短路
在这里插入图片描述

思路简述

模拟建图，后面直接跑最短路就行。
我队友赛前还跟我说Bellon-Ford来着

结果他写了弗洛伊德哈哈哈哈哈哈
太秀了

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
const int inf=0x3f3f3f3f;
const int maxn=1e5+5;
const int N=6e6+5;
const LL mod=998244353;
const double pi=acos(-1);
int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
struct node{
    int u,v,w;
    node(int uu,int vv,int ww) { u=uu,v=vv,w=ww; }
};
int n,dis[maxn];
vector<node>g;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) dis[i]=inf; dis[1]=0;
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        {
            if(j-i>21) continue;
            g.push_back( node(  i , j , i*j/gcd(i,j)  ) );
        }
    for(int i=1;i<=n-1;i++)
    {
        bool f=0;
        for(int j=0;j<g.size();j++)
        {
            int u=g[j].u,v=g[j].v,w=g[j].w;
            if(dis[v]>dis[u]+w)
                f=1,dis[v]=dis[u]+w;
        }
        if(f==0) break;
    }
    printf("%d\n",dis[n]);
    return 0;
}

参考结果

10266837

E 回路计数

没做，本来以为能做的，想着做做大题回来，结果后面做炸了，一去不返。
在这里插入图片描述

马上更马上更，在写了在写了
写大题的时候心态有点崩，感觉题意可能读的都有问题。
大题题意好像真不记得了。。。
只能大体想起来思路和代码，也不知道读没读对题

F 砝码称重

问题描

有一个天平和一堆砝码，砝码可以放左边也可以放右边。他现在知道每个砝码的重量。问根据上述条件，能测出多少组不同的重量。
在这里插入图片描述

思路简述

动态规划？
感觉就是写了简单的递推，直接看代码就好了

重要的点是要存下来-sum到sum吧，所以下标都加sum。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
const int inf=0x3f3f3f3f;
const int maxn=1e3+5;
const int N=3e5+5;
const LL mod=998244353;
const double pi=acos(-1);
vector<int>mid;
int n,res,a[maxn],sum,f[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)   scanf("%d",&a[i]),sum+=a[i];
    for(int i=1;i<=n;i++)
    {
        mid.clear();
        mid.push_back(sum+a[i]); mid.push_back(sum-a[i]);
        for(int j=0;j<=2*sum;j++)
            if(f[j])
            {
                if(j-a[i]>=0) mid.push_back(j-a[i]);
                mid.push_back(j+a[i]);
            }
        for(int j=0;j<mid.size();j++) f[mid[j]]=1;
    }
    for(int i=sum+1;i<=2*sum;i++) if(f[i]) res++;
    printf("%d\n",res);
    return 0;
}

G 异或数列

问题描述

~~题意说错了别打我，那说明我也读错了~~
A和B两个人在玩游戏，初始时两人分别有一个数a、b，给出一个数组x，每回合轮到的那人可以做两种操作，选出来一个数异或a或者异或b，每个数只能用一次。A先手，多组输入输出。
在最优策略下，选完所有数，谁的数大谁赢，否则平局。
在这里插入图片描述

思路简述

把所有数按二进制表示，按位计数。如果最高位只有一个的话，肯定先手的A赢了，如果最高位有两个的话，应该去找次高位。所以就只和数位的奇偶有关，但按这样想先手的A根本不会输啊，我也不知道是不是想得太简单了。。阿巴阿巴阿巴，太菜了。

错了
先手必输样例 2 2 2 1
省一无了

代码

#include<bits/stdc++.h> //样例都没得测
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
const int inf=0x3f3f3f3f;
const int maxn=1e5+5;
const int N=6e6+5;
const LL mod=998244353;
const double pi=acos(-1);
int cnt[30],bit[30],n,t,x;
int solve()
{
    for(int i=25;i>=0;i--)
        if(cnt[i]%2)
            return 0*printf("1\n");
    return 0*printf("0\n");
}
int main()
{
    scanf("%d",&t);
    for(int i=0;i<=25;i++) bit[i]=1<<i;
    while(t--)
    {
        scanf("%d",&n);
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x);
            for(int i=25;i>=0;i--)
                if(x>=bit[i])
                    x-=bit[i],cnt[i]++;
        }
        solve();
    }
    return 0;
}

H 左孩子右兄弟

问题描述

把一颗树按照左儿子右兄弟转化成二叉树。树的根高度为0，求转化之后二叉树的最高高度。
在这里插入图片描述

思路简述

构造、树的递归遍历

代码

数据范围、样例和题目细节都想不起来了，代码仅供参考

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int inf=0x3f3f3f3f;
const int maxn=2e5+5;
int n;
vector<int>g[maxn];
int dfs(int u)
{
    int mx=0,sz=g[u].size();
    for(int i=0;i<sz;i++)
        mx=max(mx,dfs(g[u][i])+sz-1);
    return mx+1;
}
int main()
{
    scanf("%d",&n);
    for(int i=2,u;i<=n;i++)
    {
        scanf("%d",&u);
        g[u].push_back(i);
    }
    printf("%d\n",dfs(1)-1);
    return 0;
}

I 括号序列

最气的一道题，一直感觉自己能做，写了一个多小时，还是没的写，最后简化成许多取值的线段取点的题。
比如样例 ((()
最后出来就是从[1,2]、[1,3]两线段上取两个点的方案数，分别是(1,1),(1,2),(1,3),(2,2),(2,3)五种。
再比如(((()
就是从[1,2]、[1,3]、[1,4]上取点，分别是(1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,2,2),(1,2,3),(1,2,4),(1,3,3),(1,3,4),(2,2,2),(2,2,3),(2,2,4),(2,3,3),(2,3,4)十四种。
但就是不知道怎么推出来公式，最后打表都没推出来，绝了，最后写了个爆搜。写完这题的暴力就剩不到半小时了，还有J和E没碰。

不想写这道题…
在这里插入图片描述

J 分果果

问题描述

分糖果
n种糖果，m个人，每种糖果最多分两次，最少分一次，每个人都要分到，且只能分到连续的糖果。
在这里插入图片描述

思路简述

没时间了，看完题还剩十来分钟，写了最暴力的暴力

爆搜
初始化cnt数组都是2
搜的时候枚举起点终点，再遍历看一下起点到终点，出现cnt[i]=0这组起点终点就不合法，合法的话就继续搜，一直递归完m个人，在从1到n判断一下cnt[i]==2也不合法，爆搜所有情况求个res=min(res,mx-mn)

时间复杂度已经不敢想了
可能n=10都难跑出来吧，但确实没时间了…

代码

这么暴力的代码不想再写一遍了
等着有时间仔细想想这题。

；原文链接：https://blog.csdn.net/qq_45856614/article/details/115827861
本站部分内容转载于网络，版权归原作者所有，转载之目的在于传播更多优秀技术内容，如有侵权请联系QQ/微信：153890879删除，谢谢！

上一篇：2021 蓝桥杯省赛第一场 C++ 大学 B 组 下一篇：第十二届蓝桥杯 Java 省赛 B 组（第一场）真题 + 填空题全解

随机推荐

利用Typings为Visual Studio Code实现智

前言相信大家都知道在IDE中代码的智能提示几乎都是标配，虽然一些文本编辑器也...
Android 微信文件传输助手文件夹

微信文件传输助手是微信电脑版与手机微信之间相互传输图片等文件的好工具，但很...
Vue中computed和watch有哪些区别

计算属性computed：支持缓存，只有依赖数据发生改变，才会重新进行计算不支持...
ES6的循环与可迭代对象示例详解

本文将研究 ES6 的 for ... of 循环。旧方法在过去，有两种方法可以遍历 javas...
vbs:把一段文字中指定字符颜色变成红色的

vbs:把一段文字中指定字符颜色变成红色的正则 functionc(Tstr,Word) Dimre Setre...
ASP 常见对象总结(熟悉一下利用以后的开

ADO对象： Connection Command Recordset Record Stream ASP支持的对象很多，可...
歌词编辑器和选择歌曲可播放的网页

歌词编辑器歌词编辑器第一步：选择要播放的歌曲并播放第二步：填写全部的歌词...
成也数据库败也数据库 Oracle 如何云渡

一石激起千层浪，继中国区浩浩荡荡的大裁员告一段落之后，甲骨文并未因此收起手...
【排序算法】之lowb三人组（冒泡、插入、

【排序算法】之lowb三人组冒泡、插入、选择什么是lowb三人组冒泡排序bubble so...
正则表达式的应用

一、正则表达式概述二、正则表达式在VBScript中的应用三、正则表达式在VavaScr...

第十二届蓝桥杯 C/C++A组真题 赛后回顾

A 卡片

题目描述

思路简述

代码

参考结果

B 直线

题目描述

思路简述

代码

参考结果

C 货物摆放

题目描述

思路简述

代码

参考结果

D 路径

问题描述

思路简述

代码

参考结果

E 回路计数

F 砝码称重

问题描

思路简述

代码

G 异或数列

问题描述

思路简述

代码

H 左孩子右兄弟

问题描述

思路简述

代码

I 括号序列

J 分果果

问题描述

思路简述

代码

推荐图文

随机推荐

关于我们

第十二届蓝桥杯 C/C++A组真题赛后回顾