10
巅峰赛28题解
本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目标题 难度 T1 Alice的石子合并 普及/提高- T2 Alice的奇妙爬山之旅 普及/提高- T3 Alice的神秘二叉树 普及/提高- T4 Alice的棋盘游戏 普及/提高- T5 Alice 的回文串 普及+/提高 T6 Alice 的分段游戏 普及+/提高
T1
题解
定义权值
w1=b1,wi=min(ai,bi) (2≤i≤n−1),wn=an.w_1=b_1,\qquad w_i=\min(a_i,b_i)\ (2\le i\le n-1),\qquad w_n=a_n. w1 =b1 ,wi =min(ai ,bi ) (2≤i≤n−1),wn =an .
记
base=∑i=1nwi=b1+∑i=2n−1min(ai,bi)+an.\text{base}=\sum_{i=1}^n w_i =b_1+\sum_{i=2}^{n-1}\min(a_i,b_i)+a_n. base=i=1∑n wi =b1 +i=2∑n−1 min(ai ,bi )+an .
则最小总代价为
Ans=base−max1≤i≤nwi .\boxed{\ \text{Ans}=\text{base}-\max_{1\le i\le n} w_i\ }. Ans=base−1≤i≤nmax wi .
* 下界：若最终幸存的是位置 sss，它不付费；其他位置至少各付 wiw_iwi ，故总代价 ≥base−ws\ge \text{base}-w_s≥base−ws 。
* 可达：选使 wsw_sws 最大的 sss 为幸存点；对每个 i≠si\ne si=s，只主动一次并向更便宜的一侧（端点方向唯一）。左右两侧分别先做“向左”的一批、再做“向右”的一批，能完成所有合并，总代价恰为 base−ws\text{base}-w_sbase−ws 。
综上取最小即 base−maxiwi\text{base}-\max_i w_ibase−maxi wi 。
参考代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T2
题解
将相邻格子的高度差记为 d(u,v)=∣hu−hv∣d(u,v)=|h_u-h_v|d(u,v)=∣hu −hv ∣，二分阈值 TTT 并做判定：把所有边改成 wT(u,v)=1d(u,v)>Tw_T(u,v)=\mathbf{1}{d(u,v)>T}wT (u,v)=1d(u,v)>T（d≤Td\le Td≤T 记 0、d>Td>Td>T 记 1），在四联通网格上用 0!-!1 BFS 计算从起点到终点所需的“1 边”最少条数 dist∗T\mathrm{dist}*Tdist∗T；若 dist∗T≤K\mathrm{dist}*T\le Kdist∗T≤K 则该 TTT
可行，否则不可行；利用可行性关于 TTT 的单调性在区间 [0,D∗max][0,D*{\max}][0,D∗max]（D∗maxD*{\max}D∗max 为相邻可通行格的最大高度差）上二分最小可行 TTT，若在 DmaxD_{\max}Dmax 仍不可行则输出 −1-1−1；复杂度 O(nmlogDmax)O(nm\log D_{\max})O(nmlogDmax )、空间 O(nm)O(nm)O(nm)。
参考代码
T3
题解
关键性质
对任意中序子区间 [L,R]，该子树的根一定是“在层序序列里最先出现（下标最小）且键值落在 [L,R] 的那个结点”。
因为层序总是先访问根，再访问整棵左子树与整棵右子树。
等价转化
把每个键 x 的层序出现次序记作 rank[x]（越小越靠前）。
将中序位置 i 赋权 prio[i]=rank[in[i]]。
在位置序 i=1..n 上构造一棵最小堆笛卡尔树：
* 这棵树的中序遍历顺序恰是 1..n（对应输入的中序位置）；
* 最小堆：每个结点的 prio 小于其左右孩子的 prio；
* 因此在任何区间 [L,R] 内，prio 最小者就是根——与上面的“层序最早者为根”完全一致。
构造好后，把结点下标 i 再映射回键值 in[i]，对这棵树做先序输出即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
参考代码
T4
题解
把所有可通行格（含 S）抽成一个最多 20 点的无向图（四联通、屏蔽 #）。规则“离开格子即封冻”等价于：棋子始终走在未封冻顶点上，每走一步把当前顶点加入“封冻集合”。因此状态可表示为 (mask, u)：mask 是已封冻顶点集合（位集），u 是当前所在顶点。转移：可去任一相邻未封冻顶点 v，新状态为 (mask ∪ {u}, v)。这是标准的有向无环图上的对弈 DP（必败/必胜）：
* 记 win[mask][u]：从该状态当前手是否必胜。
* 若存在某个邻居 v 使 win[mask ∪ {u}][v] 为假，则当前为真（因为能把对手送进必败）。
* 否则为假。
起始状态为 (0, S)。若起始为真，枚举四邻中任意一个能把对手送进必败的 v，输出 S -> v 作为首回合必胜走法；否则输出 LOSE。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
参考实现
T5
题解
设 dp[l][r] 表示把子串 s[l..r]（闭区间，0-based）全部删除所需的最少步数。转移：
* 先手段：把 s[l] 单独删掉，再处理右侧
dp[l][r]≤1+dp[l+1][r].dp[l][r] \le 1 + dp[l+1][r]. dp[l][r]≤1+dp[l+1][r].
* 更优的可能：若存在 p∈(l..r] 且 s[p]=s[l]，可以把 s[l] 与 s[p] 放在同一次删除里（那次删除是以这两个相同字符为两端的回文子串；在此之前需先把中间段 s[l+1..p-1] 全清空）。于是
dp[l][r]≤dp[l+1][p−1]+dp[p+1][r].dp[l][r]\le dp[l+1][p-1]+dp[p+1][r]. dp[l][r]≤dp[l+1][p−1]+dp[p+1][r].
边界：dp[i][i]=1；若整段本身是回文，显然 dp[l][r]=1。
参考代码
T6
题解
设
f[t][i];=;min0≤j<i(f[t−1][j]+cost(j+1,,i)),f[t][i] ;=; \min_{0 \le j < i}\Big( f[t-1][j] + \mathrm{cost}(j+1,, i) \Big), f[t][i];=;0≤j<imin (f[t−1][j]+cost(j+1,,i)),
表示把前 iii 个元素切成恰好 ttt 段的最小代价。最终答案为 f[k][n]f[k][n]f[k][n]。
其中
cost(L,R)=∑x(cx(L,R)2),\mathrm{cost}(L,R) = \sum_x \binom{c_x(L,R)}{2}, cost(L,R)=x∑ (2cx (L,R) ),
等价于区间内所有相等下标对 (p,q)(p,q)(p,q) 的个数（L≤p<q≤R, ap=aqL \le p < q \le R,\ a_p=a_qL≤p<q≤R, ap =aq ）。
代价维护
用一个可移动窗口 [L,R][L,R][L,R] 维护当前区间代价 curCost，配一个频次数组 cnt[v]：
* 加入值 vvv：curCost += cnt[v]，然后 cnt[v]++。
* 删除值 vvv：先 cnt[v]--，然后 curCost -= cnt[v]。
这样把窗口从 [L,R][L,R][L,R] 调整到任意 [L′,R′][L',R'][L′,R′] 的过程中，总代价可在摊还 O(1)O(1)O(1) 时间更新。
分治优化
对固定的 ttt，需要求解
f[t][i];=;minj<i,,f[t−1][j]+cost(j+1,,i),.f[t][i] ;=; \min_{j<i},{, f[t-1][j] + \mathrm{cost}(j+1,, i) ,}. f[t][i];=;j<imin ,,f[t−1][j]+cost(j+1,,i),.
记 w(j,i)=cost(j+1,i)w(j,i)=\mathrm{cost}(j+1,i)w(j,i)=cost(j+1,i)。该代价满足四边形不等式/Monge 性，故最优断点具有单调性：
opt[t][i] ≤ opt[t][i+1].\operatorname{opt}[t][i]\ \le\ \operatorname{opt}[t][i+1]. opt[t][i] ≤ opt[t][i+1].
据此用分治优化：在区间 [L,R][L,R][L,R] 的中点 mmm 仅在 [optL,,optR][optL,,optR][optL,,optR] 扫 jjj，递归到两侧时分别缩小搜索区间。
配合“可移动窗口”，在枚举 jjj 的过程中把窗口依次从 [j+1,m][j+1,m][j+1,m] 挪到下一个候选，保证整体效率。
初始层与边界
* t=1t=1t=1：直接线性扩展窗口得到 cost(1,i)\mathrm{cost}(1,i)cost(1,i) 作为 f[1][i]f[1][i]f[1][i]。
* 不可行状态：i<ti<ti<t 无法切成 ttt 段，置为 +∞+\infty+∞。
* 基础：f[0][0]=0f[0][0]=0f[0][0]=0，其余 f[0][i>0]=+∞f[0][i>0]=+\inftyf[0][i>0]=+∞。
复杂度
时间 O(k,nlogn),空间 O(n+maxai).\text{时间 } O(k,n\log n), \qquad \text{空间 } O(n+\max a_i). 时间 O(k,nlogn),空间 O(n+maxai ).
参考代码
有帮助，赞一个