巅峰赛32题解
本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目标题 难度 T1 返程拼车 普及- T2 星港远航 普及/提高- T3 霓虹线路 普及/提高- T4 雾港灯串 普及- T5 星灯选址 普及- T6 分裂晶体 提高+/省选-
T1 返程拼车
题目大意
给定 nnn 个同学在数轴上的位置 xix_ixi ，每辆车最多载 222 人，且两人之间距离满足 ∣xi−xj∣≤D|x_i-x_j|\le D∣xi −xj ∣≤D 才能拼车。求最少需要多少辆车使所有同学都能回家。
题解思路
要让车辆数最少，就要让“拼车的对数”尽量多，因为每拼成一对就比两人各自打车少用一辆车。
把所有位置 xix_ixi 排序为 p1≤p2≤⋯≤pnp_1\le p_2\le \dots \le p_np1 ≤p2 ≤⋯≤pn 。在有序序列上从左到右扫描：
* 如果 pi+1−pi≤Dp_{i+1}-p_i\le Dpi+1 −pi ≤D，就把这两位同学配成一对，然后跳过这两人；
* 否则 pip_ipi 无法与任何更右侧的人拼车（更右只会更远），只能单独一辆车。
这是最大化不相交配对数的典型贪心：能配就立刻配相邻元素。设配对数为 pairs，答案为
cars=n−pairs.\text{cars}=n-\text{pairs}. cars=n−pairs.
复杂度：排序 O(nlogn)O(n\log n)O(nlogn)，扫描 O(n)O(n)O(n)。
参考代码
T2 星港远航
题目大意
从位置 000 出发，要到达位置 LLL。初始有能量 PPP，每走 111 单位距离消耗 111 能量。沿途有若干补给站，第 iii 个补给站在位置 xix_ixi ，可以提供 aia_iai 的能量，每个站最多使用一次。求最少需要使用多少个补给站才能到达终点，若无法到达输出 −1-1−1。
题解思路
这是一个典型的贪心问题。关键在于：当当前能量不足以继续前进时，应该从之前经过的所有补给站中选择补给量最大的那个来使用。
先将所有补给站按位置排序，并把终点看成一个位置为 LLL、补给量为 000 的虚拟站。设当前最远能到达的位置为 reachreachreach，初始为 PPP，同时用一个大根堆维护所有已经经过的补给站的补给量。
从左到右扫描每个站：
如果当前站的位置 xi≤reachx_i \le reachxi ≤reach，说明可以到达，就把该站的补给量加入堆中；如果 xi>reachx_i > reachxi >reach，说明当前无法到达这个站，此时必须从堆中取出最大补给量来补充能量，使 reachreachreach 增大，并统计一次补给操作。重复这个过程，直到可以到达当前站或者堆为空。
如果堆为空仍无法前进，说明无法到达终点，输出 −1-1−1。否则最终成功走到终点，补给次数就是答案。
这个贪心策略的核心在于：每次必须补给时，选择补给量最大的站，可以让当前可达距离尽可能远，从而减少后续补给次数，是最优选择。
参考代码
T3 霓虹线路
题目大意
给定一棵有 nnn 个点的树，需要给每条边染色，颜色编号为 1∼k1\sim k1∼k。要求对于任意一个点，与它相连的所有边颜色必须两两不同。判断是否存在合法方案，若存在输出任意一种。
题解思路
树的边染色要求“每个点相邻边颜色两两不同”，这就是树上的proper edge coloring。设树的最大度数为 Δ\DeltaΔ。必要条件是 k≥Δk\ge \Deltak≥Δ：因为度为 Δ\DeltaΔ 的点周围 Δ\DeltaΔ 条边必须用不同颜色。
对树而言这也是充分条件：当 k≥Δk\ge\Deltak≥Δ 时一定能染色。构造方法用一次 DFS 从根向下分配颜色即可。
把树以 1 为根。对每个点 uuu，设与父边的颜色为 parColor[u]（根为 0）。我们给 uuu 的所有子边依次分配颜色 1..k，但跳过 parColor[u]，并且同一节点内部不重复。因为 uuu 的子边数是 deg(u)-1（根是 deg(u)），而 deg(u)≤kdeg(u)\le kdeg(u)≤k，所以总能分配完且不会用到第 k+1k+1k+1 种颜色。
实现上先用栈/队列求出父子关系，再按父到子的顺序给边赋色，复杂度 O(n)O(n)O(n)。
若 k<Δk<\Deltak<Δ，直接输出 NO。
参考代码
T4 雾港灯串
题目大意
给定一个长度为 nnn 的 01 串，可以通过翻转某一位（0↔10 \leftrightarrow 10↔1）来修改它。要求最终得到的新串满足：任意连续长度为 444 的子串中，111 的个数不能恰好为 333。求最少需要翻转多少次。
题解思路
本题的约束只涉及长度为 4 的相邻窗口，因此可以用“最近若干位作为状态”的线性 DP。设我们从左到右构造目标串 bbb，当决定了当前位置的值后，未来只会和“最近 3 位”共同组成新的长度为 4 的窗口，所以只需记住最后 3 位即可。
用一个 3 位二进制掩码 mask 表示当前已构造前缀的最后 3 盏灯（从左到右依次是更早到更晚）。令 dp[mask] 为构造到当前位置之前的最少翻转次数。处理第 iii 位时，尝试把 bib_ibi 取为 0 或 1：
* 若 i≥4i\ge 4i≥4，则长度为 4 的窗口正好是“上一状态的 3 位 + 当前选择的 1 位”，对应一个 4 位数 w=(mask<<1)|b_i，若 popcount(w)==3 则该选择非法；
* 否则（前 3 位）没有形成长度为 4 的窗口，不需要检查。
代价增加为 [s_i\ne b_i]，新状态为 ((mask<<1)&7)|b_i。每步转移常数只有 16 次，整体复杂度为 O(n)O(n)O(n)，空间为 O(1)O(1)O(1)。
最终答案是处理完全部位置后所有 dp[mask] 的最小值。
参考代码
T5 星灯选址
题目大意
给定一个长度为 nnn 的数组 aia_iai ，表示在第 iii 个位置放置星灯的收益（可以为负）。要求选择若干位置，使得不能选择相邻位置，并且总收益最大。同时需要输出一种最优方案。
题解思路
这是经典的线性 DP。设 dp[i] 表示只考虑前 i 个位置能得到的最大收益，则第 i 个位置要么不选，要么选：
* 不选 i：收益 dp[i-1]
* 选 i：则 i-1 不能选，收益 dp[i-2] + a_i
所以递推为
dp[i]=max(dp[i−1],dp[i−2]+ai).dp[i]=\max(dp[i-1], dp[i-2]+a_i). dp[i]=max(dp[i−1],dp[i−2]+ai ).
边界 dp[0]=0，dp[1]=max(0,a_1)。为了输出方案，用一个数组记录每个 i 是通过哪种转移得到的，最后从 i=n 反向回溯即可。复杂度 O(n)。
参考代码
T6 分裂晶体
题目大意
给定一棵以 1 号节点为根的树，每个节点有一个整数能量值。要求通过任意重排每个节点的子树顺序，生成字典序最小的先序遍历序列。
题解思路
对任意节点 u，设它的“最稳定子序列” S(u) 是在允许重排 u 的孩子后，u 的子树先序序列中字典序最小的那条。显然整棵树的答案就是 S(1)。
如果 u 的孩子子树最稳定子序列分别是 S(v1),S(v2),…，那么 S(u) 一定形如：
S(u) = [a_u] + S(按某顺序排列的孩子 1) + S(孩子 2) + …
为了让拼接后的整体字典序最小，只需把孩子按各自的 S(v) 的字典序从小到大排序后依次拼接即可：因为先序序列在进入第一个孩子子树前已经固定为 a_u，之后最先产生差异的位置一定落在“第一个不同孩子的子序列”里，所以把最小的子序列放在最前是最优的。
因此问题变成：需要能高效比较两个子树的 S(u) 与 S(v)。直接把 S(u) 展开成数组会导致总长度平方级。
做法是把每个 S(u) 当成一条“序列对象”，用一棵隐式 Treap 维护：
* 长度 len；
* 两个模数下的多项式哈希值；
* 支持 O(log n) 取第 k 个元素、取前缀哈希。
比较两个序列时，用二分 + 前缀哈希求它们的最长公共前缀 LCP，再比较下一位元素即可完成字典序比较。对子树排序后，用 Treap 进行序列拼接（merge）即可得到父节点的序列对象。
整体流程：先把树以 1 为根，得到父子关系与后序顺序；按后序从叶到根处理，每个节点对孩子排序并合并生成自己的序列对象，同时把排序结果存下来。最后按存下来的孩子顺序做一次先序遍历输出能量值。
复杂度：设比较一次序列为 O(log^2 n)，则总复杂度约为 O((n + 总排序比较次数)·log^2 n)，在本题规模内可通过；空间 O(n)。
参考代码
