官方题解 | 巅峰赛#33

userId_undefined
NoonMaple
时空双修者7月全勤卷王出道萌新题解仙人快乐小狗传道者

2026-05-03 16:32:11

发布于：浙江

43阅读
0回复
0点赞

巅峰赛33题解

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

题目编号 题目标题 难度
T1 双色序判定 普及-
T2 阈值远征 普及/提高-
T3 更优括号子序列 普及/提高-
T4 单向配送 普及+/提高
T5 异或后缀排列 普及+/提高
T6 回文区间翻转 提高+/省选-

T1 双色序判定

题意简述

给定一个长度为 nn 的排列（元素互不相同），需要给每个位置染成两种颜色之一，使得满足两个条件：一是在原序列中相邻位置颜色必须不同；二是将所有元素按数值从小到大排序后，相邻元素的颜色仍然不同。要求判断是否存在这样的染色方案。

解题思路

先看第一个条件：原序列相邻位置颜色不同，这实际上已经把染色方式基本确定了。因为只有两种颜色，所以一旦第一个位置确定，后面的位置颜色就必须交替出现，也就是说整个序列的染色方案只能是“黑白黑白……”或者“白黑白黑……”。

换句话说，本质上就是按照下标奇偶性来染色，比如让 i mod 2i \bmod 2 决定颜色。

接下来关键是第二个条件：将序列按数值从小到大排序后，相邻元素颜色也必须不同。我们可以把每个数连同它原来的位置一起排序，然后检查排序后的相邻两个元素，它们原来的位置奇偶性（也就是颜色）是否不同。

如果存在一对相邻元素，它们排序后挨在一起，但原下标奇偶性相同，那么它们颜色相同，就不满足要求，答案为 NO；否则如果所有相邻对都满足奇偶不同，则说明这种交替染色是合法的，答案为 YES。

由于另一种染色（整体翻转颜色）本质是一样的，所以只需要检查一种情况即可。

时间复杂度主要是排序，为 O(nlog⁡n)O(n \log n)，在数据范围内完全没问题。

参考代码

#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<pair<int,int>> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i].first;
            a[i].second = i & 1; // 原序列按奇偶位置染色
        }

        sort(a.begin(), a.end());
        bool ok = true;
        for (int i = 1; i < n; ++i) {
            if (a[i].second == a[i - 1].second) {
                ok = false;
                break;
            }
        }
        cout << (ok ? "YES" : "NO") << '\n';
    }
    return 0;
}

T2 阈值远征

题意简述

有 nn 把武器，第 ii 把威力为 aia_i，还有 nn 个关卡，第 ii 关需要恰好 bib_i 次攻击才能通过。你需要先选择一个难度值 xx，所有威力小于 xx 的武器会失效，其余武器每把只能使用一次。

然后按顺序挑战关卡：如果当前剩余武器数不少于 bib_i，就消耗 bib_i 把通过该关，否则停止。最终得分为：

score=x×(通过的关卡数)\text{score} = x \times (\text{通过的关卡数})

求最大得分。

解题思路

关键在于如何选择 xx。注意到如果确定了 xx，那么所有满足 ai≥xa_i \ge x 的武器都可以用，也就是说我们实际拥有的武器数量就是“威力不小于 xx 的武器个数”。

因此可以先将数组 aa 从大到小排序。假设当前考虑第 ii 大的武器作为阈值 x=aix = a_i，那么此时我们一共有 ii 把可用武器。

接下来问题变成：用这 ii 把武器，最多可以通过多少关。由于必须按顺序打关卡，我们可以贪心地从前往后尝试，用一个变量记录已经通过的关卡数 levellevel，以及通过这些关卡一共消耗的武器数量 needneed。

当我们尝试多通过一关时，只要满足：

need+blevel+1≤ineed + b_{level+1} \le i

就说明当前武器数足够，可以继续通过这一关，并更新 needneed 和 levellevel。

随着 ii 增大，可用武器变多，能通过的关卡数也单调不减，因此用双指针或类似滑动方式维护这个过程即可。

对于每个 ii，计算当前得分：

ai×levela_i \times level

取最大值作为答案。

整体时间复杂度是排序 O(nlog⁡n)O(n \log n) 加上线性扫描 O(n)O(n)，可以通过所有数据。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

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), b(n + 1);
        for (int i = 1; i <= n; ++i) cin >> a[i];
        for (int i = 1; i <= n; ++i) cin >> b[i];

        sort(a.begin() + 1, a.end(), greater<int>());

        int level = 0;
        ll need = 0;
        ll ans = 0;

        for (int i = 1; i <= n; ++i) {
            while (level < n && need + b[level + 1] <= i) {
                ++level;
                need += b[level];
            }
            ans = max(ans, 1LL * a[i] * level);
        }

        cout << ans << '\n';
    }
    return 0;
}

T3 更优括号子序列

题意简述

给定一个长度为 $n $$ 的合法括号序列 ss，需要从中删除若干字符（保留相对顺序），得到一个非空子序列 tt，要求：

  • tt 仍然是合法括号序列；
  • tt 在字典序意义下比 ss 更优（即要么 ss 是 tt 的前缀，要么在第一个不同的位置 tt 放的是 '(' 而 ss 放的是 ')'）。

求满足条件的 tt 的最大长度，如果不存在输出 −1-1。

解题思路

关键在于理解“更优”的定义。因为括号序列只包含 '(' 和 ')'，而 '(' 的字典序更小，所以本质就是希望在尽量靠前的位置，把原本的 ')' 换成 '('。

但我们只能通过“删除字符”来实现这一点。也就是说，我们要找到一个位置 $$ i $$，使得 $$ s_i = ')' $$，然后在它后面找到一个 '(' 来“提前”作为子序列中的位置，从而让新序列在这个位置变成 '('，达到更优。

假设我们选定一个位置 ii（满足 si=′)′s_i = ')'），然后找到后面最近的一个 '('，位置为 jj。为了让这个 '(' 提前，我们必须删除区间 [i,j][i, j] 内的所有字符（否则顺序无法改变），这样相当于删除了长度为：

need=j−ineed = j - i

但删除这些字符后，还要保证剩下的序列仍然是合法括号序列。由于删除了若干个括号，为了维持匹配关系，还需要在后面再删除同样数量的 '(' 来平衡。

因此我们需要在 jj 之后，至少还有 needneed 个 '(' 可以删除（用于匹配之前删除的 ')'），也就是满足：

suf_open[j+1]≥need{suf\_open}[j+1] \ge need

如果这个条件成立，那么我们可以构造一个合法的更优子序列，其长度为：

n−2×needn - 2 \times need

枚举所有这样的 ii，取最大值即可。

为了快速找到每个位置之后的最近 '('，可以预处理一个数组 nxt[i]nxt[i] 表示从 ii 开始往后的第一个 '(' 的位置；同时用 suf_open[i]suf\_open[i] 表示从 ii 到结尾的 '(' 数量。

整体时间复杂度为 O(n)O(n)，对每组数据线性处理即可。

参考代码

#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;
        string s;
        cin >> n >> s;

        vector<int> nxt(n + 2, n + 1);
        vector<int> suf_open(n + 2, 0);

        for (int i = n - 1; i >= 0; --i) {
            nxt[i] = (s[i] == '(' ? i : nxt[i + 1]);
            suf_open[i] = suf_open[i + 1] + (s[i] == '(');
        }

        int ans = -1;
        for (int i = 0; i < n; ++i) {
            if (s[i] != ')') continue;
            int j = nxt[i];
            if (j > n - 1) continue;
            int need = j - i;
            if (suf_open[j + 1] >= need) {
                ans = max(ans, n - 2 * need);
            }
        }

        cout << ans << '\n';
    }
    return 0;
}

T4 单向配送

题意简述

在平面上从起点 (Ax,Ay)(A_x, A_y) 出发，最终到达终点 (Bx,By)(B_x, B_y)，途中需要访问所有给定的投递点。每次只能向右、向上或向下移动一步（即 xx 只能递增，yy 可以上下变化），每步代价为 1。

要求在满足访问所有点的前提下，使总移动步数最小。

解题思路

由于只能向右移动（xx 单调递增），所以整个路径在 xx 轴上是从 AxA_x 一路走到 BxB_x，中途不会回头。因此可以把问题看成按 xx 坐标分组，从左到右依次处理。

对于同一个 xx 坐标上的所有点，我们必须把这些点全部访问。因为在同一列中可以上下移动，所以最优策略一定是从这一列的某个端点走到另一个端点，把这一列的所有点“一次扫完”。因此我们只需要关心这一列的最小 yy 和最大 yy，记为区间 [low,high][low, high]。

于是问题转化为：有若干列，每列对应一个区间 [lowi,highi][low_i, high_i]，我们从左往右依次经过这些列，每一列必须完整走一遍（代价是 highi−lowihigh_i - low_i），并且需要考虑列与列之间的移动代价。

设 dp[i][0]dp[i][0] 表示处理到第 ii 列，最后停在这一列的上端点 highihigh_i 的最小代价；dp[i][1]dp[i][1] 表示停在下端点 lowilow_i 的最小代价。

转移时，从上一列的两个端点转移到当前列的某个端点，取最小值。例如转移到当前列的下端点：

dp[i][1]=min⁡(dp[i−1][0]+dist((xi−1,highi−1),(xi,lowi)),dp[i−1][1]+dist((xi−1,lowi−1),(xi,lowi)))+(highi−lowi)dp[i][1] = \min \Big( dp[i-1][0] + \text{dist}((x_{i-1}, high_{i-1}), (x_i, low_i)), dp[i-1][1] + \text{dist}((x_{i-1}, low_{i-1}), (x_i, low_i)) \Big) + (high_i - low_i)

到上端点同理。

其中距离函数是曼哈顿距离：

dist=∣x1−x2∣+∣y1−y2∣\text{dist} = |x_1 - x_2| + |y_1 - y_2|

注意起点和终点也可以看作特殊的列加入处理。

最终答案是最后一列两种状态的最小值。

整体复杂度主要是排序或 map 处理，为 O(nlog⁡n)O(n \log n)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct Group {
    ll x;
    ll low;
    ll high;
};

static inline ll dist(ll x1, ll y1, ll x2, ll y2) {
    return llabs(x1 - x2) + llabs(y1 - y2);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        ll Ax, Ay, Bx, By;
        cin >> n >> Ax >> Ay >> Bx >> By;

        vector<ll> xs(n), ys(n);
        for (int i = 0; i < n; ++i) cin >> xs[i];
        for (int i = 0; i < n; ++i) cin >> ys[i];

        map<ll, pair<ll,ll>> mp;
        mp[Ax] = {Ay, Ay};
        mp[Bx] = {By, By};

        for (int i = 0; i < n; ++i) {
            auto it = mp.find(xs[i]);
            if (it == mp.end()) {
                mp[xs[i]] = {ys[i], ys[i]};
            } else {
                it->second.first = min(it->second.first, ys[i]);
                it->second.second = max(it->second.second, ys[i]);
            }
        }

        vector<Group> g;
        g.reserve(mp.size());
        for (auto &kv : mp) {
            g.push_back({kv.first, kv.second.first, kv.second.second});
        }

        int m = (int)g.size();
        vector<array<ll,2>> dp(m, {0, 0});
        for (int i = 1; i < m; ++i) {
            ll need = g[i].high - g[i].low;
            dp[i][0] = min(
                dp[i - 1][0] + dist(g[i - 1].x, g[i - 1].high, g[i].x, g[i].low),
                dp[i - 1][1] + dist(g[i - 1].x, g[i - 1].low,  g[i].x, g[i].low)
            ) + need;
            dp[i][1] = min(
                dp[i - 1][0] + dist(g[i - 1].x, g[i - 1].high, g[i].x, g[i].high),
                dp[i - 1][1] + dist(g[i - 1].x, g[i - 1].low,  g[i].x, g[i].high)
            ) + need;
        }

        cout << min(dp[m - 1][0], dp[m - 1][1]) << '\n';
    }
    return 0;
}

T5 异或后缀排列

题意简述

给定一个整数 nn，需要构造一个 1∼n1 \sim n 的排列 pp，满足对于每个位置 ii（1≤i≤n−11 \le i \le n-1），在后缀区间 [i,n][i,n] 中存在某个位置 jj，使得：

pi=pj⊕ip_i = p_j \oplus i

如果存在这样的排列输出任意一个，否则输出 −1-1。

解题思路

先考虑什么时候无解。一个关键结论是：当 nn 是 2 的幂时一定无解。这是因为异或的结构在二进制下具有分层性质，当范围刚好是 [1,2k][1, 2^k] 时，无法构造满足所有位置条件的匹配关系。

接下来考虑如何构造。核心思路是让大部分位置两两配对，比如让：

pi=i+1,pi+1=ip_i = i+1, \quad p_{i+1} = i

这样对于这些位置，很容易在后面找到满足异或关系的元素（实际上是通过构造保证可行性）。

具体分情况讨论：

当 nn 是奇数时，可以让 pn=1p_n = 1，然后对 2∼n−12 \sim n-1 按照相邻交换的方式构造（奇偶位置互换），再单独安排 p1p_1。
当 nn 是偶数时，基本同样构造，但需要额外处理一个位置，避免冲突。做法是找到一个最大的 2k<n2^k < n，设 r=n−2kr = n - 2^k，然后交换 p1p_1 和 prp_r 来修正结构。

这种构造方式本质是利用异或的性质和排列结构，通过局部交换保证全局可行。

整体时间复杂度为 O(n)O(n)，可以处理所有数据。

参考代码

#include <bits/stdc++.h>
using namespace std;

static bool is_power_of_two(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;

        if (is_power_of_two(n)) {
            cout << -1 << '\n';
            continue;
        }

        vector<int> p(n + 1, 0);
        p[n] = 1;

        if (n & 1) {
            p[1] = n - 1;
            for (int i = 2; i <= n - 1; ++i) {
                if (i & 1) p[i] = i - 1;
                else p[i] = i + 1;
            }
        } else {
            p[1] = n;
            for (int i = 2; i <= n - 1; ++i) {
                if (i & 1) p[i] = i - 1;
                else p[i] = i + 1;
            }
            int pw = 1;
            while ((pw << 1) < n) pw <<= 1;
            int r = n - pw;
            swap(p[1], p[r]);
        }

        for (int i = 1; i <= n; ++i) {
            cout << p[i] << (i == n ? '\n' : ' ');
        }
    }
    return 0;
}

T6 回文区间翻转

题意简述

给定两个长度为 nn 的二进制串 s,ts, t。你可以对 ss 进行若干次操作，每次选择一个区间 [l,r][l, r]（l<rl < r），要求当前子串 s[l..r]s[l..r] 是回文串，然后将该区间所有字符翻转（0 变 1，1 变 0）。

目标是在不超过 2n2n 次操作内，把 ss 变成 tt，若无法做到则输出 −1-1，否则输出任意可行方案。

解题思路

这题的关键在于一个性质：我们并不是随意翻转区间，而是只能翻转“当前是回文串”的区间，因此操作的设计必须保证我们能稳定地逐步“消解结构”，而不是直接贪心修改单点。

核心做法是一个“统一归零 + 拼接”的构造思路。

首先考虑一个子问题：如何把任意字符串变成全 0。函数 reduce_to_zero 就是在做这件事。它的策略是：

先找到一对相邻相同的位置 s[i]=s[i+1]s[i] = s[i+1]，把它作为“中心”，然后从这个结构扩展一个区间 [L,R][L, R]，在扩展过程中不断利用“回文 + 翻转”的操作去调整两侧字符，使得整个串逐渐趋于一致。

如果一开始没有相邻相等的位置，就先对一个固定长度为 3 的区间进行操作“制造结构”，然后再继续处理。

在扩展过程中，如果遇到破坏当前目标值的字符，就对当前区间进行一次翻转，使其重新对齐。通过不断扩展左右边界，最终可以把整个字符串变成全 0，同时记录操作序列。

得到这个过程后，我们对 ss 和 tt 分别执行一次：

把 ss 变成全 0，得到操作序列 aa
把 tt 变成全 0，得到操作序列 bb

注意到如果我们把 tt 的操作反过来执行，就相当于从全 0 变回 tt，因此最终答案就是：

a+reverse(b)a + reverse(b)

这样就构造出从 ss 到 tt 的完整操作序列。

由于每次扩展最多线性扫描，每个字符串操作次数不超过 O(n)O(n)，整体复杂度为 O(n)O(n)，满足要求。

参考代码

#include <bits/stdc++.h>
using namespace std;

static inline void flip_segment(string& s, int l, int r) {
    for (int i = l; i <= r; ++i) {
        s[i] = (s[i] == '0' ? '1' : '0');
    }
}

vector<pair<int,int>> reduce_to_zero(string s) {
    int n = (int)s.size();
    vector<pair<int,int>> ops;

    int pos = -1;
    for (int i = 0; i + 1 < n; ++i) {
        if (s[i] == s[i + 1]) {
            pos = i;
            break;
        }
    }

    if (pos == -1) {
        ops.push_back({0, 2});
        flip_segment(s, 0, 2);
        pos = 2; // 此时下标 2 和 3 一定相等
    }

    int L = pos, R = pos + 1;
    char val = s[L];

    while (R + 1 < n) {
        if (s[R + 1] != val) {
            ops.push_back({L, R});
            flip_segment(s, L, R);
            val = s[L];
        }
        ++R;
        val = s[R];
    }

    while (L - 1 >= 0) {
        if (s[L - 1] != val) {
            ops.push_back({L, R});
            flip_segment(s, L, R);
            val = s[L];
        }
        --L;
        val = s[L];
    }

    if (s[0] == '1') {
        ops.push_back({0, n - 1});
        flip_segment(s, 0, n - 1);
    }

    return ops;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        string s, t;
        cin >> n >> s >> t;

        auto a = reduce_to_zero(s);
        auto b = reduce_to_zero(t);
        reverse(b.begin(), b.end());

        cout << a.size() + b.size() << '\n';
        for (auto [l, r] : a) {
            cout << l + 1 << ' ' << r + 1 << '\n';
        }
        for (auto [l, r] : b) {
            cout << l + 1 << ' ' << r + 1 << '\n';
        }
    }
    return 0;
}
userId_undefined
去预览
0/2000

全部评论 1

热门讨论