官方题解 | 巅峰赛31
2026-03-02 16:20:25
发布于：浙江
巅峰赛31题解
本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平
| 题目编号 | 题目标题 | 难度 |
|---|---|---|
| T1 | 雾港城的神秘区域 | 入门 |
| T2 | 雾港城的符文 | 普及 - |
| T3 | 雾港学宫的括号匹配 | 普及/提高- |
| T4 | 雾港实验室的高压服务器 | 普及/提高- |
| T5 | 雾港冲刺营的队伍序列 | 普及+/提高 |
| T6 | 雾港实验室的神秘联通块 | 普及+/提高 |
T1
简要题解
关键只看信标数 k：删一条边会让连通块数量从 1 变成 2，再删一条变成 3，总之删 x 条边就会得到 x+1 个连通块。要求每块信标数 ≤1，若有 k 个信标，就至少需要 k 个连通块来“装下”它们，所以必须有 x+1≥k，也就是 x≥k−1；另一方面总能做到 k−1：把所有信标连起来的最小连通子树里，信标一定出现在叶子上，反复把一个叶子信标与子树内部相连的那条边切断，就能一次分离出一个只含 1 个信标的连通块，做 k−1 次即可把所有信标分到不同块里。于是答案就是 max(0, k−1)。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
for (int i = 0; i < k; i++) {
int x;
cin >> x;
}
for (int i = 1; i <= n - 1; i++) {
int u, v;
cin >> u >> v;
}
if (k <= 1) cout << 0 << "\n";
else cout << (k - 1) << "\n";
return 0;
}
T2
简要题解
任何长度 ≥4 的回文子串内部一定会包含一个长度为 2 的回文（相邻相等）或者长度为 3 的回文（形如 aba），所以只要把长度 2 和 3 的回文都挡住，就不会出现更长的回文。于是从左到右贪心构造保留下来的串 t：依次尝试把当前字符加到 t 末尾，如果会造成 t 的最后两位相等，或最后三位形成回文，就删掉这个字符；否则保留。这样每次只在“当前字符一加就必然违规”的情况下才删除，而且违规只可能由最新加入的字符触发，因此这个贪心的删除次数就是最少的，整体 O(n)。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
string t;
int ans = 0;
for (char ch : s) {
int m = (int)t.size();
if (m >= 1 && t[m - 1] == ch) {
ans++;
continue;
}
if (m >= 2 && t[m - 2] == ch) {
ans++;
continue;
}
t.push_back(ch);
}
cout << ans << "\n";
return 0;
}
T3
简要题解
从左到右扫描字符串，用 bal 记录当前还没被匹配的左括号数量。遇到 '(' 就 bal++；遇到 ')' 时如果 bal>0 说明能和之前某个 '(' 配对，就 bal--，否则这个 ')' 无论如何都配不到，只能删除，答案加一。扫描结束后 bal 还剩多少，表示有多少个 '(' 没法被匹配，只能删掉它们，所以答案再加上 bal。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
string s;
cin >> n >> s;
long long ans = 0;
int bal = 0;
for (char c : s) {
if (c == '(') {
bal++;
} else {
if (bal > 0) bal--;
else ans++;
}
}
ans += bal;
cout << ans << "\n";
return 0;
}
T4
简要题解
迁移发生在什么时候其实不重要：如果某个任务打算在区间中间才迁走，把它改成在 l_i 一开始就迁走只会让 A 的压力更小，不会变大，所以等价于“直接选出至多 K 个区间整段不留在 A 上”。于是问题变成删掉至多 K 个区间，让剩余区间的最大重叠数最小。我们二分答案 X，判定是否能把最大重叠压到 ≤X：按 l 从小到大扫一遍，用 multiset 维护当前还没结束的右端点集合（右端点 < 当前 l 的就删掉），每插入一个新区间后如果集合大小变成 X+1，说明此时必须删掉一个区间才能不超限，贪心删右端点最大的那个（它拖得最久，最容易影响后面），统计最少删掉的数量是否 ≤K。二分最小可行的 X 即答案。
参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 200000 + 5;
int n, K;
pair<int,int> seg[N];
bool check(int x) {
multiset<int> st;
int removed = 0;
for (int i = 0; i < n; i++) {
int a = seg[i].first;
int b = seg[i].second;
while (!st.empty() && *st.begin() < a) st.erase(st.begin());
st.insert(b);
if ((int)st.size() > x) {
st.erase(prev(st.end()));
removed++;
if (removed > K) return false;
}
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> K;
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
seg[i] = {a, b};
}
sort(seg, seg + n);
int l = 0, r = n;
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << l << "\n";
return 0;
}
T5
简要题解
要让名次尽量小，只需要让自己的最终昵称字典序尽量小，因为当昵称变得更小的时候，队伍里“小于等于它”的人数只会减少，不可能增加，所以名次是单调变好的。于是从左到右处理自己的字符串，高位比低位重要：只要还能动手并且预算够把当前位置至少降低 1 位，就应该立刻动这个位置，否则再怎么改后面都无法在字典序上超过“把更靠左的位置变小”。并且一旦决定改某个位置，为了让字典序尽可能小，当然应当在不超过预算的前提下把它尽量降到更小（同一位置降得更小不会额外消耗动手次数）。因此对每个位置 i 计算最多能降低的位数 delta=min(S[i]-'a', B/p_i)，若 delta>0 就把字符减去 delta、扣除 delta*p_i，并把可修改位置数 K 减 1。得到最终昵称 T 后，将其他人的昵称排序，用 upper_bound(T) 统计有多少昵称字典序小于等于 T（同名也算在前面，因为你报名最晚），名次就是这个数量加 1。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
long long K, B;
cin >> n >> m >> K >> B;
string s;
cin >> s;
vector<string> a(m);
for (int i = 0; i < m; i++) cin >> a[i];
vector<long long> p(n);
for (int i = 0; i < n; i++) cin >> p[i];
for (int i = 0; i < n; i++) {
if (K == 0 || B == 0) break;
if (s[i] == 'a') continue;
long long d = B / p[i];
long long need = s[i] - 'a';
if (d > need) d = need;
if (d > 0) {
s[i] = char(s[i] - (int)d);
B -= d * p[i];
K--;
}
}
sort(a.begin(), a.end());
long long pos = upper_bound(a.begin(), a.end(), s) - a.begin();
cout << (pos + 1) << "\n";
cout << s << "\n";
return 0;
}
T6
简要题解
把每条询问的答案看成在 上的一个“最早满足”的位置。连通性具有单调性：若在时刻 已经连通，那么在任意 也一定连通，因此每个询问都可以二分答案。为了避免对每个询问都单独重建并查集，把所有询问的二分过程并行起来：每一轮对仍未确定的询问取中点 分桶，然后按 从小到大推进时间指针，依次把前 条边用并查集合并，在对应桶里判断这些询问是否连通，从而收缩各自的二分区间。重复约 轮后区间收敛得到最早连通时刻；若收敛到 则表示直到最后也不连通输出 ，另外 的询问直接输出 。
参考代码
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> fa, sz;
DSU() {}
DSU(int n) { init(n); }
void init(int n) {
fa.resize(n + 1);
sz.assign(n + 1, 1);
for (int i = 1; i <= n; i++) fa[i] = i;
}
int find(int x) {
while (fa[x] != x) {
fa[x] = fa[fa[x]];
x = fa[x];
}
return x;
}
void merge(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
if (sz[a] < sz[b]) swap(a, b);
fa[b] = a;
sz[a] += sz[b];
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, q;
cin >> n >> m >> q;
vector<int> x(m + 1), y(m + 1);
for (int i = 1; i <= m; i++) cin >> x[i] >> y[i];
vector<int> a(q), b(q);
for (int i = 0; i < q; i++) cin >> a[i] >> b[i];
vector<int> L(q, 1), R(q, m + 1), ans(q, -1);
vector<int> ids;
ids.reserve(q);
for (int i = 0; i < q; i++) {
if (a[i] == b[i]) ans[i] = 0;
else ids.push_back(i);
}
vector<vector<int>> box(m + 2);
while (true) {
bool any = false;
for (int id : ids) {
if (L[id] < R[id]) {
any = true;
int mid = (L[id] + R[id]) / 2;
box[mid].push_back(id);
}
}
if (!any) break;
DSU dsu(n);
int t = 0;
for (int mid = 1; mid <= m; mid++) {
while (t < mid) {
t++;
dsu.merge(x[t], y[t]);
}
if (!box[mid].empty()) {
for (int id : box[mid]) {
if (dsu.find(a[id]) == dsu.find(b[id])) R[id] = mid;
else L[id] = mid + 1;
}
box[mid].clear();
}
}
box[m + 1].clear();
}
for (int id : ids) {
if (L[id] == m + 1) ans[id] = -1;
else ans[id] = L[id];
}
for (int i = 0; i < q; i++) cout << ans[i] << "\n";
return 0;
}
有帮助，赞一个