NOIP2022

字符串

回文类

给定一个字符串 a，你每次可以交换 a 的相邻两个字符，问最少进行多少次交换才能使得 a 变为回文串。数据保证一定能够在有限次交换操作后使得 a 变为回文串。保证有解

样例

abcab
1

对于 100%的数据，1≤|a|≤1e6

想到回文串——> 对称性质——>奇数个还是偶数个讨论——>

1. 奇数个去掉中间那个可以变成偶数个。如果是奇数个，那么必然有一个字符是奇数个。把中间的字符替换后就能转化为偶数类。
2. 回文串左右两边是对称的，考虑一边的状态
3. 难点：你需要从交换相邻的两个字符联想到逆序对，可以证明从小到大排是最优策略
证明：在从小到大排的前提下你能想到逆序对的个数就是答案。如果有两个字符是逆序对，那么交换这两个字符，你就能使逆序对的个数减一。考虑两边是对称的。另一半对应的两个字符也必须交换，逆序对的个数可能再减一或者加一。说明这种变换是不劣的。
逆序对用树状数组可以NlogN解决。

原文地址：http://www.cnblogs.com/zychh/p/16844715.html