| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 1799 | Accepted: 523 |
Description
Input
Output
Sample Input
3 mamad asflkj aabb
Sample Output
3 Impossible 2
题意：一个字符串变成回文最少要几次
题解：
1、用回文的性质判断是否可以变成回文：个数为奇数的字母出现的次数小于等于1
2、从字符串的两端出发（l，r）,在字符串两端同时找能使s[l]==s[r]的位置，
3、取使左右两端相等步数最少的那一端，并从内到外交换位置（若从外到内交换会疯狂WA）
#include<iostream> #include<algorithm> #include<string.h> #include<string> #include<vector> #include<stack> #include<math.h> #define mod 998244353 #define ll long long #define MAX 0x3f3f3f3f using namespace std; int vis[26]; string s; int check(string ss) { int cnt=0; memset(vis,0,sizeof(vis)); for(int i=0;i<ss.length();i++) vis[ss[i]-‘a‘]++; for(int i=0;i<26;i++) { if(vis[i]%2==1) cnt++; } if(cnt>1) return 1; else return 0; } int main() { int n,ans; cin>>n; while(n--) { ans=0; cin>>s; if(check(s)) cout<<"Impossible"<<endl; else { int len=s.length(),l,r,j,mid,x=MAX,y=MAX; for(int i=0;i<len/2;i++) { l=i; r=len-1-i; if(s[l]!=s[r]) { for(j=l+1;s[j]!=s[r];j++); x=j; for(j=r-1;s[j]!=s[l];j--); y=j; if(x-l>r-y) { ans=ans+r-y; for(int j=y;j<r;j++) s[j]=s[j+1]; } else { ans=ans+x-l; for(int j=x;j>l;j--) s[j]=s[j-1]; } } } cout<<ans<<endl; } } return 0; }
poj 1854 Evil Straw Warts Live 变成回文要几次
原文：https://www.cnblogs.com/-citywall123/p/11216852.html