[GESP2023012 五级] 2023年12月GESP C++五级上机题题解，附带讲解视频！

本文为GESP 2023年12月 五级的上机题目详细题解和讲解视频，觉得有帮助或者写的不错可以点个赞。

视频讲解制作中！

题目一:小杨的幸运数

B3929 [GESP202312 五级] 小杨的幸运数 - 洛谷

题目大意:

题目定义了大于a的完全平方数都是超级幸运数，然后呢超级幸运数字的整数倍的数字都是幸运数字。

然后题目再定义了一个幸运化的操作，就是把一个数字持续的加一，直到它变成幸运数字。

现在给了你n个数字，让你判断。

如果这个数字本来就是幸运数，那么我们就输出lucky。

如果这个数字不是幸运数字，就把它幸运化，然后再输出。

解题思路:

首先我们很容易想到，如果有这样一个幸运数的数组nums，我们每次遇到一个数字n的时候，我们就方便判断了。

如果有一个包含所有幸运数的数组nums的话，我们很容易想到如下思路:

比如如果这个n小于a，那就需要幸运化，我们就在数组nums中查找一个刚好大于等于a的数字，就是我们想要的幸运数，如果n大于a，我们只需要在数组nums中查找一个大于等于n的数字num，如果num == n,那么n不需要幸运化，直接输出lucky，否则这个数字就是幸运化后的数字。

查找的话，我们可以用二分查找加快速度。

所以现在我们的主要任务是生成nums数组。

这个题目中a的范围是a <= 1e6，每一个数字x的范围为x <= 1e6 + 1。

那么也就是我们要找出第一个大于等于x的幸运数,这个数作为上界mx。

我们注意到(其实也可以暴力生成): 这个数字的为1e6 + 4。

因为4是完全平方数，1e6 + 4是4的倍数。

我们可以用类似于质数筛的方式来选出所有的幸运数。

定义两个数组is(mx + 1)和t，is[i]表示i是否为幸运数，然后t里面放实际的幸运数。

从a到mx，遇到一个完全平方数，我们就对把这个数字的若干倍（但是小于mx）都变成true;

上面的操作的时间复杂度可以近似于O(mx * p)，p可以看作是一个很小的常数，约等于1.6，具体证明过程会在视频里面展示，由于涉及到高数知识，不是5级的知识点，只需要知道近似于O(mx)即可。

代码(C++):

#include <bits/stdc++.h>
//https://blog.csdn.net/2401_83669813
using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int a, N;
    std::cin >> a >> N;

    const int mx = 1e6 + 4;
    std::vector<bool> is(mx + 1, false);
    for (int i = a; i <= mx; i++) {
        int s = std::sqrt(i);
        if (s * s == i) {
            for (i64 j = 1; j * i <= mx; j++) {
                is[i * j] = true;
            }
        }
    }

    std::vector<int> t;
    for (int i = 1; i <= mx; i++) {
        if (is[i]) {
            t.push_back(i);
        }
    }

    int ans1 = *std::lower_bound(t.begin(), t.end(), a);

    while (N--) {
        int x;
        std::cin >> x;

        if (x < a) {
            std::cout << ans1 << "\n";
        } else if (is[x]) {
            std::cout << "lucky\n";
        } else {
            int ans2 = *std::lower_bound(t.begin(), t.end(), x);
            std::cout << ans2 << "\n";
        }
    }
}

题目二:烹饪问题

B3930 [GESP202312 五级] 烹饪问题 - 洛谷

题目大意:

给你n个数字a1,a2,...,an。你需要在这n个数字中找出两个数字(x, y)，使得x & y的值尽可能大，输出这个最大值，n <= 1e6，ai在int范围内。

解题思路:

关键点1:

所有的数字都在Int范围内，那么答案也是一个int类型的数字

关键点2:

&运算是都为1的时候,这一位才是1.

关键点3:

要使得数字尽可能的大，两个数字的高位的1尽可能位置一样！

得出思路：

我们遍历从高到低遍历每一位，也就是遍历bit从31到0，定义变量mask

首先把mask的第bit位设置成1，然后遍历整个数组，看看会不会有两个数字bit位置都有1，如果有

即可保留这个1,这样我们就可以尽可能的保留高位的1！

代码(C++):

#include <bits/stdc++.h>
//https://blog.csdn.net/2401_83669813 csdn: @立志成为算法讲师

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    int mask = 0;
    for (int bit = 31; bit >= 0; bit--) {
        int cur = mask | (1 << bit);
        int cnt = 0;
        for (int x : a) {
            if ((cur & x) == cur) {
                cnt++;
            }
            if (cnt == 2) {
                break;
            }
        }
        if (cnt == 2) {
            mask = cur;
        }
    }

    std::cout << mask << "\n";
}