POJ 1854

Description

A palindrome is a string of symbols that is equal to itself when reversed. Given an input string, not necessarily a palindrome, compute the number of swaps necessary to transform the string into a palindrome. By swap we mean reversing the order of two adjacent symbols. For example, the string "mamad" may be transformed into the palindrome "madam" with 3 swaps:
swap "ad" to yield "mamda"
swap "md" to yield "madma"
swap "ma" to yield "madam"

Input

The first line of input gives n, the number of test cases. For each test case, one line of input follows, containing a string of up to 8000 lowercase letters.

Output

Output consists of one line per test case. This line will contain the number of swaps, or "Impossible" if it is not possible to transform the input to a palindrome.

Sample Input

3
mamad
asflkj
aabb

Sample Output

3
Impossible
2

Source

Waterloo local 2004.09.19

输入一串字符，先判断是否可以通过变换顺序变成回文串，不是的话输出impossible。

然后如果possible，定义一次swap相邻两个字母为一步，计算这个字符串经过最少多少次swap可以变为回文串。

具体思维：使用分治的方法……

每次搞定最左边和最右边的两个字母，也就是从外向内一层层做成回文串。

比如 abcbac 这个，先看最左边的“a”，从最右边开始遍历字符串，找到的第一个“a”就可以经过最少次数把右边变成“a”，

再看最右边的“c”，同样的，从最左边遍历字符串，找到的第一个“c”就可以经过最少次数把右边变成“c”,

比较一下是把最外层变成两个a还是两个c……哪个划算，就加上这个步数，把字符串最外层排好：“abcbca”，then去掉最外层变成：“bcbc”，继续重复上面的工作……

 1 #include<cstring>
 2 #include<string>
 3 using namespace std;
 4 void swap_palindrome(char s[],int begin,int end,int &step)
 5 {
 6     if(end-begin<=1) return;
 7     int i,left_distance,right_distance;
 8     for(i=begin;i<end;i++) if(s[i]==s[end]) break;
 9     left_distance=i-begin;
10     for(i=end;i>begin;i--) if(s[i]==s[begin]) break;
11     right_distance=end-i;
12     if(left_distance<right_distance){
13         step+=left_distance;
14         for(int i=left_distance+begin;i>begin;i--) swap(s[i],s[i-1]);
15     }else{
16         step+=right_distance;
17         for(int i=end-right_distance;i<end;i++) swap(s[i],s[i+1]);
18     }
19     swap_palindrome(s,begin+1,end-1,step);
20 }
21 int is_palindrome(char s[])
22 {
23     int letter[26]={0},len=strlen(s);
24     for(int i=0;i<len;i++) letter[ (s[i]-'a') ]++;
25     int count=0;
26     for(int i=0;i<26;i++){
27         if(letter[i]%2==1) count++;
28     }
29     if(count>1) return 0;
30     else return 1;
31 }
32 int main()
33 {
34     int n;scanf("%d",&n);
35     char s[8001];
36     while(n--){
37         scanf("%s",s);
38         if(!is_palindrome(s)) printf("Impossible
");
39         else{
40             int begin=0,end=strlen(s)-1,step=0;
41             swap_palindrome(s,begin,end,step);
42             printf("%d
",step);
43         }
44     }
45     return 0;
46 }

另外……这题，刚开始我用了string类型，cin输入，迭代器遍历……就time limit exceeded……