C/C++教程

【蓝桥杯备赛】2021年第十二届蓝桥杯省赛第一场(5月9日)真题C++ B组 未完待续……

本文主要是介绍【蓝桥杯备赛】2021年第十二届蓝桥杯省赛第一场(5月9日)真题C++ B组 未完待续……,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

文章目录

  • 题目结构
    • 第一题 空间
    • 第二题 卡片
    • 第三题 直线
    • 第四题 货物摆放
    • 第五题 路径
    • 第六题 时间显示

题目结构

项目题型分值题型
第一题结果填空5空间(单位换算)
第二题结果填空5卡片(模拟)
第三题结果填空10直线(数学)
第四题结果填空10货物摆放(数学)
第五题结果填空15路径(最短路径)
第六题程序设计15时间显示(时间换算/取位数)
第七题程序设计20砝码称重(DP)
第八题程序设计20杨辉三角
第九题程序设计25双向排序
第十题程序设计25括号序列

第一题 空间

小蓝准备用 256MB 的内存空间开一个数组,数组的每个元素都是 32 位 二进制整数,如果不考虑程序占用的空间和维护内存需要的辅助空间,请问 256MB 的空间可以存储多少个 32 位二进制整数?

进值转换:1MB=1024KB 1KB=1024B 1B=8位

cout<<256*1024*1024/4<<endl;

第二题 卡片

在这里插入图片描述

  1. 用数组计数,从2021减
  2. 枚举取位数
  3. excel+word检验
#include <iostream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
int cnt[10]={0};
int main(){
    for(int i=0;i<=9;i++) cnt[i]=2021;
    for(int i=1;;i++){
        int t=i;
        while(t){
            if(cnt[t%10]==0) {
                cout<<i-1;
                return 0;
            };
            cnt[t%10]--;
            t/=10;
        }
    }
    return 0;
}

第三题 直线

在这里插入图片描述

  1. 确定直线用两点式:(y1-y2)x+(x2-x1)y+(x1y2-x2y1)=0
  2. 枚举所有的直线
  3. 使用set去重
  4. pair存放坐标
#include<iostream>
#include<vector>
#include<set>
using namespace std;
typedef pair<int,int> PII;
typedef pair<PII,int> PIII;
vector<PII> v;
set<PIII> s;
int x,y;
int gcd(int a,int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int main(){
    cin>>x>>y;

    for(int i=0;i<x;i++){
        for(int j=0;j<y;j++){
            v.push_back({i,j});
        }
    }

    for(int i=0;i<v.size();i++){
        for(int j=i+1;j<v.size();j++){
            int x1=v[i].first;
            int y1=v[i].second;
            int x2=v[j].first;
            int y2=v[j].second;
            int A=y1-y2,B=x2-x1,C=x1*y2-x2*y1;
            int gcdd=gcd(gcd(A,B),C);
            s.insert({{B/gcdd,A/gcdd},C/gcdd});
        }
    }
    
    cout<<s.size();
    return 0;
    //答案40257
}

第四题 货物摆放

在这里插入图片描述

  1. 找到因子数组(平方循环技巧)
  2. 遍历因子数组判断乘积是否为n并计数
#include<iostream>
using namespace std;
typedef long long ll;
ll a[5000];
ll len=0,cnt=0;
int main()
{
    ll n=2021041820210418;
    for(ll i=1;i*i<=n;i++){
        if(n%i==0){
            a[len++]=i;
            if(i!=n/i){
                a[len++]=n/i;
            }
        }
    }
    for(ll i=0;i<len;i++){
        for(ll j=0;j<len;j++){
            for(ll k=0;k<len;k++){
                if(a[i]*a[j]*a[k]==n){
                    cnt++;
                }
            }
        }
    }
    cout<<cnt<<endl;
} // namespace std;

第五题 路径

在这里插入图片描述

  1. 首先确定使用弗洛伊德算法求解最短路径(三个循环)
  2. 使用邻接矩阵构造图
  3. 弗洛伊德求最短路径得到结果
  4. 注意邻接矩阵的数据类型应该为long long 因为无穷大设置的为1e18
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define INF 1e18;
ll mp[3000][3000];
int gcd(int a,int b){
    if(b==0) return a;
    else return gcd(b,a%b);
}
void Floyd(int n){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
            }
        }
    }
}
int main()
{
    int n=2021;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j) mp[i][j]=0;
            else if(abs(i-j)<=21) mp[i][j]=mp[j][i]=i*j/gcd(i,j);
            else mp[i][j]=mp[j][i]=INF;
        }
    }
    Floyd(n);
    cout<<mp[1][2021]<<endl;
    return 0;
} // namespace std;

第六题 时间显示

在这里插入图片描述
在这里插入图片描述
所有数据不超过10^18

#include <iostream>
#include <stdio.h>
using namespace std;
long long t,h,m,s,ms;
int main()
{
    cin>>t;
    t=t/1000;
    h=t/3600%24;
    m=t/60%60;
    s=t%60;
    printf("%02lld:%02lld:%02lld",h,m,s);
    return 0;
}
这篇关于【蓝桥杯备赛】2021年第十二届蓝桥杯省赛第一场(5月9日)真题C++ B组 未完待续……的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!