巅峰赛35题解
本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目标题 难度 T1 午枫的电路谜题 普及- T2 小安的括号调整 普及/提高- T3 午枫的图书馆 普及/提高- T4 小枫的排列谜题 普及/提高- T5 小枫的密码锁 普及+/提高 T6 小枫的三角形游戏 普及+/提高
T1 午枫的电路谜题
题目大意
每个灯连接两个开关，灯的状态等于这两个开关被“翻转”的次数奇偶性（即两个开关状态之和 mod 2\bmod 2mod2）。
例如某个灯连接两个开关：
* 若它们都是 000 或都是 111，则该灯为关闭；
* 若一个是 000，一个是 111，则该灯为开启。
问题转化为：将 2n2n2n 个开关两两配对，使得每对的异或结果（是否不同）决定灯是否亮。
题目思路
这题的关键在于理解灯的状态。每个灯连接两个开关，而灯是否亮取决于这两个开关被翻转的次数之和的奇偶性，其实就是这两个开关状态的异或值。
所以问题变成：把 2n2n2n 个数分成 nnn 对，每一对如果是 (0,1)(0,1)(0,1) 或 (1,0)(1,0)(1,0)，这一对贡献一个亮灯；如果是 (0,0)(0,0)(0,0) 或 (1,1)(1,1)(1,1)，这一对贡献 000。
设数组中 111 的个数是 cntcntcnt，那么 000 的个数就是 2n−cnt2n - cnt2n−cnt。
先考虑最大值。为了让亮灯数量最多，我们应该尽量多配出 (0,1)(0,1)(0,1) 对。显然最多能配 min(cnt,2n−cnt)min(cnt, 2n-cnt)min(cnt,2n−cnt) 对这样的组合。
再考虑最小值。我们希望尽量避免 (0,1)(0,1)(0,1)，也就是尽量把相同的配在一起：(0,0)(0,0)(0,0) 和 (1,1)(1,1)(1,1)。能做到的最大数量分别是 ⌊cnt2⌋\lfloor \frac{cnt}{2} \rfloor⌊2cnt ⌋ 和 ⌊2n−cnt2⌋\lfloor \frac{2n-cnt}{2} \rfloor⌊22n−cnt ⌋。剩下如果还有无法配的，就必须产生 (0,1)(0,1)(0,1)。
最终可以发现，最少亮灯数就是 cnt%2cnt \% 2cnt%2。
因此答案为：
* 最少：cnt%2cnt \% 2cnt%2
* 最多：min(cnt,2n−cnt)min(cnt, 2n - cnt)min(cnt,2n−cnt)
参考代码
T2 小安的括号调整
题意简述
给定一个长度为 2N2N2N 的括号串 SSS，可以交换任意两个字符（代价 AAA）或替换单个字符（代价 BBB），求将其变为合法括号序列的最小总代价。
解题思路
首先去掉 SSS 中所有能够匹配的括号对。具体做法是：从左到右扫描，维护当前未匹配的左括号数，遇到 ( 则记录，遇到 ) 且存在未匹配的左括号时就消去一对。这样剩下的是一个形如 ))...)((...( 的串，即若干个右括号后接若干个左括号。设剩余串中左括号数为 LLL，右括号数为 RRR。
这些剩余的括号无法互相匹配，必须通过操作消除。每消除一对 ()（即一个多余右括号和一个多余左括号）的最小代价是 min(A,2B)\min(A, 2B)min(A,2B)，因为可以用一次交换（代价 AAA）或两次替换（代价 2B2B2B）。如果某一种括号有剩余（全是左括号或全是右括号），则它们只能两两配对，每对需要两次替换，代价 2B2B2B，若剩余奇数个则还需额外 2B2B2B。按照这个思路计算代价即可。
参考代码
T3 午枫的图书馆
题意简述
有 NNN 张书桌环形排列，第 iii 张书桌和第 i+1i+1i+1 张之间有一把椅子（第 NNN 张与第 111 张之间为第 NNN 把椅子）。NNN 个同学按排列 PPP 的顺序依次取椅子：每人优先取自己惯用手同侧的椅子（如果该侧椅子还在），否则取另一侧，若两侧都无则失败。给定字符串 SSS 表示某些同学的惯用手固定为 L 或 R，其余可任选。求有多少种给 ? 指定 L/R 的方式，使得最终每人恰好拿到一把椅子。
解题思路
观察发现，每个同学的取椅决策只与其两侧椅子的剩余情况有关。由于环形结构，最终每人拿到一把椅子等价于：按顺序处理时，每个人至少有一侧椅子可用，且整个流程结束时椅子恰好被取完。这是一个经典的环形匹配问题，实际上只有当所有同学按顺序“抢占”椅子时，每个人的惯用手选择必须与椅子被取走的顺序相匹配。
将椅子视为位置 111 到 NNN，其中椅子 iii 位于书桌 iii 和 i+1i+1i+1 之间。同学 iii（即坐在书桌 iii 的人）能取到的椅子是 i−1i-1i−1（左侧）或 iii（右侧，其中 i=Ni=Ni=N 时右侧为 111 号椅子）。按排列 PPP 的顺序，每个人会优先选择自己惯用手对应的那侧椅子。要使最后全部椅子被取走，本质上需要排列 PPP 与惯用手的选择构成一个无冲突的定向匹配。
第一次扫描：对于每个同学 pip_ipi ，检查其右侧椅子 pi%n+1p_i \% n + 1pi %n+1 是否被标记，若被标记则说明右侧已无，再看左侧 pip_ipi 是否被标记：若两侧都已标记则失败；若两侧都空且该同学为 ?，则有两种选择（乘 2）；否则只能取未被标记的一侧。扫描结束后标记取走的椅子。第二次扫描对称处理，将左右交换。两种方向对应了环上两种可能的“旋转”匹配方式，相加即为总方案数。
参考代码
T4 小枫的排列谜题
题意简述
给定一个长度为 nnn 的排列 ppp，求满足 a<b<c<da<b<c<da<b<c<d 且 pa<pcp_a < p_cpa <pc 且 pb>pdp_b > p_dpb >pd 的四元组 (a,b,c,d)(a,b,c,d)(a,b,c,d) 的数量。
解题思路
枚举中间的两个位置 bbb 和 ccc（b<cb < cb<c）。对于固定的 b,cb,cb,c，需要统计左边满足 a<ba < ba<b 且 pa<pcp_a < p_cpa <pc 的 aaa 的数量，以及右边满足 d>cd > cd>c 且 pd<pbp_d < p_bpd <pb 的 *** 的数量，两者相乘累加。由于 n≤5000n \le 5000n≤5000，可以用 O(n2)O(n^2)O(n2) 预处理或直接枚举。
更高效的做法是：先预处理 dp[i]dp[i]dp[i] 表示 iii 右边比 pip_ipi 小的数的个数。然后从左到右枚举 ccc，维护左侧比 pcp_cpc 小的数的个数和对应贡献，动态更新并累加。
参考代码
T5 小枫的密码锁
题意简述
密码长度为 NNN，每位可填 111 到 MMM。对每个数字 BBB，要求任意两个 BBB 之间的闭区间内必须至少出现一次 XBX_BXB 。求合法密码数，对 998244353998244353998244353 取模。
解题思路
考虑每个数字 BBB 出现后，在下次出现之前必须见到 XBX_BXB ，这类似一种“依赖”关系。将每个数字是否还在等待其依赖数字的状态压缩成 MMM 位二进制。初始时，所有数字都未出现，但为了处理边界，设初始状态为所有数字都“已满足”（即全 111）。用 dp[i][mask]dp[i][mask]dp[i][mask] 表示前 iii 位后，当前哪些数字正在等待其依赖数字的状态。填入数字 jjj 时，只有当 jjj 当前不处于等待状态（即 maskmaskmask 中 jjj 位为 111）时才能填入。填入后，jjj 变为等待状态（因为它下次出现需要 XjX_jXj ），同时 jjj
的出现会满足所有依赖 jjj 的数字（即 XB=jX_B = jXB =j 的那些 BBB），将它们从等待状态中清除。用 mask[j]mask[j]mask[j] 表示填入 jjj 后可以清除的集合，转移为 dp[i+1][(mask⊕(1<<j−1))∣mask[j]]+=dp[i][mask]dp[i+1][(mask \oplus (1<<j-1)) | mask[j]] += dp[i][mask]dp[i+1][(mask⊕(1<<j−1))∣mask[j]]+=dp[i][mask]。答案即为 ∑dp[N][mask]\sum dp[N][mask]∑dp[N][mask]。
参考代码
T6 小枫的三角形游戏
题意简述
正 nnn 边形顶点有权值 aia_iai ，每次选三个未选过的顶点构成三角形，且三角形内部不能与已有三角形重叠，得分增加三个顶点权值乘积。求最大总得分。
解题思路
合法三角形集合对应多边形的一种三角剖分。设 dp[i][j]dp[i][j]dp[i][j] 表示顶点 iii 到 jjj 按顺序构成的子多边形（边数 ≥2\ge 2≥2）能获得的最大得分。转移时考虑顶点 iii 和 jjj 之间的边，有两种情况：
1. 在子多边形中取一个三角形 (i,j,k)(i,j,k)(i,j,k)，则多边形被分成 (i+1,k−1)(i+1,k-1)(i+1,k−1) 和 (k+1,j−1)(k+1,j-1)(k+1,j−1) 两部分，加上三角形贡献，即 dp[i][j]=max{dp[i+1][k−1]+dp[k+1][j−1]+aiajak}dp[i][j] = \max\{dp[i+1][k-1] + dp[k+1][j-1] + a_i a_j a_k\}dp[i][j]=max{dp[i+1][k−1]+dp[k+1][j−1]+ai aj ak }。
2. 不取与边 (i,j)(i,j)(i,j) 相关的三角形，而是将多边形分成两段，即 dp[i][j]=max{dp[i][k]+dp[k+1][j]}dp[i][j] = \max\{dp[i][k] + dp[k+1][j]\}dp[i][j]=max{dp[i][k]+dp[k+1][j]}。
取所有情况的最大值即可。最终答案为 dp[1][n]dp[1][n]dp[1][n]。
参考代码
