本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16681444.html

过题情况

AC：6 / 8
排名：215

题目分析

判重即可

看看 $s$ 每一位是否分别对应 $t$

计算一下从 $i$ 分别转到 $p_i-1,p_i,p_i+1$ 分别要多少步，则当前对这三个选择的贡献加1

最后扫一遍统计最大贡献

首先枚举 $s$ 的全排列，然后枚举任意 $s$ 中插入多少个 _，然后再判重

判重的过程直接暴力会爆掉，哈希一下即可

加入从 $i$ 到 $p_i$ 要 $k$ 步，则此时它对 $k$ 的代价是0

然后随着步数增长其对当前步数的代价必然是先增大后减小，所以枚举一下转折点，差分一下最后扫一遍即可

细节有点多，主要是要考虑初始状态，维护初始状态的代价和接下来的变化

显然，块内代价可以预处理

然后我们再处理两个数组 $a_i,c_i$ ，分别代表 $S_i$ 中 X 的个数和非 X 数的和

假设最后构造了一种序列 $T$ ，考虑相邻两个 $T_i,T_{i+1}$ 有没有交换的必要

首先这两个如果单独交换对其它 $T_j$ 是没影响的

而原先的贡献是 $a_i\times c_{i+1}$ ，而交换后的代价是 $a_{i+1}\times c_i$

由于 $T$ 是最终构造序列，所以必然满足 $a_i\times c_{i+1}\geq a_{i+1}\times c_i$

移项得 $\dfrac{a_i}{c_i}\geq \dfrac{a_{i+1}}{c_{i+1}}$

由于任意相邻两项都符合这个原则，所以按 $\dfrac{a_i}{c_i}$ 从大到小排序即可