官方题解 | 巅峰赛#33

NoonMaple

2026-05-03 16:32:11

发布于：浙江

52阅读

0回复

0点赞

巅峰赛33题解

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

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

T1 双色序判定

题意简述

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

解题思路

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

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

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

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

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

时间复杂度主要是排序，为 $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 阈值远征

题意简述

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

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

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

求最大得分。

解题思路

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

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

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

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

$need + b_{level+1} \le i$

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

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

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

$a_i \times level$

取最大值作为答案。

整体时间复杂度是排序 $O(n \log 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 $$ 的合法括号序列 $s$ ，需要从中删除若干字符（保留相对顺序），得到一个非空子序列 $t$ ，要求：

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

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

解题思路

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

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

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

$need = j - i$

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

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

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

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

$n - 2 \times need$

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

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

整体时间复杂度为 $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 单向配送

题意简述

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

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

解题思路

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

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

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

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

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

$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)$

到上端点同理。

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

$\text{dist} = |x_1 - x_2| + |y_1 - y_2|$

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

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

整体复杂度主要是排序或 map 处理，为 $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 异或后缀排列

题意简述

给定一个整数 $n$ ，需要构造一个 $1 \sim n$ 的排列 $p$ ，满足对于每个位置 $i$ （ $1 \le i \le n-1$ ），在后缀区间 $[i,n]$ 中存在某个位置 $j$ ，使得：

$p_i = p_j \oplus i$

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

解题思路

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

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

$p_i = i+1, \quad p_{i+1} = i$

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

具体分情况讨论：

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

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

整体时间复杂度为 $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 回文区间翻转

题意简述

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

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

解题思路

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

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

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

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

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

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

得到这个过程后，我们对 $s$ 和 $t$ 分别执行一次：

把 $s$ 变成全 0，得到操作序列 $a$
把 $t$ 变成全 0，得到操作序列 $b$

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

$a + reverse(b)$

这样就构造出从 $s$ 到 $t$ 的完整操作序列。

由于每次扩展最多线性扫描，每个字符串操作次数不超过 $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;
}