本次题解格式参考 墨羽魂韶

本文所用的试题:
第十二届蓝桥杯大赛软件赛省赛_CB.pdf

最后编辑时间
2021年4月29日 21:27:46

填空题答案速览

统一声明
如果不写默认带有常用头文件
如果不表明主函数默认表示在 void solve(){}
默认使用

using namespace std;

ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using ll = long long;

填空题答案速览

1. 67108864
2. 3181
3. 40257
4. 2430
5. 10266837

A. 空间

问题简述

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

1 Mb = 1024 Kb = 1024 * 1024 b

int = 4B (一个 int 占4比特)

注意用 long long

cout << 1ll * 256 * 1024 * 1024 * 8 / 32 << "\n";

B. 卡片

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

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

void solve() {
    for (int i = 0; i < 10; ++i) a[i] = 2021;
    int i = 1;
    while (true) {
        int tmp = i;
        while (tmp) {
            --a[tmp % 10], tmp /= 10;
        }
        bool f = true;
        for (int i = 0; f && i < 10; ++i)
            if (a[i] < 0) f = false;
        if (!f) break;
        i++;
    }
    cout << --i << '\n';
}

C. 直线

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

问题分析

结论而言就是比较K，B值，可以直接模拟，代码如下

const int N = 2e5 + 10;
struct Line {
    double k, b;
    bool operator<(const Line &t) const {
        if (k != t.k) return k < t.k;
        return b < t.b;
    }
} l[N];

void solve() {
    int cnt = 0;
    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) {
                        double k = (double)(y2 - y1) / (x2 - x1);
                        double b = y1 - k * x1;
                        l[cnt++] = {k, b};
                    }
                }
    sort(l, l + cnt);
    int ans = 1;
    for (int i = 1; i < cnt; ++i)
        if (fabs(l[i].k - l[i - 1].k) > 1e-8 || fabs(l[i].b - l[i - 1].b) > 1e-8)
            ans++;
    cout << ans + 20 << '\n'; // 加上20条竖线
}

D. 货物摆放

问题简述

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

问题分析

找到所有的因子，然后对因子进行暴力枚举

const ll N = 2021041820210418, mod = 1e3 + 7;
int P[mod], idx = 0;
void solve() {
    for (int i = 1; N / i >= i; ++i)
        if (N % i == 0) P[idx++] = i;
    ll cnt = 0;
    for (int i = 0; i < idx; ++i)
        for (int j = 0; j < idx; ++j)
            for (int k = 0; k < idx; ++k) {
                if (1ll * P[i] * P[j] * P[k] == N) ++cnt;
                if (N / P[i] != P[i] && P[i] == P[j] * P[k]) ++cnt;
                if (N / P[j] != P[j] && P[j] == P[i] * P[k]) ++cnt;
                if (N / P[k] != P[k] && P[k] == P[j] * P[i]) ++cnt;
            }
    cout << cnt << "\n";
}

E. 路径

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

问题分析
按题目建图, 跑一下SPFA（dijstra 等均可

void solve() {
    int 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() << '\n';// 赛后听说有人暴力跑 Floyd 也能出答案，但不建议
}

F. 时间显示

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

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

void solve() {
    ll time;
    cin >> time;
    int h = time / (1000 * 60 * 60) % 24;
    int m = time / (1000 * 60) % 60;
    int s = time / 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};
void solve() {
    int n, t;
    cin >> n;
    while (n--) {
        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 << '\n';
}

H. 杨辉三角形

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

问题分析

待补充

I. 双向排序

问题简述
给定序列 \(a_1,a_2,…,a_n=1,2,…,n,\) 对该序列进行 \(m\)次 操作, 每次可能是对 [1, q]进行降序排列或者对[q, n] 进行升序排列

问题分析
没啥思路, 直接sort骗分了, 不过sort前判断了下当前是否有序, 有序直接调整了

暂未解决

J. 括号序列

问题简述
给定一个括号序列，要求尽可能少地添加若干括号使得括号序列变得合法

问题分析
分为两种特殊情况:

1. 当左括号或右括号数量全为零, 此时是个卡特兰数
2. 左括号与右括号相等, 不需要再插入括号

暂未解决