开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 2021年蓝桥杯c++b组解析(个人) -> 正文阅读

[数据结构与算法]2021年蓝桥杯c++b组解析(个人)

随着蓝桥杯不断地推进，期间也要多加练习才能有所收获，对于这份去年的试卷，个人感觉有些难度，具体体现在数字大、状态方程难想，对于后四题编程都有所难度，本人也只能通过40%-60%的样例，下面针对下面10个题进行系统讲解，部分代码与思路源于网上，力求使用最简单的方法帮助你来理解，同时有任何疑问，可以留言，大家一起进步。
同时你的三连就是我创作的最大动力！！！
前言：本次题目还是有一定的难度，不少题目用到了dp，题目是比之前越来越高了，当然厉害的人也是越来越多了（不过我本人实在是太弱了）感觉去年的题目做对3道填空是不成问题的，再在大题混点分，省一还是有点希望的，不过A组竞争会更大一点。其实纵观题目有点难度，但是填空题还是可以在能力范围之内的，只要用心，稍微用一点技巧还是没有问题的，当然大题可以使用暴力，例如打表等方法进行求解。
如果还有什么更好的方法和解析，欢迎留下你的评论！
本次答题正确答案参考了以下的博客讲解：
2021蓝桥杯题解1
2021蓝桥杯题解2

A：空间（5分）

在这里插入图片描述
讲解：此题难度简单，看来也是给我增强信心用的了！这个题目考查对计算机内存的理解：32位二进制是4个字节（8位一个字节），那么25610241024=268435456字节，用总字节除以4=67108864.
故答案是67108864！

B：卡片（5分）

在这里插入图片描述
这个题怎么想呢？其实这个题有个技巧，那就是一定是1最快结束，所以我们只要考虑1什么减少到0。那么这个题关键就是求每个位的数字，一般来说，可以使用循环迭代求出各个位，当然也可以使用整数转换为字符串然后直接进行判断，不过我个人推进循环迭代求出就好了。当然也很容易发现，肯定在千位就结束了，因为光是1000-2000就有1k+个了，所以，最后循环跳出的temp肯定使用break出来的，所以直接对他进行判断，如果是while出来的那必定是0了。
答案：3181

#include <iostream>

using namespace std;

int main(){
    int a[10]={0};
    for(int i=1;;i++){
        int temp=i;
        while(temp){
            int n=temp%10;
            if(n==1) a[1]++;
            if(a[1]==2021) break;
            temp/=10;
        }
        if(temp){
            cout<<i<<endl;
            break;
        }
    }
    return 0;
}

C：直线（10分）

在这里插入图片描述
乍一眼看到这个题就会感觉数字很大，但冷静分析一下，其实就是找不同的直线。注意，不同的直线，那肯定要使用set或map来进行存储了，但是我们也发现一条直线参数有k,b。根据高中数学知识可以得到下面一个直线方程：
$y=\frac{y1-y2}{x1-x2}x+b$
其中x前面的系数就是我们所要的k，那么b怎么得到呢，见下式，直接代入(x1,y1)就好：
$b=y1-\frac{y1-y2}{x1-x2}x1$
然后将k,b代入set里面就好，关键是set怎么处理？这有2个参数，那么当然是使用pair<>了，最好不要自己定义结构体放入set中，因为还需要重载排序方法。
这个题还有一个坑点就是double类型的炸精度，所以要将分母全部写上，如果使用我公式的求法会导致漏解，因为我定义y1是int型。
当然还要注意斜率不存在和直线平行x轴的情况哦！
答案：40257
下面是代码：

#include <iostream>
#include <set>

using namespace std;

int main(){
    set<pair<double,double> > a;
    for(int x1=0;x1<20;x1++){
        for(int y1=0;y1<21;y1++){
            for(int x2=0;x2<20;x2++){
                for(int y2=0;y2<21;y2++){
                    if((x1!=x2)&&(y1!=y2)){
                        double k=(y1-y2)*1.0/(x1-x2);
                        double b=(y1*(x1-x2)-(y1-y2)*x1)*1.0/(x1-x2);
                        a.insert(pair<double,double>(k,b));
                    }
                }
            }
        }
    }
    cout<<a.size()+21+20<<endl;
    return 0;
}

D：货物摆放（10分）

在这里插入图片描述
拿到这个题目很容易发现，这类似于把一个数拆分3个进行乘积，我一开始想暴力解决，直接找出n的全部因数，然后通过打表进行三重循环求解，但发现运算的时候实在太大了，这里使用c++根本都运行不出来，使用java会运行到12位后就很慢了，所以纯粹的暴力解决是解决不了问题。那么只能换个思路了。我突然就想到了质因数分解了，什么意思呢？任何一个数都可以拆分成质因数来进行求解。例如：36=2233。那么把这个质因数找到了，就相当于高中数学排列组合一样，把这几个数放在3个空一样，而且每个空必须有数字，当然了可以是1，这很关键。OK，那么当务之急就是寻找质因数了，这个不难，可以看我下面代码，通过运算得出
$2021041820210418=2*3^3*17*131*2857*5882353$
问题就很显然了，首先考虑2,17,131,2857,5882353这5个数，相当于把这五个数放进3个空里面，那么每一个数就是有3种选择，即3^5=243。
最后考虑3的排列，有3个3，这3个三相当于给这5个数进行分配，不要考虑将其放在3个空中，举个例子，33就是一个数了9（9也是一种情况），我们已经将上面5个数进行放口了，现在就是对这5个数进行分配3的位置，就相当于5个里面选3个，即C(3,5)=10.
所以总数就是2430，很多人会问那11n的情况呢？注意到我前面说的，每个数都有3种选择，那么就存在一个空或2个空没有数来放，那么就是用1来进行补充，这一点很关键！
下面附质因数分解，比较简单的方法。

#include <iostream>

using namespace std;

long long n=2021041820210418;
long long a[]={1,2,3,3,3,17,131,2857,5882353,2021041820210418};

int main(){
    //寻找质因数
    /*for(int i=2;i<=n;i++){
        if(n%i==0) {
            cout<<i;
            n/=i;
            if(n!=1) cout<<",";
            i=1;
        }
    }*/
    cout<<pow(3,5)*10<<endl;
    return 0;
}

E：路径（15分）

在这里插入图片描述
拿到这个题目，心里还是比较开心的，这不就是最短路径的题目吗？心里还是比较开心的。当然前面的信息也不要大意，首先是最小公倍数怎么求，这里还是使用最常规的辗转相除法，先求出公因数，然后根据公式求出最小公倍数。接下来的事就是交给了图。首先对于图，不要忘记对角线a[i][i]=0，当然了不存在的路就是无穷大了。关键还得是怎么求图的最短路径，这里为了方便还是使用Floyd算法吧，比较简单，就是三个循环的事了。关于Floyd和Dijkstra的算法可以看我之前的博客此处链接
下面是解法代码（不过需要等待一会），答案是10266837

#include <iostream>

using namespace std;

int gcd(int m,int n){
    return m%n==0?n:gcd(n,m%n);
}

long long a[2022][2022];
const long long  maxm=2147483647;

int main(){
    for(int i=1;i<=2021;i++){
        for(int j=1;j<=2021;j++){
            if((i-j>21)||(i-j<-21)){
                a[i][j]=a[j][i]=maxm;
            }
            else if(i==j) a[i][j]=a[j][i]=0;
            else{
                int ix=max(i,j);
                int jx=min(i,j);
                a[i][j]=a[j][i]=i*j/gcd(ix,jx);
            }
        }
    }
    //floyd
    for(int i=1;i<=2021;i++){
        for(int j=1;j<=2021;j++){
            for(int k=1;k<=2021;k++){
                if(a[j][k]>a[j][i]+a[i][k]){
                    a[j][k]=a[j][i]+a[i][k];
                }
            }
        }
    }
    cout<<a[1][2021]<<endl;
    return 0;
}

F：时间显示（15分）

在这里插入图片描述
这个别的不说，签到题。思路就是毫秒不用去管，然后根据时间运算来进行取舍，当然了同时也考了格式化输出的方法，注意到如何显示0和不显示，这个还是一个基本功，临近竞赛抽时间来整理一下。

#include <iostream>

using namespace std;

long long n,s,hour,mins,sec;

int main(){
    cin>>n;
    s=n/1000;
    hour=s/(60*60);
    mins=(s-hour*3600)/60;
    sec=s-hour*3600-mins*60;
    printf("%02lld:%02lld:%02lld\n",hour%24,mins%60,sec%60);
    return 0;
}

G：砝码称重（20分）

在这里插入图片描述
其实拿到这道题我是比较难受的，一看就知道要用到dp，然后并没有掌握得太好。这其实就是类似于整数拆分的问题，通过实现拆分来达到目的。我这个自己的做法也只能通过40%的数据，大概思路就是dfs了，（深搜yyds)整体思路就是通过在sum加减数字来达到目的。话说也可能有同学不太理解dfs，这里就做简单的回答：在这个题目面，先进行sum+a[i]，等待此时i达到N时就出来，比较类似于栈一样进行回溯，然后再进入下一个阶段。
通过40%简单理解的代码：

#include <iostream>

using namespace std;

const int maxn=1e6;

int N;
long long a[maxn];
int vis[maxn];

void dfs(int sum,int i){
    if(i==N){
        if(sum>0){
            vis[sum]=1;
        }
        return;
    }
    dfs(sum+a[i],i+1);
    dfs(sum,i+1);
    dfs(sum-a[i],i+1);
}

int main(){
    int cnt=0;
    cin>>N;
    for(int i=0;i<N;i++){
        cin>>a[i];
    }
    dfs(0,0);
    for(int i=1;i<=maxn;i++){
        if(vis[i]==1){
            cnt++;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

正确代码：关键就是状态方程。（考试能写出40%也是很不错了）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int dp[102][100002];

int main()
{
    int n;
    scanf("%d",&n);
    int w[n+1];
    ll sum=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&w[i]);
        sum+=w[i];
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=sum;j++){
            dp[i][j]=dp[i-1][j];
            if(dp[i][j]==0){
                if(w[i]>j)dp[i][j]=dp[i-1][w[i]-j];
                if(w[i]==j)dp[i][j]=1;
                if(w[i]<j)dp[i][j]=dp[i-1][j-w[i]];
            }
        }
    }

    ll ans=0;
    for(int i=1;i<=sum;i++){
        if(dp[n][i])ans++;
    }
    printf("%lld",ans);
    return 0;
}

H：杨辉三角形（20分）

在这里插入图片描述
本题我也没什么好的思路，对于这个题我的最开始的思路偏向于大表，肯定是过不了全部用例，至少还是能混点一半分的，挂网测大概40%通过。这里的思路首先构造c[i][j]，对此进行赋值，不过建立起map关系，将出现的数字和位置放在map中，这样就很快查询了，比一般的查询要快不少，但还是暴力打表求解，不过打表法yyds!
附通过40%的样例代码：

#include <iostream>
#include <map>
#include <cstring>

using namespace std;

const int maxn=1000;
long long c[maxn][maxn];
int N;
map<long long,long long> a;

int main(){
    memset(c,0,sizeof(c));
    for(int i=0;i<maxn;i++) c[i][0]=1;
    for(int i=0;i<maxn;i++) c[i][i]=1;
    for(int i=2;i<maxn;i++){
        for(int j=1;j<i;j++) c[i][j]=c[i-1][j]+c[i-1][j-1];
    }
    int sum=0;
    for(int i=0;i<maxn;i++){
        for(int j=0;j<=i;j++){
            if(c[i][j]!=0){
                sum++;
                if(a.find(c[i][j])==a.end()){
                    a.insert(pair<long long,long long>(c[i][j],sum));
                }
            }
        }
    }
    cin>>N;
    map<long long,long long>::iterator it;
    it=a.find(N);
    cout<<it->second<<endl;
    return 0;
}

下面是正确的答案：这个题正确解法偏向于二分求解。

#include <bits/stdc++.h>
using namespace std;

// 打印杨辉三角前x行，帮助直观感受
void Print(int x) {
  long long int c[100][100];

  for (int i = 1; i <= x; i++) {
    c[i][0] = 1;
    printf("%lld\t", c[i][0]);
    for (int j = 1; j < i; j++) {
      c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
      printf("%lld\t", c[i][j]);
    }
    printf("\n");
  }
}

// 二分方法
long long int n;
long long int C(long long int a, long long int b) {
  long long int ret = 1;
  for (long long int i = a, j = 1; j <= b; i--, j++) {
    ret = ret * i / j;
    if (ret > n) {
      return n + 1;
    }
  }
  return ret;
}

long long int GetAns(int col) {
  long long int l = col, r = max(n, (long long int)col);
  while (l < r) {
    long long int mid = (l + r) / 2;
    if (C(mid, col) >= n)
      r = mid;
    else
      l = mid + 1;
  }

  if (C(r, col) != n) { // 没有出现则返回出现位置无限大
    return 4e18;
  } else {
    return r * (r + 1) / 2 + col + 1;
  }
}

int main() {
  scanf("%lld", &n);

  long long int ans = 4e18;
  for (int i = 0; i < 20; i++) { // 枚举前20列，记录最早出现位置
    long long int cur = GetAns(i);
    ans = min(ans, cur);
  }

  printf("%lld\n", ans);
  return 0;
}

I：双向排序（25分）

在这里插入图片描述
这个题目我是没啥思路，照样使用sort函数走天下！比较sort函数会采用最好的方法来选择。这个题目理解了意思就不觉得困难了。关键在于p=1和p=0的情况，当然也要注意，题目要求是对a1,a2…进行排序，也就是说你换了顺序以后，你的数组编号也要跟着改变，理解了这个意思就会觉得比较简单了！
通过60%评测的代码：

#include <iostream> 
#include <algorithm>

using namespace std;

int n,m;

bool cmp(int a,int b){
    return a>b;
}

int main(){
    cin>>n>>m;
    int a[n+1];
    for(int i=0;i<=n;i++) a[i]=i; 
    while(m--){
        int p,q;
        cin>>p>>q;
        if(p==0){
            sort(a+1,a+q+1,cmp);
        }else{
            sort(a+q,a+1+n);
        }
    }
    for(int i=1;i<=n;i++) cout<<a[i]<<" ";
    cout<<endl;
    return 0;
}

贴一波正确代码：

#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int sta[m];//栈数组
    int cnt=0;//栈的长度
    while(m-->0)
    {
        int op;
        int mid;
        scanf("%d %d",&op,&mid);

        if(op==0){
            if(cnt%2!=op)
            {
                if(cnt-1>=0&&sta[cnt-1]<=mid)cnt--;
                else continue;
            }
            while(cnt-2>=0&&sta[cnt-2]<=mid){
                cnt-=2;
            }
        }else{
            if(cnt%2!=op)
            {
                if(cnt-1>=0&&sta[cnt-1]>=mid)cnt--;
                else continue;
            }
            while(cnt-2>=0&&sta[cnt-2]>=mid){
                cnt-=2;
            }
        }
        sta[cnt++]=mid;
    }
    int l=1;
    int r=n;
    int ans[n+1];//答案数组
    int x=n;
    for(int i=0;i<cnt;i++){
        int mid=sta[i];
        if(i%2==1){
            mid=min(r, mid);
            while(l<mid)ans[l++]=x--;
        }
        else {
            mid=max(l, mid);
            while(r>mid)ans[r--]=x--;
        }
        if(r-l<1)break;
    }
    if(l<=r)
        if(cnt%2==1) {
            while(l<=r)ans[l++]=x--;
        }else {
            while(l<=r)ans[r--]=x--;
        }

    printf("%d",ans[1]);
    for(int i=2;i<=n;i++)
    {
        printf(" %d",ans[i]);
    }
    printf("\n");
}

J：括号序列（25分）

在这里插入图片描述
本题我觉得是最难的一道题，没什么特别好的思路，参考了一个博主的想法，写下了这段代码，主要是通过dfs方法来进行，这样每一次插入set中判断是否重复过。

#include <iostream>
#include <stack>
#include <string>
#include <cstring>
#include <set>
#include <cmath>
#include <algorithm>

using namespace std;

string m;
const int mod=1e9+7;
int f;
char c;
set<string> a;

//判断括号是否匹配
bool isok()
{
    stack<char> sta;
    for(int i=0;i<m.size();i++){
        if(m[i]=='('){
            sta.push(m[i]);
        }else{
            if(sta.empty()||sta.top()!='(')return false;
            else sta.pop();
        }
    }
    if(sta.empty())return true;
    else return false;
}

//dfs，把每一种情况都进行判断
void dfs(int depth){
    if(depth==f){
        if(isok()){
            a.insert(m);
        }
    }else{
        for(int i=0;i<m.size();i++){
            m.insert(m.begin()+i,c);
            dfs(depth+1);
            m.erase(m.begin()+i,m.begin()+i+1);
        }
    }
}

int main(){
    cin>>m;
    int left=0,right=0;
    for(int i=0;i<m.size();i++){
        if(m[i]=='('){
            left++;
        }else{
            right++;
        }
    }
    int flag=0;
    left>right?flag=0:flag=1;
    left>right?c=')':c='(';
    f=abs(left-right);
    dfs(0);
    cout<<a.size()<<endl;
    return 0;
}

贴一波正确代码：


#include <bits/stdc++.h>
using namespace std;
const int maxn = 5052;
const long long int MOD = 1e9 + 7;

int dp[maxn][maxn];
bool vis[maxn][maxn];
char str[maxn];
int n;

long long int mod(long long int x) { return x % MOD; }

long long int GetAns() {
  memset(dp, 0, sizeof dp);
  memset(vis, 0, sizeof vis);
  dp[0][0] = 1;
  vis[0][0] = true;

  for (int i = 1; i <= n; i++) {
    if (str[i - 1] == '(') {
      for (int j = 1; j <= n; j++) {
        dp[i][j] = dp[i - 1][j - 1];
        vis[i][j] = vis[i - 1][j - 1];
      }
    } else {
      dp[i][0] = mod(dp[i - 1][0] + dp[i - 1][1]);
      vis[i][0] = vis[i-1][0] | vis[i-1][1];
      for (int j = 1; j <= n; j++) {
        dp[i][j] = mod(dp[i - 1][j + 1] + dp[i][j - 1]);
        vis[i][j] = vis[i - 1][j + 1] | vis[i][j - 1];
      }
    }
  }
  for (int i = 0; i <= n; i++) {
    if (vis[n][i] != 0) {
      return dp[n][i];
    }
  }
  return -1;
}
int main() {
  scanf("%s", str);
  n = strlen(str);

  long long int ansL = GetAns();

  reverse(str, str + n);
  for (int i = 0; i < n; i++) {
    if (str[i] == ')') {
      str[i] = '(';
    } else {
      str[i] = ')';
    }
  }
  long long int ansR = GetAns();

  printf("%lld\n", mod(ansL * ansR));
  return 0;
}