分治思想初窥之回文串

UVA - 10716

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

AC代码：

#include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<iostream> #include<algorithm> using namespace std; string a; int b[27]; bool solve1() { int t=0; memset(b,0,sizeof(b)); for(int i=0; i<a.size(); i++) { b[a[i]-'a']++; } for(int i=0; i<26; i++) { if(b[i]%2==1) { t++; } if(t>1) return 0; } return 1; } int solve2() { int len=a.size(); int begin1=0,end1=len-1,sum=0; while(end1>begin1) { int i,j,k,s=0; for(i=end1;a[i]!=a[begin1]; i--); for(j=begin1;a[j]!=a[end1];j++); if(end1-i<j-begin1) { for(k=i; k<end1; k++) a[k]=a[k+1]; sum+=end1-i; } else { for(k=j; k>begin1; k--) a[k]=a[k-1]; sum+=j-begin1; } ++begin1; --end1; } return sum; } int main() { int n; cin>>n; getline(cin,a); while(n--) { int pace=0; cin>>a; if(solve1()) { pace=solve2(); cout<<pace<<"\n"; } else cout<<"Impossible\n"; } return 0; }

解题思路： 1.从字符串两边向内寻找与边界相同的字母（边界若为中心字符时距离最大会被自动筛选掉，所以不用单独处理，若定住一边，则要但单独处理中心字符，较为麻烦） 2.逐渐缩小字符串范围，直至中心字符，记下交换相邻字符次数。 3.读入字符串用getline，若用scanf(“%s”,a); 或gets(a);则超时；（我也不知道为啥。。【郁闷】） 如下代码，超时；

#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; char a[8010]; int b[27],w; bool solve1() { int t=0; memset(b,0,sizeof(b)); for(int i=0; i<strlen(a); i++) { b[a[i]-'a']++; } for(int i=0; i<26; i++) { if(b[i]%2==1) { t++; w=i; } if(t>1) return 0; } return 1; } int solve2() { int len=strlen(a); int begin1=0,end1=len-1,sum=0; while(end1>begin1) { int i,j,k,s=0; for(i=end1;a[i]!=a[begin1]; i--); for(j=begin1;a[j]!=a[end1];j++); if(end1-i<j-begin1) { for(k=i; k<end1; k++) a[k]=a[k+1]; sum+=end1-i; } else { for(k=j; k>begin1; k--) a[k]=a[k-1]; sum+=j-begin1; } ++begin1; --end1; } return sum; } int main() { int n; cin>>n; while(n--) { int pace=0; scanf("%s",a); if(solve1()) { pace=solve2(); cout<<pace<<"\n"; } else cout<<"Impossible\n"; } return 0; }