分治思想初窺之回文串

2019-11-06 07:19:16

字體：大中小

來源：轉載

供稿：網友

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

3mamadasflkjaabb

Sample Output

3Impossible2

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;}

上一篇：1001.Sum Problem

下一篇：1000. A + B Problem