官方题解 | 巅峰赛#38题解
2026-09-16 11:46:00
发布于：浙江
巅峰赛38题解
本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平
| 题目编号 | 题目标题 | 难度 |
|---|---|---|
| T1 | 山间烤羊 | 普及/提高- |
| T2 | 山间营地音乐会 | 普及/提高- |
| T3 | 山间抹茶宴 | 普及/提高- |
| T4 | 山间双人探险 | 普及/提高- |
| T5 | 深山能源网络 | 普及+/提高 |
| T6 | 山中补给站 | 普及+/提高 |
T1 山间烤羊
题意简述
初始美味值为 ，每次炭烤增加 （无使用次数限制），另有三种香料 ，每种最多使用一次，使用香料增加对应香气值且不耗时。求达到美味值 所需的最少炭烤分钟数。
解题思路
因为炭烤每分钟增加 ，所以最少炭烤时间等价于选择若干种香料（共 种组合），使香料总和不大于 ，且 减去香料总和最小。枚举所有香料组合，计算 的最小值即为答案。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
long long k, a, b, c;
cin >> k >> a >> b >> c;
long long arr[3] = {a, b, c};
long long ans = k;
for (int mask = 0; mask < (1 << 3); mask++) {
long long sum = 0;
for (int i = 0; i < 3; i++) {
if (mask & (1 << i)) sum += arr[i];
}
if (sum <= k) {
ans = min(ans, k - sum);
}
}
cout << ans << '\n';
}
return 0;
}
T2 山间营地音乐会
题意简述
乐队需要五个位置：主唱、贝斯、鼓、吉他、键盘。现有 个主唱候选人， 个贝斯候选人， 个鼓手候选人， 个吉他手候选人， 个键盘手候选人。每个位置选一个人，同一个人不能兼两个位置，求不同乐队方案数。
解题思路
主唱、贝斯、鼓手的选择相互独立，分别为 种。对于吉他手和键盘手，从 人中选出 人，但其中两人都选键盘手的方案无效（因为键盘只有一个位置），所以有效方案数为从 人中选 人减去从 人中选 人，即 。答案即为 。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int a, b, c, d, e;
cin >> a >> b >> c >> d >> e;
long long ways = 1LL * a * b * c;
long long guitar_keyboard = 1LL * (d + e) * (d + e - 1) / 2 - 1LL * e * (e - 1) / 2;
cout << ways * guitar_keyboard << '\n';
}
return 0;
}
T3 山间抹茶宴
题意简述
有 个甜品，每个有抹茶浓度 和冰度 。选择一个连续区间，要求区间内每个甜品的 都相等。区间美味值定义为 ，即区间内 之和乘以区间长度。求所有满足条件的区间中的最大美味值。
解题思路
令 。满足条件的区间必须是 值相同的连续段。对于每个连续的相同 值的段，我们需要计算该段内所有子区间的 的最大值。由于段内 值相同，但 不同，最大美味值出现在整个段上，因为 均为正数，扩大区间会使 增大。因此对每个连续段，取整个段，计算段长 与 前缀和之差乘积，取最大值。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<long long> a(n + 1), pre(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
pre[i] = pre[i - 1] + a[i];
}
vector<int> b(n + 1);
long long ans = 0;
int len = 1;
int last = 0;
for (int i = 1; i <= n; i++) {
cin >> b[i];
int cur = a[i] + b[i];
if (i == 1) {
last = cur;
len = 1;
} else if (cur == last) {
len++;
} else {
ans = max(ans, len * (pre[i - 1] - pre[i - 1 - len]));
last = cur;
len = 1;
}
}
ans = max(ans, len * (pre[n] - pre[n - len]));
cout << ans << '\n';
}
return 0;
}
T4 山间双人探险
题意简述
有 个石台，编号 到 。第 个石台为红色，是红叶的起点。每个石台最多踩一次。红叶只能跳到红色石台，墨岩只能跳到黑色石台。两人轮流跳跃，红叶先跳。若当前轮到的探险家无可用石台则结束。求能获得的最大总危险系数之和。
解题思路
由于跳跃顺序固定：红、黑、红、黑……，且可以跳到任意未被踩踏的对应颜色石台，最优策略是每次从当前颜色中选取危险系数最大的石台。将红色石台（不包括起点）和黑色石台分别排序，按从大到小交替取数，取到某颜色无剩余时停止。累加所有取到的值。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
string s;
cin >> s;
s = " " + s;
vector<int> R, B;
for (int i = 1; i <= n; i++) {
if (s[i] == 'R') R.push_back(a[i]);
else B.push_back(a[i]);
}
sort(R.begin(), R.end(), greater<int>());
sort(B.begin(), B.end(), greater<int>());
long long ans = 0;
int i = 0, j = 0;
while (true) {
if (j < (int)B.size()) {
ans += B[j++];
} else break;
if (i < (int)R.size()) {
ans += R[i++];
} else break;
}
cout << ans << '\n';
}
return 0;
}
T5 深山能源网络
题意简述
有 个节点和 个项目，每个项目可选择连接两个端点 或 中的一个，获得能量 。每个节点最多参与一个项目，求最大总能量。
解题思路
将每个项目视为一条边 ，权值为 。问题等价于在图中选择若干条边，使得每个节点的度数不超过 ，即选出一个边集构成一个匹配（但允许有环？注意每个节点最多选一条边，所以实际选出的边集形成若干个连通块，每个连通块要么是一棵树（边数 = 点数 - 1），要么是一个基环树（边数 = 点数）。由于项目可以在两个端点中任选一个，相当于每条边可以消耗一个端点，因此每个连通块内最多可以选的点数为节点数，但必须满足边数不超过节点数（否则无法分配）。按权值从大到小排序，用并查集维护连通块，记录每个块的点数和已选边数，若加入当前边不违反“边数 < 点数”的约束则选择该边并更新。
参考代码
#include <bits/stdc++.h>
using namespace std;
struct Edge {
int u, v, w;
};
struct DSU {
vector<int> fa, node, edge;
DSU(int n) {
fa.resize(n + 1);
node.assign(n + 1, 1);
edge.assign(n + 1, 0);
iota(fa.begin(), fa.end(), 0);
}
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return x;
if (node[x] < node[y]) swap(x, y);
fa[y] = x;
node[x] += node[y];
edge[x] += edge[y];
return x;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
vector<Edge> e(m);
for (int i = 0; i < m; i++) {
cin >> e[i].u >> e[i].v >> e[i].w;
}
sort(e.begin(), e.end(), [](Edge a, Edge b) {
return a.w > b.w;
});
DSU dsu(n);
long long ans = 0;
for (auto [u, v, w] : e) {
int fu = dsu.find(u), fv = dsu.find(v);
if (fu == fv) {
if (dsu.edge[fu] < dsu.node[fu]) {
ans += w;
dsu.edge[fu]++;
}
} else {
if (dsu.edge[fu] < dsu.node[fu] || dsu.edge[fv] < dsu.node[fv]) {
ans += w;
int root = dsu.unite(u, v);
dsu.edge[root]++;
}
}
}
cout << ans << '\n';
}
return 0;
}
T6 山中补给站
题意简述
有 种物资，每种价格 、体积为 ，可无限购买。求在总花费不超过 的前提下，恰好装满体积为 的背包的方案数，对 取模。
解题思路
完全背包计数问题。设 表示花费为 、已选 件物品的方案数。对每种物资 ，枚举花费 从 到 ，枚举数量 从 到 ，进行完全背包转移：。最后累加所有花费 且 的方案数。
参考代码
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int dp[405][405];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n, m, V;
cin >> n >> m >> V;
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
int g;
cin >> g;
for (int cost = g; cost <= V; cost++) {
for (int cnt = 1; cnt <= m; cnt++) {
dp[cost][cnt] = (dp[cost][cnt] + dp[cost - g][cnt - 1]) % MOD;
}
}
}
int ans = 0;
for (int cost = 1; cost <= V; cost++) {
ans = (ans + dp[cost][m]) % MOD;
}
cout << ans << '\n';
}
return 0;
}
有帮助，赞一个