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

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

题目一视频讲解

题目二视频讲解

题目一:因数分解

B3871 [GESP202309 五级] 因数分解 - 洛谷

题目大意:

给你一个正整数n，让你把这个正整数n分解成质数的乘积，并且把质数从小到大排序，并且用题目要求的格式输出出来。

解题思路:

首先，我们可以注意到，为偶数的质数只有2，那么一个数字为偶数的时候，那它肯定包含若干个因子2，我们可以先把2筛出来。

可以不断的对这个数字除以2，同时记录2的个数。

2筛出来后，我们就筛所有的奇数。

我们可以注意到，一个数字x的因数不会超过sqrt(x)。

所以我们只需要枚举到sqrt(x）即可。

具体的细节可以看视频讲解！

代码(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);

    /*
    一眼思路:
    用质数筛,筛到根号n就行了,然后从最小开始除

    优化思路:
    1.直接遍历2,3,4,..,根号n
    2.对于每个数字,将n不断除以这个数字,统计除的个数
    
    3.最后按格式输出
    */

    i64 n;
    std::cin >> n;

    //1.
    std::vector<std::pair<i64, int>> ans;
    for (int i = 2; 1LL * i * i <= n; i++) {
        //2.
        int cnt = 0;
        while (n % i == 0) {
            n /= i;
            cnt++;
        }
        if (cnt > 0) {
            ans.push_back({i, cnt});
        }
    }
    if (n > 0) {
        ans.push_back({n, 1});
    }

    //3.
    int sz = ans.size();
    for (int i = 0; i < sz; i++) {
        auto& [num, c] = ans[i];
        if (c == 1) {
            std::cout << num;
        } else {
            std::cout << num << "^" << c;
        }
        if (i != sz - 1) {
            std::cout << " * ";
        }
    }
}

题目二:巧夺大奖

B3872 [GESP202309 五级] 巧夺大奖 - 洛谷

题目大意:

现在有n个时间段，小明可以在一个时间段内完成一款游戏，现在有n款游戏，每一款游戏都有对应的奖励分和截至时间，在截止时间内完成就可以获得奖励分。

现在请问你，小明在这n个时间段内，最多可以获得多少个奖励分。

解题思路:

关键点1：

可以在一个时间段内完成一款游戏，游戏只有n个，那么小明可以完成所有的游戏。

但是游戏有截止时间。

关键点2：

可以优先处理所有奖励值高的游戏。

关键点3：

对于一款可以游戏，可以“拖延”，在截止之前的时间段完成即可，这样就不会浪费前面的时间。

根据上述三种关键点即可得出思路，具体可以参考代码和讲解视频。

代码(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);
    
    /*
    关键点1:
    当游戏的时限符合条件,理论上小明可以完成所有游戏
    关键点2:
    我们来优先完成奖励值最高的游戏(自定义排序)
    关键点3:
    对于某一款游戏,我们尽可能的"拖延",放在时间要截至的时候完成

    具体思路:
    用一个长度为n + 1的数组used

    1.自定义排序,把奖励值高的游戏排在前面
    2.从前到后遍历,对于每一个游戏,尽可能的"拖延"
    */

    int n;
    std::cin >> n;

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

    //1.
    std::sort(a.begin(), a.end(), [](auto u, auto v) {
        return u.second > v.second;
    });

    //2.
    std::vector<bool> used(n + 1, false);
    int ans = 0;
    for (auto& [T, R] : a) {
        for (int t = T; t >= 1; t--) {
            if (!used[t]) {
                used[t] = true;
                ans += R;
                break;
            }
        }
    }

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