官方题解 | 巅峰赛#34
2026-05-27 09:32:29
发布于：浙江
巅峰赛34题解
本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平
| 题目编号 | 题目标题 | 难度 |
|---|---|---|
| T1 | 午枫的宝石容器 | 普及− |
| T2 | 午枫的城市路线 | 普及/提高− |
| T3 | 午枫的对称字符 | 普及/提高− |
| T4 | 午枫的小队评分 | 普及/提高− |
| T5 | 午枫的平衡调整 | 普及/提高− |
| T6 | 午枫的路线封闭 | 普及+/提高 |
T1 午枫的宝石容器
题目大意
有 颗宝石，大小为 ，以及 个容器，容量为 。现在可以额外购买一个容量为 的容器，使得总共有 个容器。要求每个容器最多放一颗宝石，且宝石大小不超过容器容量。求最小的 使得所有宝石都能放入容器中，若无法实现输出 。
题解思路
贪心匹配即可。为了尽量让大的宝石优先匹配大的容器，先将宝石数组 和容器数组 都按从大到小排序。
然后用双指针从大到小匹配：指针 枚举宝石，指针 枚举容器。如果当前宝石 ，说明可以用这个容器装下，指针 向后移动；否则说明当前宝石无法被任何已有容器容纳，只能依赖新买的容器，于是记录这个宝石。
统计这种“装不下”的宝石个数：
- 如果为 ，说明原有容器已经够用，此时新容器可以取最小值，即 ；
- 如果为 ，说明只有一个宝石需要新容器，答案就是这个宝石的大小；
- 如果超过 ，说明至少有两个宝石需要新容器，但我们只能买一个，因此无解。
这个贪心是正确的，因为总是优先让大宝石匹配大容器，可以保证不会浪费容量。
时间复杂度为 。
参考代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 200010;
ll a[N],b[N];
bool rcmp(int a,int b){return a>b;}
int main(){
int n;cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n-1;i++) cin>>b[i];
sort(a+1,a+n+1,rcmp);
sort(b+1,b+n,rcmp);
ll cnt=0;
ll ans=0;
for(int i=1,j=1;i<=n && j<=n-1;i++){
if(a[i]<=b[j]){
j++;
continue;
}
else{
cnt++;
ans=a[i];
}
}
if(cnt==0) cout<<a[n]<<endl;
else if(cnt==1) cout<<ans<<endl;
else cout<<-1<<endl;
}
T2 午枫的城市路线
题目大意
给定一张有向图，从节点 出发，问是否存在一条路径可以回到节点 （即形成一个包含 的环）。如果存在，求这样的路径中边数最少的一条长度；否则输出 。
题解思路
由于所有边权为 ，要求最短路径，直接使用 BFS。
从节点 出发进行广度优先搜索，用数组 记录从 到达节点 的最短距离。每次从队列中取出一个节点，遍历它的所有出边，如果某个节点还没访问过，就更新距离并入队。
在 BFS 过程中，如果某条边可以从当前节点走回 ，那么就找到了一个回环，其长度就是当前节点的距离加 。由于 BFS 按层扩展，第一个找到的回环一定是最短的。
如果最终没有办法回到 ，说明不存在这样的路径，输出 。
时间复杂度为 。
参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
vector<int>v[N];
int d[N];
bool st[N];
int main(){
int n,m;cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b;cin>>a>>b;
v[a].push_back(b);
}
queue<int>q;
q.push(1);
while(!q.empty()){
int t=q.front();q.pop();
for(auto x:v[t]){
if(st[x]) continue;
st[x]=true;
d[x]=d[t]+1;
q.push(x);
}
}
if(d[1]) cout<<d[1]<<endl;
else cout<<-1<<endl;
}
T3 午枫的对称字符
题意简述
给定一个仅由大写英文字母组成的字符串 ，要求计算三元组 的数量，使得 且 是回文串。由于长度为 的回文串唯一的条件是首尾字符相同，即 ，中间字符可以是任意字符，因此本题实质上就是统计所有首尾字符相同的三元组数量。
解题思路
可以采用前缀计数的方法，遍历字符串时维护一个数组记录每个字母已经出现的次数，同时维护一个数组记录以每个字母为首字符的可形成组合数量。在遍历每个字符作为中间字符时，将当前字符对应的组合数量累加到结果中，然后更新以每个字母为首字符的组合数量，最后更新当前字符的出现次数。这样就能在一次遍历中统计出所有满足条件的三元组，时间复杂度为 ，空间复杂度为 ，足够应对 的情况。
参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
long long cnt[26],add[26];
int main(){
string s;cin>>s;s=' '+s;
long long res=0;
for(int i=1;i<(int)s.size();i++){
res+=add[s[i]-'A'];
for(int j=0;j<26;j++){
add[j]+=cnt[j];
}
cnt[s[i]-'A']++;
}
cout<<res<<endl;
}
T4 午枫的小队评分
题意简述
有 名选手，每位选手都有实力值 和消耗值 。需要从中选出一个大小为 的小队 ，小队评分定义为：
目标是选择一个小队，使得评分尽可能小，并输出最小评分。
解题思路
首先将选手按照实力值 从小到大排序。然后考虑当某个选手 的实力值成为小队中最大实力值时，如何选择另外 名选手以使得消耗值之和最小。为了高效计算，可以使用一个大根堆维护当前已选择的 个消耗值最大的选手，如果当前堆中超过 个元素，就弹出最大的，这样保证堆中始终保存消耗值最小的 个候选成员。每遍历一个选手，将其作为最大实力值候选时，累加堆中消耗值与自身消耗值，然后计算评分并更新最小值。这样遍历一次即可得到最优解，时间复杂度为 ，空间复杂度为 。
参考代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define PII pair<ll,ll>
const int N = 200010;
const ll INF = 1e18+10;
PII p[N];
void solve(){
int n,k;cin>>n>>k;
for(int i=1;i<=n;i++) cin>>p[i].first;
for(int i=1;i<=n;i++) cin>>p[i].second;
sort(p+1,p+n+1);
priority_queue<ll>q;
ll ans=INF;
ll sum=0;
for(int i=1;i<=n;i++){
sum+=p[i].second;
q.push(p[i].second);
if(q.size()>k){
auto t=q.top();q.pop();
sum-=t;
}
if(q.size()==k) ans=min(ans,p[i].first*sum);
}
cout<<ans<<endl;
}
int main(){
int T;cin>>T;
while(T--){
solve();
}
}
T5 午枫的平衡调整
题意简述
给定 名成员，每名成员属于三个小组之一并有一个贡献值。希望通过调整部分成员的小组归属，使得三个小组的总贡献值完全相等。每次调整只能将某个成员移动到另一个已有的小组中，目标是判断是否可以实现平衡，如果可以，则输出最少需要调整的人数，否则输出 。
解题思路
首先计算所有成员贡献值之和，如果不能被 整除，则无法实现平衡，直接输出 。设每组的目标贡献值为总和的三分之一。使用三维动态规划，状态为 ，表示前 个成员中，第一组总贡献为 ，第二组总贡献为 时所需的最少调整人数。遍历每个成员时，可以选择将其分配到任意一组，累加调整次数（若成员当前组与选择组不同则加一），更新状态。最终 即为最少调整人数，如果无法达到则为无穷大，输出 -1。
参考代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = 1e18+10;
const int N = 110, M = 510;
ll a[N],b[N];
ll dp[N][M][M];
int main(){
ll n;cin>>n;
ll sum=0;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
sum+=b[i];
}
if(sum%3!=0){
cout<<-1<<endl;
return 0;
}
for(int i=0;i<=n;i++){
for(int j=0;j<=sum/3;j++){
for(int k=0;k<=sum/3;k++){
dp[i][j][k]=INF;
}
}
}
dp[0][0][0]=0;
for(int i=1;i<=n;i++){
for(int j=0;j<=sum/3;j++){
for(int k=0;k<=sum/3;k++){
if(j-b[i]>=0) dp[i][j][k]=min(dp[i][j][k],dp[i-1][j-b[i]][k]+(a[i]!=1));
if(k-b[i]>=0) dp[i][j][k]=min(dp[i][j][k],dp[i-1][j][k-b[i]]+(a[i]!=2));
dp[i][j][k]=min(dp[i][j][k],dp[i-1][j][k]+(a[i]!=3));
}
}
}
if(dp[n][sum/3][sum/3]==INF) cout<<-1<<endl;
else cout<<dp[n][sum/3][sum/3]<<endl;
}
T6 午枫的路线封闭
题意简述
给定 个地点和 条双向路线，每条路线有通行代价。随后有 个操作，包含封闭某条路线或询问两点间最小通行代价。封闭操作总次数不超过 。要求按操作顺序处理，每次询问输出当前未封闭路线下的最短路径，若无法到达输出 。
解题思路
由于地点数量 ，可以使用 Floyd 算法处理所有点对最短路径。关键是封闭操作较少，因此可以采用离线处理策略：先将所有封闭操作标记，并从最终状态的图出发，计算全局最短路径。然后逆序处理操作序列，每遇到一次封闭操作就“恢复”对应边，并更新受影响的最短路径；遇到查询操作直接读取当前最短路径表即可。这样只需在逆序处理时更新路径，而不必每次从头计算，保证在 时间内完成。最终按正序输出查询结果即可。
参考代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = 1e18+10;
const int N = 310;
ll n,m,q;
struct E{
ll a,b,c,is;
};
struct qry{
ll op,x,y;
};
ll d[N][N];
int main(){
cin>>n>>m>>q;
vector<E>edg(m+1);
for(int i=1;i<=m;i++){
ll a,b,c;cin>>a>>b>>c;
edg[i]={a,b,c,1};
}
vector<qry>Q;
while(q--){
ll op;cin>>op;
if(op==1){
ll x;cin>>x;
Q.push_back({op,x,-1});
edg[x].is=0;
}
else{
ll x,y;cin>>x>>y;
Q.push_back({op,x,y});
}
}
reverse(Q.begin(),Q.end());
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
d[i][j]=INF;
}
}
for(int i=1;i<=n;i++) d[i][i]=0;
for(int i=1;i<=m;i++){
if(!edg[i].is) continue;
auto [a,b,c,_]=edg[i];
d[a][b]=min(d[a][b],c);
d[b][a]=min(d[b][a],c);
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
}
}
vector<ll>ans;
for(auto [op,x,y]:Q){
if(op==1){
auto [a,b,c,_]=edg[x];
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
d[i][j]=min(d[i][j],d[i][a]+c+d[b][j]);
d[i][j]=min(d[i][j],d[i][b]+c+d[a][j]);
}
}
}
else{
if(d[x][y]==INF) ans.push_back(-1);
else ans.push_back(d[x][y]);
}
}
reverse(ans.begin(),ans.end());
for(auto c:ans) cout<<c<<endl;
}
有帮助，赞一个