巅峰赛33题解
本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目标题 难度 T1 双色序判定 普及- T2 阈值远征 普及/提高- T3 更优括号子序列 普及/提高- T4 单向配送 普及+/提高 T5 异或后缀排列 普及+/提高 T6 回文区间翻转 提高+/省选-
T1 双色序判定
题意简述
给定一个长度为 nnn 的排列（元素互不相同），需要给每个位置染成两种颜色之一，使得满足两个条件：一是在原序列中相邻位置颜色必须不同；二是将所有元素按数值从小到大排序后，相邻元素的颜色仍然不同。要求判断是否存在这样的染色方案。
解题思路
先看第一个条件：原序列相邻位置颜色不同，这实际上已经把染色方式基本确定了。因为只有两种颜色，所以一旦第一个位置确定，后面的位置颜色就必须交替出现，也就是说整个序列的染色方案只能是“黑白黑白……”或者“白黑白黑……”。
换句话说，本质上就是按照下标奇偶性来染色，比如让 i mod 2i \bmod 2imod2 决定颜色。
接下来关键是第二个条件：将序列按数值从小到大排序后，相邻元素颜色也必须不同。我们可以把每个数连同它原来的位置一起排序，然后检查排序后的相邻两个元素，它们原来的位置奇偶性（也就是颜色）是否不同。
如果存在一对相邻元素，它们排序后挨在一起，但原下标奇偶性相同，那么它们颜色相同，就不满足要求，答案为 NO；否则如果所有相邻对都满足奇偶不同，则说明这种交替染色是合法的，答案为 YES。
由于另一种染色（整体翻转颜色）本质是一样的，所以只需要检查一种情况即可。
时间复杂度主要是排序，为 O(nlogn)O(n \log n)O(nlogn)，在数据范围内完全没问题。
参考代码
T2 阈值远征
题意简述
有 nnn 把武器，第 iii 把威力为 aia_iai ，还有 nnn 个关卡，第 iii 关需要恰好 bib_ibi 次攻击才能通过。你需要先选择一个难度值 xxx，所有威力小于 xxx 的武器会失效，其余武器每把只能使用一次。
然后按顺序挑战关卡：如果当前剩余武器数不少于 bib_ibi ，就消耗 bib_ibi 把通过该关，否则停止。最终得分为：
score=x×(通过的关卡数)\text{score} = x \times (\text{通过的关卡数})score=x×(通过的关卡数)
求最大得分。
解题思路
关键在于如何选择 xxx。注意到如果确定了 xxx，那么所有满足 ai≥xa_i \ge xai ≥x 的武器都可以用，也就是说我们实际拥有的武器数量就是“威力不小于 xxx 的武器个数”。
因此可以先将数组 aaa 从大到小排序。假设当前考虑第 iii 大的武器作为阈值 x=aix = a_ix=ai ，那么此时我们一共有 iii 把可用武器。
接下来问题变成：用这 iii 把武器，最多可以通过多少关。由于必须按顺序打关卡，我们可以贪心地从前往后尝试，用一个变量记录已经通过的关卡数 levellevellevel，以及通过这些关卡一共消耗的武器数量 needneedneed。
当我们尝试多通过一关时，只要满足：
need+blevel+1≤ineed + b_{level+1} \le ineed+blevel+1 ≤i
就说明当前武器数足够，可以继续通过这一关，并更新 needneedneed 和 levellevellevel。
随着 iii 增大，可用武器变多，能通过的关卡数也单调不减，因此用双指针或类似滑动方式维护这个过程即可。
对于每个 iii，计算当前得分：
ai×levela_i \times levelai ×level
取最大值作为答案。
整体时间复杂度是排序 O(nlogn)O(n \log n)O(nlogn) 加上线性扫描 O(n)O(n)O(n)，可以通过所有数据。
参考代码
T3 更优括号子序列
题意简述
给定一个长度为 $n $$ 的合法括号序列 sss，需要从中删除若干字符（保留相对顺序），得到一个非空子序列 ttt，要求：
* ttt 仍然是合法括号序列；
* ttt 在字典序意义下比 sss 更优（即要么 sss 是 ttt 的前缀，要么在第一个不同的位置 ttt 放的是 '(' 而 sss 放的是 ')'）。
求满足条件的 ttt 的最大长度，如果不存在输出 −1-1−1。
解题思路
关键在于理解“更优”的定义。因为括号序列只包含 '(' 和 ')'，而 '(' 的字典序更小，所以本质就是希望在尽量靠前的位置，把原本的 ')' 换成 '('。
但我们只能通过“删除字符”来实现这一点。也就是说，我们要找到一个位置 $$ i $$，使得 $$ s_i = ')' $$，然后在它后面找到一个 '(' 来“提前”作为子序列中的位置，从而让新序列在这个位置变成 '('，达到更优。
假设我们选定一个位置 iii（满足 si=′)′s_i = ')'si =′)′），然后找到后面最近的一个 '('，位置为 jjj。为了让这个 '(' 提前，我们必须删除区间 [i,j][i, j][i,j] 内的所有字符（否则顺序无法改变），这样相当于删除了长度为：
need=j−ineed = j - ineed=j−i
但删除这些字符后，还要保证剩下的序列仍然是合法括号序列。由于删除了若干个括号，为了维持匹配关系，还需要在后面再删除同样数量的 '(' 来平衡。
因此我们需要在 jjj 之后，至少还有 needneedneed 个 '(' 可以删除（用于匹配之前删除的 ')'），也就是满足：
suf_open[j+1]≥need{suf\_open}[j+1] \ge needsuf_open[j+1]≥need
如果这个条件成立，那么我们可以构造一个合法的更优子序列，其长度为：
n−2×needn - 2 \times needn−2×need
枚举所有这样的 iii，取最大值即可。
为了快速找到每个位置之后的最近 '('，可以预处理一个数组 nxt[i]nxt[i]nxt[i] 表示从 iii 开始往后的第一个 '(' 的位置；同时用 suf_open[i]suf\_open[i]suf_open[i] 表示从 iii 到结尾的 '(' 数量。
整体时间复杂度为 O(n)O(n)O(n)，对每组数据线性处理即可。
参考代码
T4 单向配送
题意简述
在平面上从起点 (Ax,Ay)(A_x, A_y)(Ax ,Ay ) 出发，最终到达终点 (Bx,By)(B_x, B_y)(Bx ,By )，途中需要访问所有给定的投递点。每次只能向右、向上或向下移动一步（即 xxx 只能递增，yyy 可以上下变化），每步代价为 1。
要求在满足访问所有点的前提下，使总移动步数最小。
解题思路
由于只能向右移动（xxx 单调递增），所以整个路径在 xxx 轴上是从 AxA_xAx 一路走到 BxB_xBx ，中途不会回头。因此可以把问题看成按 xxx 坐标分组，从左到右依次处理。
对于同一个 xxx 坐标上的所有点，我们必须把这些点全部访问。因为在同一列中可以上下移动，所以最优策略一定是从这一列的某个端点走到另一个端点，把这一列的所有点“一次扫完”。因此我们只需要关心这一列的最小 yyy 和最大 yyy，记为区间 [low,high][low, high][low,high]。
于是问题转化为：有若干列，每列对应一个区间 [lowi,highi][low_i, high_i][lowi ,highi ]，我们从左往右依次经过这些列，每一列必须完整走一遍（代价是 highi−lowihigh_i - low_ihighi −lowi ），并且需要考虑列与列之间的移动代价。
设 dp[i][0]dp[i][0]dp[i][0] 表示处理到第 iii 列，最后停在这一列的上端点 highihigh_ihighi 的最小代价；dp[i][1]dp[i][1]dp[i][1] 表示停在下端点 lowilow_ilowi 的最小代价。
转移时，从上一列的两个端点转移到当前列的某个端点，取最小值。例如转移到当前列的下端点：
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)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 )
到上端点同理。
其中距离函数是曼哈顿距离：
dist=∣x1−x2∣+∣y1−y2∣\text{dist} = |x_1 - x_2| + |y_1 - y_2|dist=∣x1 −x2 ∣+∣y1 −y2 ∣
注意起点和终点也可以看作特殊的列加入处理。
最终答案是最后一列两种状态的最小值。
整体复杂度主要是排序或 map 处理，为 O(nlogn)O(n \log n)O(nlogn)。
参考代码
T5 异或后缀排列
题意简述
给定一个整数 nnn，需要构造一个 1∼n1 \sim n1∼n 的排列 ppp，满足对于每个位置 iii（1≤i≤n−11 \le i \le n-11≤i≤n−1），在后缀区间 [i,n][i,n][i,n] 中存在某个位置 jjj，使得：
pi=pj⊕ip_i = p_j \oplus ipi =pj ⊕i
如果存在这样的排列输出任意一个，否则输出 −1-1−1。
解题思路
先考虑什么时候无解。一个关键结论是：当 nnn 是 2 的幂时一定无解。这是因为异或的结构在二进制下具有分层性质，当范围刚好是 [1,2k][1, 2^k][1,2k] 时，无法构造满足所有位置条件的匹配关系。
接下来考虑如何构造。核心思路是让大部分位置两两配对，比如让：
pi=i+1,pi+1=ip_i = i+1, \quad p_{i+1} = ipi =i+1,pi+1 =i
这样对于这些位置，很容易在后面找到满足异或关系的元素（实际上是通过构造保证可行性）。
具体分情况讨论：
当 nnn 是奇数时，可以让 pn=1p_n = 1pn =1，然后对 2∼n−12 \sim n-12∼n−1 按照相邻交换的方式构造（奇偶位置互换），再单独安排 p1p_1p1 。
当 nnn 是偶数时，基本同样构造，但需要额外处理一个位置，避免冲突。做法是找到一个最大的 2k<n2^k < n2k<n，设 r=n−2kr = n - 2^kr=n−2k，然后交换 p1p_1p1 和 prp_rpr 来修正结构。
这种构造方式本质是利用异或的性质和排列结构，通过局部交换保证全局可行。
整体时间复杂度为 O(n)O(n)O(n)，可以处理所有数据。
参考代码
T6 回文区间翻转
题意简述
给定两个长度为 nnn 的二进制串 s,ts, ts,t。你可以对 sss 进行若干次操作，每次选择一个区间 [l,r][l, r][l,r]（l<rl < rl<r），要求当前子串 s[l..r]s[l..r]s[l..r] 是回文串，然后将该区间所有字符翻转（0 变 1，1 变 0）。
目标是在不超过 2n2n2n 次操作内，把 sss 变成 ttt，若无法做到则输出 −1-1−1，否则输出任意可行方案。
解题思路
这题的关键在于一个性质：我们并不是随意翻转区间，而是只能翻转“当前是回文串”的区间，因此操作的设计必须保证我们能稳定地逐步“消解结构”，而不是直接贪心修改单点。
核心做法是一个“统一归零 + 拼接”的构造思路。
首先考虑一个子问题：如何把任意字符串变成全 0。函数 reduce_to_zero 就是在做这件事。它的策略是：
先找到一对相邻相同的位置 s[i]=s[i****[i] = s[i****[i]=s[i+1]，把它作为“中心”，然后从这个结构扩展一个区间 [L,R][L, R][L,R]，在扩展过程中不断利用“回文 + 翻转”的操作去调整两侧字符，使得整个串逐渐趋于一致。
如果一开始没有相邻相等的位置，就先对一个固定长度为 3 的区间进行操作“制造结构”，然后再继续处理。
在扩展过程中，如果遇到破坏当前目标值的字符，就对当前区间进行一次翻转，使其重新对齐。通过不断扩展左右边界，最终可以把整个字符串变成全 0，同时记录操作序列。
得到这个过程后，我们对 sss 和 ttt 分别执行一次：
把 sss 变成全 0，得到操作序列 aaa
把 ttt 变成全 0，得到操作序列 bbb
注意到如果我们把 ttt 的操作反过来执行，就相当于从全 0 变回 ttt，因此最终答案就是：
a+reverse(b)a + reverse(b)a+reverse(b)
这样就构造出从 sss 到 ttt 的完整操作序列。
由于每次扩展最多线性扫描，每个字符串操作次数不超过 O(n)O(n)O(n)，整体复杂度为 O(n)O(n)O(n)，满足要求。
参考代码
