#P1854. Evil Straw Warts Live

Evil Straw Warts Live

本题没有可用的提交语言。

题目描述

回文串是指正读反读都相同的字符串。给定一个任意字符串(不一定是回文),计算通过相邻字符交换将其转换为回文串所需的最少交换次数。每次交换定义为反转两个相邻字符的顺序。

例如,字符串 "mamad" 可以通过以下33次交换变为回文串 "madam"
11. 交换 "ad""mamda"
22. 交换 "md""madma"
33. 交换 "ma""madam"

输入格式

- 第一行:测试用例数量nn
- 接下来nn行:每行一个长度不超过80008000的小写字母字符串。

输出格式

- 对于每个测试用例,输出最少交换次数;若无法转换为回文串,输出 "Impossible"

样例输入 1

3
mamad
asflkj
aabb

样例输出 1

3
Impossible
2

来源

Waterloo local 2004.09.19

关键思路

11. 回文可行性检查:统计字符频率,若超过一个字符出现奇数次,则无法构成回文。
22. 贪心交换策略
- 从字符串两端向中间遍历,若两端字符不同,则在内侧找到匹配字符并通过相邻交换移至对应位置。
- 每次交换的步数计入总次数。
33. 奇数长度处理:若字符串长度为奇数,允许中心字符不匹配,但需确保其余字符成对出现。

示例解析

- "mamad"
- 步骤1:左'm'=右'd' → 交换'a''d'"mamda"11次)。
- 步骤2:左'a'≠右'a' → 交换'm''d'"madma"22次)。
- 步骤3:左'm'≠右'm' → 交换'a''m'"madam"33次)。
- "asflkj":字符频率不满足回文条件,直接输出 "Impossible"
- "aabb":通过交换'b'和相邻字符(22次)得到 "abba"