题目名称	418. [HAOI 2009]求回文串
输入输出	`string!.in/out`
难度等级	★★★
时间限制	3000 ms (3 s)
内存限制	128 MiB
测试数据	10
题目来源	cqw 于2010-04-08加入
开放分组	全部用户
提交状态
分类标签	HAOI 字符串贪心线段树
	分享题解

通过：53，提交：121，通过率：43.8%
Pine	100	0.233 s	16.53 MiB	C++
Wei	100	0.238 s	22.38 MiB	C++
thomount	100	0.314 s	16.50 MiB	C++
tswdfop	100	0.322 s	12.95 MiB	C++
tswdfop	100	0.327 s	12.95 MiB	C++
QwQ	100	0.346 s	16.52 MiB	C++
tswdfop	100	0.384 s	12.95 MiB	C++
tswdfop	100	0.489 s	112.12 MiB	C++
QwQ	100	0.500 s	115.68 MiB	C++
董泽新	100	0.521 s	10.80 MiB	C++

关于求回文串的近10条评论(全部评论)
... 不存在的 2017-04-28 22:24 9楼
... 不存在的 2017-04-28 22:24 8楼
贪心的想法是，对于同一个字母，一定是由两边向中间逐一配对，这样就可以先O(n)处理出在最终的回文串中位置对称的字母对。然后对字母重新标号。于是字母变成了互不相同的编号。然后，还是贪心的想法：先把最终位置在左边的移动到左边，最终位置在右边的移动到右边。然后就可以求逆序对了。。（常数似乎比较小）然而最开始傻呵呵地忘记将该在右边的移动到右边了。。。 thomount 2016-04-19 11:52 7楼
回复 @0_0 : stdafx.h 2015-12-14 16:34 6楼
向@stdafx 同志致以崇高敬意！ lenibomb 2015-08-07 19:50 5楼
stdafx.h 2015-08-07 19:49 4楼
............三星题目，怎么做啊？？？ forever 2015-08-07 15:08 3楼
树状数组比线段树快QAQ 水中音 2015-01-16 17:12 2楼
feng 2013-03-05 11:15 1楼

418. [HAOI 2009]求回文串

★★★ 输入文件：string!.in 输出文件：string!.out 简单对比
时间限制：3 s 内存限制：128 MiB

【题目描述】

所谓回文串，就是对于给定的字符串，正着读和反着读都一样，比如 $ABCBA$ 就是一个回文串， $ABCAB$ 则不是。我们的目标是对于任意输入的字符串，不断将第 $i$ 个字符和第 $i+1$ 个字符交换，使得该串最终变为回文串。求最少交换次数。

【输入格式】

包含一个由大写字母字母组成的字符串。

【输出格式】

输出一个整数。若能经过有限次操作能将原串变为回文串，则输出最少操作次数；否则输出 -1 。

【样例输入】

SHLLZSHZS

【样例输出】

【样例说明】

$1$ ．交换 $L$ 和 $Z$ 变成 $SHL$ $ZL$ $SHZS$

$2$ ．交换 $L$ 和 $Z$ 变成 $SH$ $ZL$ $LSHZS$

$3$ ．交换 $L$ 和 $S$ 变成 $SHZL$ $SL$ $HZS$

$4$ ．交换 $H$ 和 $Z$ 变成 $SHZLSL$ $ZH$ $S$

【数据规模与约定】

$40\%$ 的数据， $N ≤ 50000$；

$100\%$ 的数据，$N ≤ 10^6$。