官方题解 | 巅峰赛31

userId_undefined
hopebetter

2026-03-02 16:20:25

发布于：浙江

113阅读
0回复
0点赞

巅峰赛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

简要题解

把每条询问的答案看成在 [1,m][1,m] 上的一个“最早满足”的位置。连通性具有单调性：若在时刻 tt 已经连通，那么在任意 t′>tt'>t 也一定连通，因此每个询问都可以二分答案。为了避免对每个询问都单独重建并查集，把所有询问的二分过程并行起来：每一轮对仍未确定的询问取中点 midmid 分桶，然后按 midmid 从小到大推进时间指针，依次把前 midmid 条边用并查集合并，在对应桶里判断这些询问是否连通，从而收缩各自的二分区间。重复约 log⁡m\log m 轮后区间收敛得到最早连通时刻；若收敛到 m+1m+1 则表示直到最后也不连通输出 −1-1，另外 u=vu=v 的询问直接输出 00。

参考代码

#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;
}
userId_undefined
去预览
0/2000

全部评论 19

热门讨论