官方题解 | 巅峰赛#38题解

NoonMaple

2026-09-16 11:46:00

发布于：浙江

203阅读

0回复

0点赞

巅峰赛38题解

本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平

题目编号	题目标题	难度
T1	山间烤羊	普及/提高-
T2	山间营地音乐会	普及/提高-
T3	山间抹茶宴	普及/提高-
T4	山间双人探险	普及/提高-
T5	深山能源网络	普及+/提高
T6	山中补给站	普及+/提高

T1 山间烤羊

题意简述

初始美味值为 $0$ ，每次炭烤增加 $1$ （无使用次数限制），另有三种香料 $a,b,c$ ，每种最多使用一次，使用香料增加对应香气值且不耗时。求达到美味值 $k$ 所需的最少炭烤分钟数。

解题思路

因为炭烤每分钟增加 $1$ ，所以最少炭烤时间等价于选择若干种香料（共 $2^3=8$ 种组合），使香料总和不大于 $k$ ，且 $k$ 减去香料总和最小。枚举所有香料组合，计算 $k - sum$ 的最小值即为答案。

参考代码

#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 山间营地音乐会

题意简述

乐队需要五个位置：主唱、贝斯、鼓、吉他、键盘。现有 $a$ 个主唱候选人， $b$ 个贝斯候选人， $c$ 个鼓手候选人， $d$ 个吉他手候选人， $e$ 个键盘手候选人。每个位置选一个人，同一个人不能兼两个位置，求不同乐队方案数。

解题思路

主唱、贝斯、鼓手的选择相互独立，分别为 $a,b,c$ 种。对于吉他手和键盘手，从 $d+e$ 人中选出 $2$ 人，但其中两人都选键盘手的方案无效（因为键盘只有一个位置），所以有效方案数为从 $d+e$ 人中选 $2$ 人减去从 $e$ 人中选 $2$ 人，即 $\binom{d+e}{2} - \binom{e}{2}$ 。答案即为 $a \times b \times c \times (\binom{d+e}{2} - \binom{e}{2})$ 。

参考代码

#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 山间抹茶宴

题意简述

有 $n$ 个甜品，每个有抹茶浓度 $a_i$ 和冰度 $b_i$ 。选择一个连续区间，要求区间内每个甜品的 $a_i + b_i$ 都相等。区间美味值定义为 $\sum_{i=l}^r a_i \times (r-l+1)$ ，即区间内 $a_i$ 之和乘以区间长度。求所有满足条件的区间中的最大美味值。

解题思路

令 $s_i = a_i + b_i$ 。满足条件的区间必须是 $s$ 值相同的连续段。对于每个连续的相同 $s$ 值的段，我们需要计算该段内所有子区间的 $(\sum a_i) \times len$ 的最大值。由于段内 $s$ 值相同，但 $a_i$ 不同，最大美味值出现在整个段上，因为 $a_i$ 均为正数，扩大区间会使 $(\sum a_i) \times len$ 增大。因此对每个连续段，取整个段，计算段长 $len$ 与 $a_i$ 前缀和之差乘积，取最大值。

参考代码

#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 山间双人探险

题意简述

有 $n+1$ 个石台，编号 $0$ 到 $n$ 。第 $0$ 个石台为红色，是红叶的起点。每个石台最多踩一次。红叶只能跳到红色石台，墨岩只能跳到黑色石台。两人轮流跳跃，红叶先跳。若当前轮到的探险家无可用石台则结束。求能获得的最大总危险系数之和。

解题思路

由于跳跃顺序固定：红、黑、红、黑……，且可以跳到任意未被踩踏的对应颜色石台，最优策略是每次从当前颜色中选取危险系数最大的石台。将红色石台（不包括起点）和黑色石台分别排序，按从大到小交替取数，取到某颜色无剩余时停止。累加所有取到的值。

参考代码

#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 深山能源网络

题意简述

有 $n$ 个节点和 $m$ 个项目，每个项目可选择连接两个端点 $a_i$ 或 $b_i$ 中的一个，获得能量 $w_i$ 。每个节点最多参与一个项目，求最大总能量。

解题思路

将每个项目视为一条边 $(a_i, b_i)$ ，权值为 $w_i$ 。问题等价于在图中选择若干条边，使得每个节点的度数不超过 $1$ ，即选出一个边集构成一个匹配（但允许有环？注意每个节点最多选一条边，所以实际选出的边集形成若干个连通块，每个连通块要么是一棵树（边数 = 点数 - 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 山中补给站

题意简述

有 $n$ 种物资，每种价格 $g_i$ 、体积为 $1$ ，可无限购买。求在总花费不超过 $V$ 的前提下，恰好装满体积为 $m$ 的背包的方案数，对 $10^9+7$ 取模。

解题思路

完全背包计数问题。设 $dp[j][k]$ 表示花费为 $j$ 、已选 $k$ 件物品的方案数。对每种物资 $g_i$ ，枚举花费 $j$ 从 $g_i$ 到 $V$ ，枚举数量 $k$ 从 $1$ 到 $m$ ，进行完全背包转移： $dp[j][k] += dp[j-g_i][k-1]$ 。最后累加所有花费 $\le V$ 且 $k=m$ 的方案数。

参考代码

#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;
}