官方题解 | 挑战赛#23 题解
本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目标题 难度 T1 NOON 入门 T2 maple序列 普及- T3 午枫的石子合并 普及- T4 午枫的彩排2 普及/提高- T5 午枫勇闯移动迷宫 普及/提高- T6 午枫的创造 普及+/提高
T1 NOON
题目大意
对于一个字符串，找出有多少个 "NOON" 子串。
解题思路
枚举所有可能位置，判断是否为 "NOON" 。
参考代码
T2 MAPLE序列
题目大意
在序列 aaa 中选出偶数个数，使得重新排列后可以变成 "maple序列" ，求 "maple序列" 长度的最大值。
解题思路
观察到本题 aia_iai 的数据范围很小，所以我们可以枚举 b1+b2b_1+b_{2}b1 +b2 的值，统计 "maple序列" 的长度，记录最大值即可。
参考代码
T3 午枫的石子合并
题目大意
有 nnn 堆石子，每次可以选择一堆将至多 kkk 个石子移动到相邻的石子堆中，求将所有石子合并到一堆所需要的最少操作次数。
解题思路
如果要将第 iii 堆石子合并到第 i+1i+1i+1 堆中，假设第 iii 堆有 xxx 个石子，所需要的操作次数为 ⌈xk⌉\lceil\frac{x}{k}\rceil⌈kx ⌉ 。
如果最终所有石子会合并到第 iii 堆中，由于中间计算过程中涉及到上去整，所以 [1,i−1][1,i-1][1,i−1] 堆一定是从第 111 堆向右合并的，[i+1,n][i+1,n][i+1,n] 堆一定是从第 nnn 堆向左合并的。我们可以先预处理合并前缀所需最小操作次数以及合并后缀最小操作次数。
所以我们可以枚举最终合并到哪一堆中，统计合并成一堆所需最小操作次数即可。
参考答案
T4 午枫的彩排2
题目大意
每次操作可以将任意个舞台灯光亮度 +1+1+1 或 −1-1−1 ，求所有舞台灯光调整为目标值的最少操作次数。
解题思路
首先我们会发现，如果同时对第 iii 个舞台使用 +1+1+1 操作和 −1-1−1 操作，答案一定不会变得更优。因此我们可以将所有数分成两类，一类只使用 +1+1+1 操作，一类只使用 −1-1−1 操作。
所以我们可以对每一个舞台都分别计算出只用 +1+1+1 操作和 −1-1−1 操作，并用 pair<int,int> 存储，按照第一关键词排序，此时不难发现，如果第 iii 个舞台灯光只用 +1+1+1 操作最优，那么 [1,i][1,i][1,i] 的舞台灯光都用 +1+1+1 操作最优，剩下的 [i+1,n][i+1,n][i+1,n] 都用 −1-1−1 操作。
因此可以预处理使用 −1-1−1 操作的后缀 maxmaxmax ，枚举分界点 iii ，计算第 iii 的花费和 i+1i+1i+1 的后缀 maxmaxmax 之和，统计最小值即可。
参考代码
T5 午枫勇闯移动迷宫
题目大意
有一个 n×mn\times mn×m 的迷宫，每个格子有一种颜色，每种颜色代表一种移动方向，最多改变 kkk 个格子的颜色，判断能否从 (1,1)(1,1)(1,1) 移动到 (n,m)(n,m)(n,m) 。
解题思路
考虑每个格子的上下左右四个移动方向，可以对相邻格子都建有向边，若当前格子地板的移动方向与要移动的方向相同，建一条边权为 000 的有向边，若方向不同，建一条边权为 111 的有向边。
于是问题就转化为了最短路问题，求出从 (1,1)(1,1)(1,1) 到达 (n,m)(n,m)(n,m) 需要花费的最小代价，若比 kkk 大，则无法逃离迷宫，否则，可以逃离迷宫。
参考代码
T6 午枫的创造
题目大意
对于一个字符串序列，可以修改任意一个位置的字符串，问最终有多少种可能，使得所有长度至少为 222 的字符串序列中的所有字符集合与原来的相同。
解题思路
首先由于每一个字符串中的字符不会重复且长度最大不会超过 262626 ，那么我们不妨将每个小写字母用二进制表示，这样每个字符串都可以用一个整数来表示。那么对于第三点要求，就转化成：对于所有 1≤l<r≤n1\leq l<r\leq n1≤l<r≤n，均有 al∣al+1∣...∣ar=bl∣bl+1∣...∣bra_l | a_{l+1}|...|a_r = b_l|b_{l+1}|...|b_ral ∣al+1 ∣...∣ar =bl ∣bl+1 ∣...∣br 。
接下来考虑如何满足题目要求的第两、三个条件。不难发现，当我们要修改位置 iii 的元素是，对于一个包含 iii 区间 [l,r][l,r][l,r] ，满足 al∣al+1∣...∣ar=bl∣bl+1∣...∣bra_l | a_{l+1}|...|a_r = b_l|b_{l+1}|...|b_ral ∣al+1 ∣...∣ar =bl ∣bl+1 ∣...∣br ，那么一定需要满足长度至少为 222 的区间按位或值不变。因此，我们只需要让 aia_iai 与其相邻的数按位或后的值不变即可。
假设当前的数为 aia_iai ，变化后的数为 bib_ibi 且 bi≠aib_i \ne a_ibi =ai ，与其相邻的数为 xxx ，那么对于每一位老说有以下几种情况：
* ai∣xa_i | xai ∣x 的这一位为 000 ，那么 bib_ibi 的这一位一定为 000 ；
* ai∣xa_i | xai ∣x 的这一位为 111 ，并且 xxx 的这一位为 000 ，那么 bib_ibi 的这一位一定为 000 ；
* ai∣xa_i | xai ∣x 的这一位为 111 ，并且 xxx 的这一位为 111 ，那么 bib_ibi 的这一位可以为 000 ，也可以为 111 .
综上，不难发现，只有第三种情况 bib_ibi 会有两种情况，我们统计有 cntcntcnt 位会出现这种情况，那么位置 iii 的方案数就有 2cnt2^{cnt}2cnt 个，由于需要满足 ai≠bia_i\ne b_iai =bi 这个条件，还要把方案数 −1-1−1 。
最后将所有位置的方案数相加，即为答案。
参考代码
