[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,..,根号n2.对于每个数字,将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的数组used1.自定义排序,把奖励值高的游戏排在前面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";
}