首页 > 代码库 > [题解]UVA11027 Palindromic Permutation

[题解]UVA11027 Palindromic Permutation

2024-07-10 09:11:25   218人阅读

链接：http://vjudge.net/problem/viewProblem.action?id=19602

描述：给出一个字符串，求重新排列后第n个回文串，若没有则输出”XXX“。

思路：组合数问题。

        首先考虑什么时候有回文串。很简单，数量为奇数的字母不超过1个。且这个字母只能是在字符串的中间。

        然后我们会发现，回文串的字典序就是字串前半部分的字典序。问题就转化成求字典序第n的字符串。于是我们可以试着模拟一下这个过程。首先把字典序最小的字母放在第一个位置，然后计算出后面字母的排列数，即固定下第一个位置后有多少种字符串，设这个数是Num。如果Num>=n，则第一个位置就确定了，继续考虑第二个位置；如果Num<n，则第一个位置的字母不合适，n-=Num，更换成字典序第二的字母，重复上述计算。如果一直是Num<n，则无解。

        PS.zyy的数学不好，说得有点啰嗦，请各位大神不吝指教~

 

下面是我的实现：

  1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <cmath>  5 using namespace std;  6 #define MaxLen 30  7 int T,N;  8 int Cnt[30],Lit;  9 char str[MaxLen+5],Ans[MaxLen+5]; 10 bool flag; 11 inline int fac(int t) 12 { 13     if(t<=2) 14         return t; 15     int i,Ret=1; 16     for(i=2;i<=t;i++) 17         Ret*=i; 18     return Ret; 19 } 20 inline int Arg() 21 { 22     int i,Sum=0; 23     for(i=1;i<=26;i++) 24     { 25         if(!Cnt[i]) 26             continue; 27         Sum+=Cnt[i]; 28     } 29     Sum=fac(Sum); 30     for(i=1;i<=26;i++) 31     { 32         if(!Cnt[i]) 33             continue; 34         Sum/=fac(Cnt[i]); 35     } 36     return Sum; 37 } 38 void Work(int pos,int n) 39 { 40     int i,Num; 41     for(i=1;i<=26;) 42     { 43         if(!Cnt[i]) 44         { 45             i++; continue; 46         } 47         Cnt[i]--; 48         Num=Arg(); 49         if(Num==0) 50         { 51             Ans[pos]=‘a‘+i-1; 52             return; 53         } 54         else if(Num<n) 55         { 56             Cnt[i]++; 57             i++; 58             n-=Num; 59         } 60         else 61         { 62             Ans[pos]=‘a‘+i-1; 63             Work(pos+1,n); 64             return; 65         } 66     } 67     flag=false; 68 } 69 int main() 70 { 71     int Len,i,JS; 72     scanf("%d",&T); 73     for(int t=1;t<=T;t++) 74     { 75         printf("Case %d: ",t); 76         scanf("%s",str); scanf("%d",&N); 77         Len=strlen(str); Lit=(Len+1)/2; 78         if(Len==1) 79         { 80             if(N==1) 81                 printf("%s\n",str); 82             else 83                 printf("XXX\n"); 84             continue; 85         } 86         memset(Cnt,0,sizeof(Cnt)); 87         for(i=0;i<Len;i++) 88             Cnt[str[i]-‘a‘+1]++; 89         JS=0; 90         for(i=1;i<=26;i++) 91         { 92             if(Cnt[i]%2) 93             { 94                 JS++; 95                 Ans[Lit]=‘a‘+i-1; 96             } 97             Cnt[i]/=2; 98         } 99         if(JS>=2)100         {101             printf("XXX\n");102             continue;103         }104         flag=true;105         Work(1,N);106         if(!flag)107             printf("XXX\n");108         else109         {110             for(i=1;i<=Lit;i++)111                 printf("%c",Ans[i]);112             if(Lit*2==Len)113                 for(i=Lit;i>=1;i--)114                     printf("%c",Ans[i]);115             else116                 for(i=Lit-1;i>=1;i--)117                     printf("%c",Ans[i]);118             printf("\n");119         }120     }121     return 0;122 }
View Code

 


联系
我们