本文为GESP 2023年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 到 nFenwickTree(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";
}