巅峰赛29题解
本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目标题 难度 T1 奇核匹配 普及- T2 连通祭坛的封匣仪式 普及/提高- T3 风祭城的碑阵刻印 普及+/提高 T4 星塔抄卷 普及+/提高 T5 夜巡城的望炬布防 普及+/提高 T6 月环封印 提高+/省选-
T1
题解
把每个能量写成 二进制分解 的形式
x=2e⋅t,t 为奇数（或 x=0）.x=2^{e}\cdot t,\qquad t\ \text{为奇数（或 }x=0\text{）}. x=2e⋅t,t 为奇数（或 x=0）.
题目中的操作等价于：
* 当能量为偶数时，只能“剥去”一个因子 222（x↦x/2x\mapsto x/2x↦x/2）；可反复，直到变成奇数；
* 当能量为奇数时，只能先变成 2t2t2t，但下一步又只能除以 222 回到 ttt，于是奇数不能再改变；
* 能量 000 只能保持为 000。
于是一个数 xxx 可达的所有取值恰为
,2e′⋅t∣0≤e′≤e,(若 x>0),0 (若 x=0).{,2^{e'}\cdot t\mid 0\le e'\le e,} \quad(\text{若 }x>0),\qquad {0}\ (\text{若 }x=0). ,2e′⋅t∣0≤e′≤e,(若 x>0),0 (若 x=0).
这给出充要条件：
1. 必要性：任意施术后，每件灵具的奇数部分 ttt（把 xxx 去掉所有 222 的因子）保持不变；000 也不会变成非 000。因此，若两箱最终能一致，则两箱中按“奇数部分（或 000）”分组后的计数必须完全相同。
2. 充分性：若两箱在“奇数部分（或 000）”的多集计数相同，则把每一组（相同奇数部分 ttt 的物件）两两配对。设一对的指数分别为 e1,e2e_1,e_2e1 ,e2 ，两件都可降到
2min(e1,e2)⋅t,2^{\min(e_1,e_2)}\cdot t, 2min(e1 ,e2 )⋅t,
从而每对都能变成完全相同的数。各组独立配对后，两箱整体多集即相同。
因此，只需把两箱每个数反复除以 222 直到变为奇数（或保留 000），得到两组“奇数核”多集，比较是否相同即可。
复杂度：每个数最多除 log2(maxx)\log_2(\max x)log2 (maxx) 次，整体
O!(nlogmaxx).O!\bigl(n\log \max x\bigr). O!(nlogmaxx).
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
参考代码
T2
题解
把整张图按连通分量拆开。对每个连通分量 CCC，记节点数为 ∣C∣\lvert C\rvert∣C∣，灵石总和为 SC=∑i∈CaiS_C=\sum_{i\in C}a_iSC =∑i∈C ai 。
在这个分量里最多能封成的灵匣数恰为
min(,∣C∣, ⌊SC/k⌋,).\min\bigl(,\lvert C\rvert,\ \lfloor S_C/k\rfloor,\bigr). min(,∣C∣, ⌊SC /k⌋,).
全图答案是各分量答案之和：
Ans=∑Cmin(,∣C∣, ⌊SC/k⌋,).\text{Ans}=\sum_{C}\min\bigl(,\lvert C\rvert,\ \lfloor S_C/k\rfloor,\bigr). Ans=C∑ min(,∣C∣, ⌊SC /k⌋,).
参考代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T3
题解
从全 000 矩阵出发，只能做“整行 +1+1+1 / 整列 +1+1+1”。记第 iii 行被加了 rir_iri 次、第 jjj 列被加了 cjc_jcj 次，则必须有
Aij=ri+cj.A_{ij}=r_i+c_j. Aij =ri +cj .
因此可达性的充要条件是
Aij+A11=Ai1+A1j(∀,i,j).A_{ij}+A_{11}=A_{i1}+A_{1j}\quad(\forall,i,j). Aij +A11 =Ai1 +A1j (∀,i,j).
* 必要性：上式由 Aij=ri+cjA_{ij}=r_i+c_jAij =ri +cj 直接得到；
* 充分性：若恒等式成立，取
ri0=Ai1−A11,cj0=A1j,r_i^0=A_{i1}-A_{11},\qquad c_j^0=A_{1j}, ri0 =Ai1 −A11 ,cj0 =A1j ,
则 ri=ri0+t, cj=cj0−tr_i=r_i^0+t,\ c_j=c_j^0-tri =ri0 +t, cj =cj0 −t 对任意整数 ttt 都满足 ri+cj=Aijr_i+c_j=A_{ij}ri +cj =Aij 。在 A≥0A\ge 0A≥0 的前提下，取 t=minjA1jt=\min_j A_{1j}t=minj A1j 可保证 ri,cj≥0r_i,c_j\ge 0ri ,cj ≥0，从而存在一系列行列加法把全 000 变到 AAA。
算法：枚举全部 (i,j)(i,j)(i,j) 检查恒等式是否成立；若有一处不等则不可达，否则可达。时间 O(nm)O(nm)O(nm)。
参考代码
T4 题解
要求目标串 ttt 满足：任意相邻长度为 333 的子串里三个字符两两不同。等价于：当我们从左到右填第 iii 位字符 vvv 时，只要保证它与前两位 w=ti−2,u=ti−1w=t_{i-2},u=t_{i-1}w=ti−2 ,u=ti−1 都不同，即 v≠uv\ne uv=u 且 v≠wv\ne wv=w，那么所有长度为 333 的窗口都会合法。
因此用“末两位”做状态 DP。把字母映射为 0..250..250..25。
设 dp[w][u]dp[w][u]dp[w][u] 表示已经填到当前位置 i−1i-1i−1，末两位是 (w,u)(w,u)(w,u) 的方案数（且之前都合法）。第 iii 位允许的字母由输入决定：若 s[i]=′?′s[i]='?'s[i]=′?′ 则任意 0..250..250..25，否则只能取固定字母。
转移到新末两位 (u,v)(u,v)(u,v)：必须 v≠uv\ne uv=u、v≠wv\ne wv=w，且 vvv 允许。直接枚举 www 会多一层 262626。用列和降维：
对每个 uuu 先算
Su=∑w=025dp[w][u].S_u=\sum_{w=0}^{25} dp[w][u]. Su =w=0∑25 dp[w][u].
那么
dp2[u][v]=∑w≠vdp[w][u]=Su−dp[v][u],dp2[u][v]=\sum_{w\ne v} dp[w][u] = S_u - dp[v][u], dp2[u][v]=w=v∑ dp[w][u]=Su −dp[v][u],
同时还要满足 v≠uv\ne uv=u，否则该状态为 000。另外如果 vvv 不允许，也为 000。
初始化：
* n=1n=1n=1：答案是第 000 位可选字母数；
* n≥2n\ge 2n≥2：先把前两位所有允许的 (w,u)(w,u)(w,u) 置为 111，然后从 i=2i=2i=2 滚动到 n−1n-1n−1。
最终答案是最后一层所有 dp[w][u]dp[w][u]dp[w][u] 的总和。全程对模数 998244353998244353998244353 取模，复杂度是 O(262n)O(26^2 n)O(262n)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
参考代码（更短一些）
T5
把“点灯”抽象为树上的最小支配集：选一些点放灯，使得每个点要么自己有灯，要么与某个有灯的点相邻，且灯的数量最少。把树以 111 为根，做树形 DP。
对每个结点 uuu 定义三种状态：
* f0(u)f_0(u)f0 (u)：在 uuu 放灯；
* f1(u)f_1(u)f1 (u)：uuu 不放灯，但由某个子结点放灯覆盖（至少有一个子结点处于状态 000）；
* f2(u)f_2(u)f2 (u)：uuu 不放灯，且未被覆盖（等待父结点覆盖）。
设 vvv 枚举 uuu 的子结点，有：
f0(u)=1+∑vminf0(v),f1(v),f2(v).f_0(u)=1+\sum_v \min{f_0(v),f_1(v),f_2(v)}. f0 (u)=1+v∑ minf0 (v),f1 (v),f2 (v).
当 uuu 未被覆盖（交给父亲），则子结点不能处于“也未被覆盖”的状态，否则子树里会出现无人覆盖的点，因此：
f2(u)=∑vminf0(v),f1(v).f_2(u)=\sum_v \min{f_0(v),f_1(v)}. f2 (u)=v∑ minf0 (v),f1 (v).
当 uuu 由子结点覆盖时，子结点同样只能取 0/10/10/1，并且必须至少一个子结点取 000。先算基准和
S=∑vminf0(v),f1(v).S=\sum_v \min{f_0(v),f_1(v)}. S=v∑ minf0 (v),f1 (v).
如果在某个子结点上本来就满足 f0(v)≤f1(v)f_0(v)\le f_1(v)f0 (v)≤f1 (v)，那么基准选择里已经可能取到 f0(v)f_0(v)f0 (v)，这时可以令 Δ=0\Delta=0Δ=0。否则需要强制把某个子结点从 minf0(v),f1(v)\min{f_0(v),f_1(v)}minf0 (v),f1 (v) 改成 f0(v)f_0(v)f0 (v)，代价为 f0(v)−minf0(v),f1(v)f_0(v)-\min{f_0(v),f_1(v)}f0 (v)−minf0 (v),f1 (v)，取最小即可：
Δ=minv(f0(v)−minf0(v),f1(v)).\Delta=\min_v \bigl(f_0(v)-\min{f_0(v),f_1(v)}\bigr). Δ=vmin (f0 (v)−minf0 (v),f1 (v)).
于是
f1(u)=S+Δ.f_1(u)=S+\Delta. f1 (u)=S+Δ.
叶子结点没有子结点，不可能被“子结点的灯”覆盖，所以 f1(u)=+∞f_1(u)=+\inftyf1 (u)=+∞。
根结点没有父结点，不能处于 f2f_2f2 ，答案为：
minf0(1),f1(1).\min{f_0(1),f_1(1)}. minf0 (1),f1 (1).
整体复杂度 O(n)O(n)O(n)。
T6
题意转化
把切开得到的串记为 sss，长度为偶数 nnn，只含 '(' 与 ')'。允许：
1. 在环上交换两个位置字符（也可不交换，视为 l=rl=rl=r）；
2. 再任选切口摊平（等价于对串做任意循环位移）；
问：最多有多少个切口能得到正规括号序列，最大值记为 ggg，并输出一组达到 ggg 的交换位置。
若总平衡不为 000（即 #'(' \ne #')'），则无论怎么交换、怎么切口都不可能成为正规括号序列，直接 g=0g=0g=0。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
关键结论：好切口 = 最小前缀出现次数
对线性串（总平衡为 000），定义前缀和：
pre[0]=0,pre[i]=pre[i−1]+(si==′(′?1:−1).pre[0]=0,\quad pre[i]=pre[i-1]+(s_i=='('?1:-1). pre[0]=0,pre[i]=pre[i−1]+(si ==′(′?1:−1).
设 mn=min0≤i≤npre[i]mn=\min_{0\le i\le n} pre[i]mn=min0≤i≤n pre[i]。经典结论：切口 kkk（从 sk+1s_{k+1}sk+1 开始的循环位移）是正规括号序列，当且仅当 pre[k]=mnpre[k]=mnpre[k]=mn。
因此“不交换”的好切口数是
g_0=#{k\mid pre[k]=mn}.
代码先用 rot 把串旋到某个最小前缀处开头得到 ttt（只为方便分类，最后把下标旋回原串）。
并在 ttt 上标记：
* B[i]=[pre[i]=mn]B[i]=[pre[i]=mn]B[i]=[pre[i]=mn]（原本的好切口）
* C[i]=[pre[i]=mn+1]C[i]=[pre[i]=mn+1]C[i]=[pre[i]=mn+1]
* D[i]=[pre[i]=mn+2]D[i]=[pre[i]=mn+2]D[i]=[pre[i]=mn+2]
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
一次交换的影响：只会让一段前缀整体 −2-2−2
交换两处字符，只有交换 '(' 与 ')' 才会改变前缀形态。设选定一段弧 (l,r](l,r](l,r]（沿环走从 lll 到 rrr），并要求：
* 位置 lll 上是 '('，位置 rrr 上是 ')'（这样交换后这段弧对应的前缀会下降）。
交换后效果是：
* 在弧 (l,r](l,r](l,r] 内，所有前缀和整体 −2-2−2；
* 弧外前缀不变。
所以新的全局最小值只可能是 mn−2mn-2mn−2、mn−1mn-1mn−1 或仍为 mnmnmn。对应三类情况，新的好切口数可以直接数：
情况 1（KIND=1）：新最小值变成 MN−2MN-2MN−2
弧内原本 pre=mnpre=mnpre=mn 的位置会变成 mn−2mn-2mn−2，成为新的最小，因此
g=#(B\text{ 在弧内}).
std 用双倍扫描 + 单调队列，在满足“左端 '('、右端 ')'、弧长 ≤n−1\le n-1≤n−1”的弧中最大化弧内 BBB 的数量。
情况 2（KIND=2）：新最小值变成 MN−1MN-1MN−1
为避免出现 mn−2mn-2mn−2，弧内必须没有任何 BBB（否则会压到 mn−2mn-2mn−2）。在这种弧里，原本 mn+1mn+1mn+1 的位置会被压到 mn−1mn-1mn−1，因此
g=#(C\text{ 在弧内}).
弧内无 BBB 等价于弧必须落在“相邻两个 BBB 之间”的空隙里。std 枚举每个空隙，并在空隙内用 seg 求弧内 CCC 最大。
情况 3（KIND=3）：新最小值仍为 MNMNMN
弧内不能出现 mnmnmn 或 mn+1mn+1mn+1，否则最小值会下降，所以弧必须落在连续满足
pre≥mn+2pre \ge mn+2 pre≥mn+2
的块里。这时弧内 mn+2mn+2mn+2 的位置会被压到 mnmnmn，相当于在原来的 g0g_0g0 上增加这些切口：
g=g_0+#(D\text{ 在弧内}).
std 扫描所有 pre≥mn+2pre\ge mn+2pre≥mn+2 的连续块，每块用 seg 求弧内 DDD 最大，取最优。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
参考代码
