本文为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";
}