[题解]UVA11027 Palindromic Permutation

链接：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
",str);
 82             else
 83                 printf("XXX
");
 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
");
102             continue;
103         }
104         flag=true;
105         Work(1,N);
106         if(!flag)
107             printf("XXX
");
108         else
109         {
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             else
116                 for(i=Lit-1;i>=1;i--)
117                     printf("%c",Ans[i]);
118             printf("
");
119         }
120     }
121     return 0;
122 }

View Code