巅峰赛36 题解
本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目标题 难度 T1 午枫的传话游戏 普及/提高- T2 午枫的教室路线 普及/提高- T3 午枫的数字替换 普及/提高- T4 午枫的课堂笔记 普及/提高- T5 午枫的自习时间 普及+/提高 T6 午枫的涂色方案 普及+/提高
T1 午枫的传话游戏
题意简述
有 nnn 个同学，每人有一个数字 aia_iai 。若两数绝对差为 111 则可直接传话，传话关系具有传递性。求最少添加多少对直接传话关系，使得整个图连通（任意两人可互相传话）。
解题思路
将数字视为节点，值相等的同学共享同一节点（他们之间差值为 000，需要额外处理）。先对数组排序去重分析连续段：如果两个相邻数值相差为 111，则它们天然有边相连；若相差 >1>1>1，则这两段之间需要添加一条边来连通。因此，数值轴上会形成若干个由差值为 111 的连续段构成的连通块。
对于同一数值有多人的情况：这些人内部没有直接边（差值 000），他们必须借助相邻数值才能连通。如果一个连通块中只有一个数值（左右均断），那么该数值内的 ttt 个同学需要 t−1t-1t−1 条边才能内部连通，并且还需与外部块连接。当连通块有多个数值时，块内的所有同学可通过链式结构自然连通，只需向外连边时添加一条边。
边数最少为 max(0,连通块数−1)+∑(孤立数值内部人数−1)\max(0, \text{连通块数} - 1) + \sum(\text{孤立数值内部人数} - 1)max(0,连通块数−1)+∑(孤立数值内部人数−1)。
参考代码
T2 午枫的教室路线
题意简述
有一个 H×WH \times WH×W 的网格，从 (1,1)(1,1)(1,1) 走到 (H,W)(H,W)(H,W)，每次只能向下或向右。给定一个长度为 H+W−2H+W-2H+W−2 的字符串 SSS，其中 D 表示这一步必须向下，R 表示必须向右，? 表示可以自由选择向下或向右。对于每一种合法的路径，我们把该路径经过的所有格子（包括起点和终点）标记为已访问。问在所有合法路径中，最多能有多少个不同的格子被至少一条路径访问到。
解题思路
令必须向下的步数为 DfixD_{fix}Dfix ，必须向右的步数为 RfixR_{fix}Rfix ，自由步中需选 n=H−1−Dfixn = H-1-D_{fix}n=H−1−Dfix 步为向下、m=W−1−Rfixm = W-1-R_{fix}m=W−1−Rfix 步为向右。问题等价于求有多少格子 (i,j)(i,j)(i,j) 存在一种 ? 的赋值，使得路径经过该格。
考虑格子 (i,j)(i,j)(i,j)，到达它需要 k=i+j−2k = i+j-2k=i+j−2 步，其中向下 i−1i-1i−1 步。设前 kkk 步中必须向下 dkd_kdk 步、必须向右 rkr_krk 步、自由 sks_ksk 步。后 L=H+W−2−kL = H+W-2-kL=H+W−2−k 步中必须向下 dL′d'_LdL′ 步、自由 sL′s'_LsL′ 步。存在合法路径经过 (i,j)(i,j)(i,j) 当且仅当存在整数 xxx（前 kkk 步中选择向下的自由步数）满足：
* i−1=dk+xi-1 = d_k + xi−1=dk +x，即 x=i−1−dkx = i-1-d_kx=i−1−dk
* 0≤x≤sk0 \le x \le s_k0≤x≤sk ，且 x≤nx \le nx≤n
* H−i=dL′+(n−x)H-i = d'_L + (n-x)H−i=dL′ +(n−x)，即 n−x=H−i−dL′n-x = H-i-d'_Ln−x=H−i−dL′
* 0≤n−x≤sL′0 \le n-x \le s'_L0≤n−x≤sL′
消去变量后，固定 kkk 时 iii 的取值范围为：
max(dk+1, k−min(sk,m)−rk+1)≤i≤min(min(sk,n)+dk+1, k−rk+1)\max(d_k+1,\; k - \min(s_k, m) - r_k + 1) \le i \le \min(\min(s_k, n) + d_k + 1,\; k - r_k + 1) max(dk +1,k−min(sk ,m)−rk +1)≤i≤min(min(sk ,n)+dk +1,k−rk +1)
其中 n=H−1−Dfixn = H-1-D_{fix}n=H−1−Dfix ，m=W−1−Rfixm = W-1-R_{fix}m=W−1−Rfix 。每个 iii 对应格子 (i,k+2−i)(i, k+2-i)(i,k+2−i)。
遍历 k=0k = 0k=0 到 H+W−2H+W-2H+W−2，累加每个 kkk 对应的合法 iii 的个数，即为答案。起点 k=0k=0k=0 和终点 k=H+W−2k=H+W-2k=H+W−2 自动包含在内。
参考代码
T3 午枫的数字替换
题意简述
给定一个长度为 NNN 的数字串 SSS 和一个长度为 MMM 的数字串 TTT，按顺序进行 MMM 次操作，第 kkk 次操作可以将 SSS 的任意一个位置替换为 TTT 的第 kkk 个字符。每次替换会覆盖原有数字。问经过全部 MMM 次操作后，得到的 SSS 作为整数值最大是多少，输出这个字符串。
解题思路
我们依次进行 MMM 次替换，每次可以选任意位置。最后一次操作特别重要，因为它不会被后续操作覆盖。如果我们把某个数字放在最后一次操作中，它就会永远留在最终字符串的那个位置上。
为了使得最终字符串的字典序最大，我们希望前面的字符尽可能大。因此，一个直观的贪心策略是：除了最后一次操作的数字以外，前面的 M−1M-1M−1 次操作我们可以自由选择用哪些数字去替换哪些位置。我们把这 M−1M-1M−1 个数字从大到小排序，然后从左到右扫描 SSS 的每个位置，如果当前最大的可用数字比 SSS 这个位置上的数字大，就进行替换，然后这个数字被消耗掉，继续看下一个位置。这样可以保证在前面的位置上尽量使用大的数字。
接下来考虑最后一次操作的数字 TMT_MTM 。它必须被用到某个位置上。如果在前面的贪心过程中，TMT_MTM 已经被当作一个较大的数字使用过了（即它已经被换到了某个位置上），那就不用再额外处理。如果没有被使用过，说明 TMT_MTM 比 SSS 中所有未被替换过的位置上的数字都小（因为贪心过程中只有遇到更大的数字才会替换）。此时，我们只能把它放在某个位置上，为了对整个字符串的字典序影响最小，应该把它放在最后一位。因为放在任何更前面的位置都会使得那个位置变小，从而让整个字符串变小，而放在末尾只会影响最后一位，前面的大数字结构保持不变。
这样操作后，得到的字符串就是最大的可能结果。
参考代码
T4 午枫的课堂笔记
题意简述
按顺序处理 NNN 个数，对每个数必须恰好执行一次操作：要么写入到笔记板末尾，要么删除笔记板末尾的一个数（板为空时不能删除）。操作结束后，笔记板中剩余数的和即为结果。求最大可能和。
解题思路
定义 f[i][0]f[i][0]f[i][0] 表示处理完前 iii 个数且第 iii 步执行删除操作时，当前栈中数字和的最大值；f[i][1]f[i][1]f[i][1] 表示第 iii 步执行写入操作时的最大值。
若第 iii 步是删除，则它必须删除上一步刚写入的数，因此第 i−1i-1i−1 步必须是写入，删除后状态回到第 i−2i-2i−2 步之后的状态，故 f[i][0]=max(f[i−2][0],f[i−2][1])f[i][0] = \max(f[i-2][0], f[i-2][1])f[i][0]=max(f[i−2][0],f[i−2][1])。
若第 iii 步是写入，则直接加上 AiA_iAi ，可以从第 i−1i-1i−1 步的任意状态转移来，即 f[i][1]=max(f[i−1][0],f[i−1][1])+Aif[i][1] = \max(f[i-1][0], f[i-1][1]) + A_if[i][1]=max(f[i−1][0],f[i−1][1])+Ai 。
初始条件 f[1][0]f[1][0]f[1][0] 不合法（第一步不能删除），设为负无穷；f[1][1]=A1f[1][1] = A_1f[1][1]=A1 。最终答案为 max(f[N][0],f[N][1])\max(f[N][0], f[N][1])max(f[N][0],f[N][1])。
参考代码
T5 午枫的自习时间
题意简述
给定一个长度为 NNN 的字符串 SSS，由 o 和 x 组成。将 SSS 重复 MMM 次得到字符串 TTT（长度为 N×MN \times MN×M）。你可以将 TTT 中恰好 KKK 个 x 改为 o。问修改后最长的连续 o 子串长度最大是多少。
解题思路
设 SSS 中 x 的总数为 cntcntcnt。由于 MMM 可能很大（10910^9109），不能直接构造 TTT。考虑分情况讨论。
首先，如果 M=1M = 1M=1 或 M=2M = 2M=2，可以直接构造出 TTT（长度最多 2N≤6×1052N \le 6\times 10^52N≤6×105），然后用双指针（滑动窗口）求最多包含 KKK 个 x 的最长区间即可。
当 M≥3M \ge 3M≥3 时，考虑在完整的若干个 SSS 块中，每块有 cntcntcnt 个 x。设 num=⌊K/cnt⌋num = \lfloor K / cnt \rfloornum=⌊K/cnt⌋，即可以完全填满的块数。分三种情况：
* 若 num≥Mnum \ge Mnum≥M，则所有 MMM 个块都可以完全填成 o，答案为 N×MN \times MN×M。
* 若 num=M−1num = M-1num=M−1，则前 M−1M-1M−1 个完整的块可以全部填满，剩下 K′=K−(M−1)×cnt+cntK' = K - (M-1) \times cnt + cntK′=K−(M−1)×cnt+cnt 次调整机会（注意这里 STD 中写的是 k = k % cnt + cnt，相当于先消耗掉 M−1M-1M−1 个整块，剩下的 kkk 可能小于 cntcntcnt，但为了充分利用，实际上是在两个块中寻找最长的区间，最后加上 (M−2)×N(M-2) \times N(M−2)×N 作为中间已填满的块的长度）。
* 若 num≤M−2num \le M-2num≤M−2，则中间有 numnumnum 个完整填满的块，剩下的 K′=K%cntK' = K \% cntK′=K%cnt 次调整机会用于在前后两个块中跨越拼接。同样用双指针在 S+SS+SS+S 上找最多包含 K′K'K′ 个 x 的最长区间，然后加上 num×Nnum \times Nnum×N 作为中间完整块的长度。
关键点在于：当 MMM 很大时，最优解一定由若干完整填满的 o 块加上两端部分块内扩展得到的连续区间组成。通过在 S+SS+SS+S 上运行滑动窗口（最多包含 K%cntK \% cntK%cnt 或 K%cnt+cntK \% cnt + cntK%cnt+cnt 个 x），可以求出跨越两个块边界时的最大长度，再加上中间完整块的总长度即可。
参考代码
T6 午枫的涂色方案
题意简述
一排 NNN 个座位，初始状态第 iii 个座位上的数字为 i mod 2i \bmod 2imod2，即 1,0,1,0,…1,0,1,0,\dots1,0,1,0,… 交替。每次操作可以选择两个位置 lll 和 rrr 满足 l+1<rl+1<rl+1<r，且 lll 和 rrr 上的数字相同，而 (l,r)(l,r)(l,r) 内的所有数字都与 lll 不同，然后将 (l,r)(l,r)(l,r) 内所有数字改为 lll 上的数字。给定目标状态 A1,…,ANA_1,\dots,A_NA1 ,…,AN ，问有多少种不同的操作序列（操作次数不同或某一步的 (l,r)(l,r)(l,r)
不同都算不同）能从初始状态变成目标状态，答案对 998244353998244353998244353 取模。
解题思路
首先无解条件：A1A_1A1 必须为 111（位置 111 永远不会被修改），ANA_NAN 必须等于 N mod 2N \bmod 2Nmod2（位置 NNN 也不会被修改）。否则答案为 000。
将初始序列视为 NNN 个长度为 111、颜色交替的连续段。一次操作选择三个连续段（左、中、右），其中左右颜色相同、中间相反，操作后三段的中间段变为左右颜色，三段合并为一段。因此操作只合并相邻的相同颜色段，且每次减少两个段。
最终目标 AAA 划分成若干连续同色段。每个段的长度必须为奇数（因为每次合并三个奇数长度段得到奇数长度段，从 111 开始只能得到奇数）。若任何一段长度为偶数，答案为 000。
对于长度为 L=2k+1L=2k+1L=2k+1 的段，它由 2k+12k+12k+1 个初始段合并而成，需要 kkk 次操作。其内部合并方案数为 f(k)=(2k−1)!!=∏i=1k(2i−1)f(k) = (2k-1)!! = \prod_{i=1}^{k} (2i-1)f(k)=(2k−1)!!=∏i=1k (2i−1)。
设最终有 ccc 个段，半长度分别为 k1,…,kck_1,\dots,k_ck1 ,…,kc （即段长为 2ki+12k_i+12ki +1），总操作数 K=∑kiK = \sum k_iK=∑ki 。不同段之间的操作可以任意交错，穿插方案数为多重组合数 K!∏ki!\frac{K!}{\prod k_i!}∏ki !K! 。
因此总方案数为：
(∏i=1cf(ki))×K!∏ki!\left(\prod_{i=1}^{c} f(k_i)\right) \times \frac{K!}{\prod k_i!} (i=1∏c f(ki ))×∏ki !K!
预处理阶乘、逆元及 f(k)f(k)f(k) 即可 O(N)O(N)O(N) 计算。
参考代码
