巅峰赛30题解
本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目标题 难度 T1 雾港城的开关 普及 - T2 雾港学宫的时钟塔调度 普及 - T3 雾港学宫的能量点对 普及/提高- T4 雾港城的道路网 普及/提高- T5 雾港学宫的能量链 普及/提高- T6 雾港城的服务中心 普及/提高-
T1
简要题解
从左到右扫一遍，记 rev 表示前面做过的后缀翻转次数的奇偶性。当前位置的实际值是 (s[i]-'0') XOR rev；如果这一位实际为 1，就说明它只能通过在当前位置再翻一次才能归零（再往右的操作不会影响它），因此必须在 i 操作一次，答案加一并把 rev 取反。扫完整个串得到的计数就是最少操作次数。
参考代码
T2
简要题解
从左到右处理，维护前一个位置最终确定的值 need。为了严格递增，当前位置最终值至少要是 need+1；如果原来的 a[i] 已经不小于 need+1 就不用动，直接把 need 更新成 a[i]，否则就把 a[i] 增加到 need+1，增加量累加进答案，并把 need 更新成 need+1。每一步都让当前值取得满足条件的最小值，不会让后面变得更难，所以得到的总增加次数就是最少操作次数。
参考代码
T3
简要题解
把每条边的权值只看奇偶即可。任选 1 号点为根做一次 DFS，设 pref[u] 表示从根到 u 这条路径上边权奇偶的异或（也就是边权和 mod 2），那么任意两点 u,v 的路径可以理解成“根到 u”和“根到 v”两条路把公共部分抵消掉，所以 u 到 v 的边权和奇偶就是 pref[u] XOR pref[v]。因此路径能量和为偶数当且仅当 pref[u]==pref[v]，问题就变成数有多少对点落在同一桶里。统计 pref=0 的点数 cnt0、pref=1 的点数 cnt1，答案是 cnt0*(cnt0-1)/2 + cnt1*(cnt1-1)/2。
参考代码
T4
简要题解
把“是否已经发生转折”当作状态即可：把每个点 uuu 拆成两层 (u,0)(u,0)(u,0)、(u,1)(u,1)(u,1)，其中 000 表示还在“不下降阶段”，111 表示已经进入“不上升阶段”。从 (u,0)(u,0)(u,0) 走边 (u,v,w)(u,v,w)(u,v,w) 时，若 h[v]≥h[u]h[v]\ge h[u]h[v]≥h[u] 就转移到 (v,0)(v,0)(v,0)（继续不下降），否则这一步就是第一次下降，转移到 (v,1)(v,1)(v,1)；从 (u,1)(u,1)(u,1) 出发则只能走满足 h[v]≤h[u]h[v]\le h[u]h[v]≤h[u]
的边并转移到 (v,1)(v,1)(v,1)（保持不上升）。这样所有从 (S,0)(S,0)(S,0) 出发的路径恰好对应“先不下降再不上升、至多一次转折”的合法路径，边权仍为 www，于是对这个 2n2n2n 状态图直接跑一遍 Dijkstra，得到 d0[u],d1[u]d_0[u],d_1[u]d0 [u],d1 [u]，答案为 min(d0[T],d1[T])\min(d_0[T],d_1[T])min(d0 [T],d1 [T])，两者都不可达则输出 −1-1−1。
参考代码
T5
简要题解
因为允许选任意非空子序列，取任意单个元素就有 L=1L=1L=1，此时没有相邻前缀可比较，必然 C=0C=0C=0，因此
Cmin=0.C_{\min}=0. Cmin =0.
接下来只需统计有多少非空子序列能让前缀乘积符号序列 S1,S2,…,SLS_1,S_2,\dots,S_LS1 ,S2 ,…,SL 恒定不变（也就是整个子序列的“符号变化次数”仍为 000）。
若前缀符号恒为 000，则首个被选元素必须满足 ai=0a_i=0ai =0。一旦首元素为 000，之后无论再选哪些位置，所有前缀乘积都为 000，因此以位置 iii 作为首个 000 的贡献为 2,n−i2^{,n-i}2,n−i，总贡献为
∑i=1n[ai=0]⋅2,n−i.\sum_{i=1}^{n}[a_i=0]\cdot 2^{,n-i}. i=1∑n [ai =0]⋅2,n−i.
若前缀符号恒为 +++，则子序列只能由正数构成。设
c_+=\left|\left{i\mid 1\le i\le n,\ a_i>0\right}\right|,
则非空正数子序列个数为
2c+−1.2^{c_+}-1. 2c+ −1.
若前缀符号恒为 −-−，则首元素必须为负数，之后只能继续选正数（再选负数会使前缀符号翻回 +++，选到 000 会使前缀符号变为 000）。对每个负数位置 iii 作为首元素，其后可选的仅为 iii 之后的正数位置。记
c_+(i)=\left|\left{j\mid i0\right}\right|,
则以该负数为首元素的贡献为 2c+(i)2^{c_+(i)}2c+ (i)，负号类总贡献为
∑i=1n[ai<0]⋅2c+(i).\sum_{i=1}^{n}[a_i<0]\cdot 2^{c_+(i)}. i=1∑n [ai <0]⋅2c+ (i).
三类子序列互不重叠，因此达到 CminC_{\min}Cmin 的子序列总数为
(∑i=1n[ai=0]⋅2,n−i+(2c+−1)+∑i=1n[ai<0]⋅2c+(i)) mod M.\left(\sum_{i=1}^{n}[a_i=0]\cdot 2^{,n-i}+\left(2^{c_+}-1\right)+\sum_{i=1}^{n}[a_i<0]\cdot 2^{c_+(i)}\right)\bmod M. (i=1∑n [ai =0]⋅2,n−i+(2c+ −1)+i=1∑n [ai <0]⋅2c+ (i))modM.
参考代码
T6
简要题解
把答案记为半径 RRR：如果能选两个中心，使每个点到最近中心的距离都不超过 RRR，就说明 RRR 可行，且 RRR 越大越容易可行，所以可以对 RRR 二分。关键是实现 check(R)：把树以 111 为根做一次 DFS，从叶子往上处理子树。对每个点 uuu 维护两件事：mx 表示在 uuu 的子树里“还没被任何中心覆盖到”的点到 uuu 的最远距离（若子树已经全覆盖则记为 −1-1−1），near 表示子树内最近的中心到 uuu 的距离（没有中心则为 ∞\infty∞）。初始时把每个点自身当作未覆盖点，所以叶子的 mx=0。合并儿子时，未覆盖最远距离就是各儿子 mx+1
的最大值，最近中心距离就是各儿子 near+1 的最小值。若当前子树里已经有中心并且它能覆盖到这棵子树中最远的未覆盖点，即满足 near+mx≤Rnear+mx\le Rnear+mx≤R，则说明整棵子树都被兜住，把 mx 置为 −1-1−1。否则如果 mx 已经等于 RRR，表示这些未覆盖点再往父亲走就会超过半径，不得不在 uuu 放一个中心：中心数加一，并把 near=0,mx=-1。DFS 结束后，如果根的 mx 仍不是 −1-1−1，说明还有点没被覆盖，再在根补一个中心。最终统计放下的中心数是否 ≤2\le2≤2，即可判断 RRR 是否可行。一次 check 是
O(n)O(n)O(n)，二分 O(logn)O(\log n)O(logn) 次，所以总复杂度 O(nlogn)O(n\log n)O(nlogn)。
参考代码
