第十二届蓝桥杯C++B组第一场省赛

相关题目：PDF

A.空间

问256MB的内存开一个数组，数组每个元素大小都是32位二进制整数。问最多储存多少个32位二进制整数？

提示

1B = 8bit = 8位

32位是一个int的长度

256MB = (256 $\times$ 1024 $\times$ 1024)B = (256 $\times$ 1024 $\times$ 1024 $\times$ 8)b

所以说我们有2147483648个bit，将这个数再除以32bit就是答案：67108864

B.卡片

问：有0～9的卡片各2021张，一张卡片可以当作一个数字，例如拼出1024需要一张1，一张0，一张2，一张4。卡片用完了就没有了啊，现在要求从1开始拼数字最多拼到多少？

好家伙，我直接模拟，答案：3181

#include <iostream>

using namespace std;

const int N = 15;

int c[N];

int check(int x){
    while (x) {
        int t = x % 10;
        x /= 10;
        c[t]--;
        if (c[t] < 0) return 0; 
    }
    return 1;
}

int main (){
    for (int i = 0; i <= 9; ++ i) c[i] = 2021;
    
    for (int i = 1; ; ++ i) {
        if (!check(i)) {
            cout << i - 1;
            break;
        }
    }
    
    
    return 0;
}

C.直线

问：x方向上有20个点，y方向上有21个点。即x是0到19之间的整数，y是0到20之间的整数。这些点一共确定了多少条不同的直线？

提示

斜率和截距可以表示一条直线

注意斜率不存在的情况

不建议用哈希表去存斜率，因为c++中的double会有精度的误差。

我们现在只要认为两个浮点数在一定的范围内 $|x_1 - x_2|\le 10^8$，就说他俩相等

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 200000;
int n;

struct Line{
    double k, b; // 斜率和截距
    bool operator< (const Line &L) const {
        if (k != L.k) return k < L.k; // 如果斜率不等 小的在前
        else return b < L.b; // 如果斜率相等，截距小的在前
    }
}l[N];


int main (){
    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) (y1 - y2) / (x1 - x2);
                        double b = k * x1 - y1;
                        l[n ++ ] = {k ,b};
                    }
                }
            }
        }
    }
    // 记得这里是1,因为之后是对比两条不同的直线的
    // 例如只有两条直线，只比对一次res=1，但很显然有2条直线呀
    int res = 1; 
    sort(l, l + n);
    for (int i = 0; i < n - 1; ++ i) {
        if (abs(l[i].k - l[i+1].k) > 1e-8 || abs(l[i].b - l[i+1].b) > 1e-8) {
            res ++;
        }
    }
    // 注意！20是斜率不存在的直线
    cout << res + 20 << endl;
    
    return 0;
}

答案：40257

D.货物摆放

小蓝有 $n$ 箱货物要摆放在仓库，货物都是正方形。她希望所有的货物摆成一个大的立方体。

比如说在长、宽、高的方向上分别堆放 $L$、$W$、$H$ 个的货物，必须满足 $n = L \times W \times H$。

例如当 $n=4$ 时，有六种方案：$1 \times 1 \times 4、1 \times 2 \times 2、1 \times 4 \times 1、2 \times 1 \times 2、2 \times 2 \times 1、4 \times 1 \times 1$。

现在问你 $n = 2021041820210418$ 时（16位数字），有多少种方案？

提示

2021041820210418没有超过long long的范围

$L$、$W$、$H$ 都是 $n$ 的因数

求出所有因数之后，来个三个for判断乘积是否是 $n$ 就行了

#include <iostream>
#include <vector>

using namespace std;

typedef long long LL;

vector<LL> v;

const LL n = 2021041820210418;

int main (){
    // 求因数
    for (LL i = 1; i * i <= n; ++ i) {
        if (n % i == 0) {
            // 10 % 5 == 2;
            // 5和2都是因数
            v.push_back(i);
            // 4 % 2 == 2 这个if因为这种情况而存在
            if (n / i != i) v.push_back(n / i);
        } 
    }
    int res = 0;
    for (LL i = 0; i < v.size(); ++ i) {
        for (LL j = 0; j < v.size(); ++ j) {
            for (LL k = 0; k < v.size(); ++ k) {
                if (n == v[i] * v[j] * v[k]) res ++;
            }
        }
    }
    cout << res << endl;
    
    return 0;
}

答案：2430

E.路径

一个图有2021个结点构成，依次编号1至2021。如果两个结点的绝对值之差大于21，则它们之间没有边相连。否则存在一条权值为它们最小公倍数的无向边。

现在问你，结点1和结点2021之间的最短路径长度是多少？

提示

邻接表gcd求最小公倍数

最短路什么算法都可以，Dijksta、Floyb....

越简单的写法，暴力起来越久...

#include <iostream>
#include <cmath>
#include <cstring>

using namespace std;

const int N = 3000;
int n = 2021;

int g[N][N];

// 求最小公约数
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

void floyb() {
    for (int t = 1; t <= n; ++ t) {
        for (int i = 1; i <= n; ++ i) {
            for (int j = 1; j <= n; ++ j) {
                g[i][j] = min(g[i][j], g[i][t] + g[t][j]);
            }
        }
    }
}

int main (){
    memset(g, 0x3f, sizeof g);
    for (int i = 1; i <= n; ++ i) {
        for (int j = 1; j <= n; ++ j) {
            if (abs(i - j) <= 21) {
                // 最大公倍数求法
                g[i][j] = i * j / gcd(i, j);
            }
        }
    }
    floyb();
    cout << g[1][n] << endl;

    return 0;
}

答案：10266837

F.时间显示

给一个时间戳，将它转换成对应的时间，但是不用显示具体年月日，只用显示日期。例如

输入：46800999

输出：13:00:00

提示

1970 年 1 月 1 日 00:00:00 到当前时刻经过的毫秒数

然后不断的作除法和求余，就能得到对应的时间了

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long LL;

int main (){
    LL t;
    cin >> t;
    int hour = (t / (1000 * 60 * 60)) % 24;
    int minute = (t / (1000 * 60)) % 60;
    int second = (t / 1000) % 60;
    
    printf("%02d:%02d:%02d", hour, minute, second);
}

G.砝码称重

你有一架天平和 $N$ 个砝码，这 $N$ 个砝码重量依次是 $W_1, W_2, · · · , W_N$。注意砝码可以放在天平两边。

请你计算一共可以称出多少种不同的重量？

思路

对于每一个砝码可以选择放在左边或右边，也可以选择不放

设有一数组 dp[i][j] = true or false，代表前 i 个物品中，能否凑出重量为 j 的物品

#include <iostream>
#include <cmath>

using namespace std;

const int N = 110, M = 200020;
int n, m, res;
int w[N], dp[N][M];

int main (){
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
        cin >> w[i];
        m += w[i]; // 砝码最多能凑出的质量是m最终的重量
    }
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++ i) {
        for (int j = 0; j <= m; ++ j) {
            // dp[i-1][j]              不使用当前砝码
            // dp[i-1][j+w[i]]         放在不同一侧
            // dp[i-1][abs(j - w[i])]  放在同的一侧
            // 如果这三者中有一种能凑出来，那么这个重量就有效
            dp[i][j] = dp[i-1][j] || dp[i-1][j+w[i]] || dp[i-1][abs(j - w[i])];
        }
    }
    
    for (int i = 1; i <= m; ++ i) {
        if (dp[n][i]) res++;
    }
    
    cout << res;
    return 0;
}

完了，后面的东西是真不会了.....