第十二届蓝桥杯C++B组 A~H题题解

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

第十二届蓝桥杯C++B组 A~H题题解

作者：

墨羽魂韶 , 2021-04-19 09:40:54 , 所有人可见 , 阅读 1226

6

8

第十二届蓝桥杯第一场C++B组部分题目回顾

本文所用的试题:

第十二届蓝桥杯大赛软件赛省赛_CB.pdf

最后编辑时间

2021年4月19日 19:27:46

填空题答案速览

67108864
3181
~~88179~~ 40257
2430
10266837

统一声明

如果不写默认带有常用头文件
如果不表明主函数默认表示主函数内
默认使用using namespace std;和ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

填空题

A. 空间

问题简述

256MB可以存放多少32位二进制整数?

问题分析

1Mb = 1024 Kb = 1024*1024B

int = 4B

问题解决

cout << 1ll*256*1024*1024*8/32 << endl;

B. 卡片

问题简述

用标有0~9且各有2021张的卡片可以拼到哪个数字

问题分析

直接按位统计, 不足退出即可, 特别注意, 退出循环的那个应该是正好无法达到的, 应该比那个少一

问题解决

const int N = 10;
int a[N]; for(int i = 0; i < N; ++ i) a[i] = 2021;
int i = 1, flag = 1;
while(flag) {
    int tmp = i++; while(tmp) {
        -- a[tmp%10]; tmp /= 10;
    }
    for(int i = 0; i < N; ++ i) if(a[i] <= 0) flag = 0;
}
cout << --i << endl;

C. 直线

问题简述

给定平面上的 20*21 个整点, 问有不同的多少直线?

问题分析

可以使用y=kx+b或者Ax+By+C=0然后放到set中进行比较, 考虑y=kx+b可能出现小数, 使用Ax+By+C=0更好

其中: $A=y_1-y_2, B=x_2-x_1, C=x_1y_2-x_2y_1$

问题解决

更正: 可能有直线 ax+by+c = 0 与 kax + kby + kc = 0( k != 0)的情况, 应最简之后再扔进set中

D. 货物摆放

问题简述

将 2021041820210418 可以分解为多少种 A * B * C 的形式

问题分析

首先找出所有因子, 之后对因子暴力进行枚举

问题解决

const long long N = 2021041820210418, T = 1e3 + 7;
// 找到所有的因子
int p[T], idx = 0;
for(int i = 1; N/i >= i; ++ i) if(N%i == 0) p[idx++] = i;
// 枚举所有组合
long long int cnt = 0;
for(int a = 0; a < idx; ++ a) for(int b = 0; b < idx; ++ b) for(int c = 0; c < idx; ++ c) {
    if(1ll*p[a]*p[b]*p[c] == N) ++ cnt ;
    if(N/p[a] != p[a] && p[a] == p[b] * p[c]) ++ cnt;
    if(N/p[b] != p[b] && p[b] == p[a] * p[c]) ++ cnt;
    if(N/p[c] != p[c] && p[c] == p[b] * p[a]) ++ cnt;
}
cout <<  cnt << endl;

E. 路径

问题简述

一个无向图, 2021个点, 标号为(1 ~ 2021), 如果两个点的差的绝对值<= 21, 则两点相通, 边长为两点的最大公倍数, 求起点1到2021的最小距离

问题分析

按题目建图, 跑一下spfa

问题解决

n = 2021; 
for(int i = 0; i < 2022; ++ i) 
    for(int j = max(i-21, 0), k = min(i+21, 2021); j <= k; ++ j)
        add(i, j, 1ll*i*j/gcd(i, j));
cout << spfa() << endl;

F. 时间显示

问题简述

给出一个整数, 表示1970年1月1日00:00开始经过的毫秒数, 输出对应的时分秒

问题分析

获取到对应的时间, 然后直接使用printf输出即可

问题解决

long long timer; cin >> timer;
int h = timer/(1000*60*60)%24;
int m = timer/(1000*60)%60;
int s = timer/1000%60;
printf("%02d:%02d:%02d", h, m, s);

G. 砝码称重

问题简述

给出N个砝码, 重量分别为$W_1, W_2, W_3, W_4, ....., W_N$, 请问一共可以称出多少不同的重量

问题分析

假设有一个长度为1e6的数组, 表示可以称出的重量, 那么每多一个砝码(重量为k), 那么对于任何一个已经可以称出的重量(i), 可以组合得到 i-k, k-i, i+k这三种重量

我们只需要维护这个数组即可

问题解决

const int N = 1e6 + 7;
int W[N] = {1};
signed main(){
    int n; cin >> n; while(n--) {
        int t; cin >> t;
        for(int i = 0; i < N; ++ i){
            // 为了节省空间, 用-1表示在大于i的, 1表示小于等于i的, 0表示无法称出的
            if(W[i] == 1) {
                // i-t的情况
                if(i > t) W[i - t] = 1;
                // t-i的情况
                if(t > i + i && W[t - i] != 1) W[t - i] = -1;
                if(t - i > 0 && W[t - i] != -1) W[t - i] = 1;
                // i+t的情况
                if(i + t < N && W[i + t] != 1) W[i + t] = -1;
            }
            if(W[i] == -1) W[i] = 1;
        }
    }
    int cnt = 0; for(int i = 1; i < N; ++ i) cnt += W[i]; cout << cnt << endl;
}

H. 杨辉三角形

问题简述

给定一个数, 求出是在杨辉三角形的第几个数出现的

问题分析

没想到什么好的解法, 目前本人只能暴力模拟, 暂无有效解决方案
直接暴力跑的话可以骗过一些数据
~~推测: 由于最大的数据已经到了1e9, 复杂度应该是$O(\sqrt{n})$, 推测是找质数, 然后通过迷之手段拿到组合数$C_n^k$, 输出$\frac{n*(n+1)}{2}+c$~~
在此感谢大佬:上帝遗弃之仔的幻影的指点
可以直接暴力跑一部分, 当第三列大于 1e9的时候就可以直接判断在第 row 行第二列, 而第三列为 n*(n+1)/2, 既最多暴力循环1e5次

问题解决

const int N = 1e6 + 7;
long long p[N][2], idx;

signed main(){
    long long n; cin >> n;
    // 特判 1
    if(n == 1) {
        cout << 1 << endl; return 0;
    }
    // 暴力跑到当第三列超过1e9时
    p[0][1] = p[1][1] = 1; idx = 2;
    for(int i = 2; idx > 2; ++ i, ++idx) {
        p[0][i&1] = 1;
        for(int j = 1; j <= idx; ++ j) {
            p[j][i&1] = p[j][i-1&1] + p[j-1][i-1&1];
            if(p[j][i-1&1] + p[j-1][i-1&1] > 1e9) {
                idx = j;
            }
            if(p[j][i&1] == n) {
                cout << i*(i+1)/2+j+1 << endl; return 0;
            }
        }
    }
    // 如果没有那么可以判断第 n 行 第二列
    cout << (long long)(n/2*(n+1)+2) << endl;
}