本文为GESP 2023年9月 六级的上机题目详细题解和讲解视频，觉得有帮助或者写的不错可以点个赞。
题目一讲解视频
GESP2023年9月六级上机题一
题目二讲解视频
题目一:小羊买饮料
B3873 [GESP202309 六级] 小杨买饮料 - 洛谷
题目大意:
现在超市一共有n种饮料，每种饮料有对应的售价c元，和容量l毫升。
现在你每种饮料只能买一瓶，并且最后要买至少L毫升饮料。
请问在这个前提下，最少花多少钱。
解题思路:
很明显的背包dp。
我们回顾一下原始的01背包问题：
有n个物品，每个物品都有价值v,和重量w，背包容量是C，我们需要在小于等于C的背包容量下获取最大的价值。
这个题目呢，可以理解成，n个物品，每个物品都有价值c和容量i，我们必须要使得最终背包的容量大于等于L，并且让价值尽可能少！
经过上述分析，很明显就能想到以下的思路：
我们令dp[i][v]表示用前i个饮料，恰好凑到v升饮料的最小花费
我们最多可以达到tot = sum(l1,l2,l3,...ln)升饮料
那么对于第i个饮料，可以不
dp[i][j] = dp[i - 1][j]
或者买
令val = 第i个饮料的价值，c = 第i个饮料的容量
dp[i][j] = dp[i - 1][j - val] + c
使得价值最低，也就是
dp[i][j] = min(dp[i][j], dp[i - 1][j - val] + c)
然后呢，最终算的结果是对于前N个饮料，容量大于等于L的时候的最小价值。
也就是我们遍历j从L 到 mx，计算dp[N][j]的最小值。这个方法即使写成一维数组也会超内存，因为tot 的最大值为5e8。
我们需要优化一下。
我们可以注意到，只要是大于等于L的部分，都可以理解成是等于L的。
那么也就是我们dp数组实际大小只需要开到L + 1就可以了，实际计算的时候把大于L的部分算成L即可。
实际实现可以是，在遍历的时候，设置一个当前j可达的一个容量cur,cur = min(L, j + val)
如果dp[i - 1][j]可以达到，那么dp[i][cur] = min(dp[i][cur], dp[i - 1][j] + cost)
代码(C++):
#include <bits/stdc++.h> using i64 = long long; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, L; std::cin >> n >> L; std::vector<int> c(n), l(n); for (int i = 0; i < n; i++) { std::cin >> c[i] >> l[i]; } int inf = INT_MAX; std::vector dp(n + 1, std::vector<int> (L + 1, inf)); dp[0][0] = 0; for (int i = 1; i <= n; i++) { //整层拷贝,表示不选 dp[i] = dp[i - 1]; int cost = c[i - 1], val = l[i - 1]; for (int j = 0; j <= L; j++) { int cur = std::min(L, j + val); if (dp[i - 1][j] != inf) { dp[i][cur] = std::min(dp[i][cur], dp[i - 1][j] + cost); } } } int ans = dp[n][L]; std::cout << (ans == inf ? "no solution" : std::to_string(ans)); }题目二:小杨的握手问题
B3874 [GESP202309 六级] 小杨的握手问题 - 洛谷
题目大意:
现在有n个学生，编号为0到n -1，现在让这n个学生按照某个顺序进入教室。
当一个同学进入教室后，他需要和所有学号小于他的进行握手。
当所有同学按照某个顺序进入教室后，请问总共的握手次数是多少？
解题思路一:归并排序
这个题目可以抽象为，求一个数组中顺序对的个数。
为了方便，我们这里就求逆序对的数量cnt，然后用总对数减去cnt即为答案
下面是归并排序的原理图，每次把当前的数组分成一半，然后分到最后的时候进行合并。
我们可以在合并的过程中求逆序对数目，比如说合并7 3，是逆序的，逆序对数目加一
合并2 3 7 16和4 9 11 24，4是小于7的，那么4肯定小于7之后所有的数字。
代码一(C++):
#include <bits/stdc++.h> using i64 = long long; i64 mSort(std::vector<int>& a, std::vector<int>& tmp, int l, int r) { if (r - l <= 1) { return 0; } i64 cnt = 0; int m = (l + r) / 2; cnt += mSort(a, tmp, l, m); cnt += mSort(a, tmp, m, r); int i = l, j = m, k = l; while (i < m && j < r) { if (a[i] <= a[j]) { tmp[k] = a[i]; k++; i++; } else { tmp[k] = a[j]; cnt += m - i; j++; k++; } } while (i < m) { tmp[k] = a[i]; i++; k++; } while (j < r) { tmp[k] = a[j]; j++; k++; } for (int i = l; i < r; i++) { a[i] = tmp[i]; } return cnt; } 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]; } std::vector<int> tmp(n); i64 tot = 1LL * n * (n - 1) / 2; i64 cnt = mSort(a, tmp, 0, n); std::cout << tot - cnt << "\n"; }解题思路二:树状数组
我们可以这么理解题目，现在有一个长度为n的数组t, 并且刚开始都为0。
我们可以持续的进行下面这个过程求顺序对个数：
现在编号为x同学进入教室
我们可以把t[x]设置成1，并且看x前面有多少个1，前面的肯定是比当前x小的，也就是求前面部分的前缀和！
那么问题抽象成了，每次把x增加1，然后求[0, x - 1]的前缀和。可以用树状数组加速处理！
代码二(C++):
#include <bits/stdc++.h> using i64 = long long; // 模板来源：https://leetcode.cn/circle/discuss/mOr1u6/ // FenwickTree 模板（1-indexed） template<typename T> class FenwickTree { std::vector<T> tree; public: // 使用下标 1 到 n FenwickTree(int n) : tree(n + 1) {} // a[i] 增加 val, i 为 1-indexed // 时间复杂度 O(log n) void update(int i, T val) { for (; i < tree.size(); i += i & -i) { tree[i] += val; } } // 求前缀和 a[1] + ... + a[i] // 时间复杂度 O(log n) T pre(int i) const { T res = 0; for (; i > 0; i &= i - 1) { res += tree[i]; } return res; } // 求区间和 a[l] + ... + a[r] T query(int l, int r) const { if (r < l) return 0; return pre(r) - pre(l - 1); } }; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n; std::cin >> n; FenwickTree<int> ft(n); i64 ans = 0; for (int i = 0; i < n; i++) { int id; std::cin >> id; id += 1; ans += ft.pre(id); ft.update(id, 1); } std::cout << ans << "\n"; }
