首页 > > 程序设计 > C/C++ >

nth Permutation LightOJ - 1060

2018-06-17 21:41:16来源：未知阅读 ()

题意：给定一个小写字母组成的字符串，对其中所有字母进行排列（排列组合的排列），将所有生成的排列按字典序排序，求排序后第n个排列。

方法：按位生成。

首先算出所有字母可以形成的排列总数，如果小于n那么为Impossible。

否则，从第一位开始，每一位都要从小到大在当前还有剩余的所有字母的范围内枚举这一位。枚举出一个就用“可重集的排列个数”的公式（总个数的阶乘/每个元素出现次数阶乘的乘积）算出这一位之后的位置用剩余字母可以形成的排列个数，然后将当前排列的编号加上这个值。如果某一次加之后当前排列的编号大于n，那么说明当前位就是当前枚举到的这个字母，把多加的这个值减掉然后开始枚举下一位。

错误次数：2

错误原因：妄想用暴力（一个一个排列生成）过

 1 #include<cstdio>
 2 #include<cstring>
 3 typedef long long LL;
 4 LL fac[]={1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800,87178291200,1307674368000,20922789888000,355687428096000,6402373705728000,121645100408832000,2432902008176640000};
 5 LL T,TT,x,len;
 6 char s[100];
 7 LL num[30],arr[30];
 8 LL get_num()
 9 {
10     LL i,a1=0,b1=1;
11     for(i=0;i<26;i++)
12         a1+=num[i],b1*=fac[num[i]];
13     return fac[a1]/b1;
14 }
15 int main()
16 {
17     LL i,j,t1,now;
18     scanf("%lld",&T);
19     for(TT=1;TT<=T;TT++)
20     {
21         scanf("%s%lld",s+1,&x);
22         len=strlen(s+1);
23         memset(num,0,sizeof(num));
24         for(i=1;i<=len;i++)
25             num[s[i]-'a']++;
26         now=0;
27         t1=get_num();
28         printf("Case %lld: ",TT);
29         if(t1<x)
30         {
31             puts("Impossible");
32             continue;
33         }
34         for(i=1;i<=len;i++)
35         {
36             for(j=0;j<26;j++)
37                 if(num[j])
38                 {
39                     num[j]--;
40                     t1=get_num();
41                     if(now+t1>=x)
42                     {
43                         arr[i]=j;
44                         break;
45                     }
46                     num[j]++;
47                     now+=t1;
48                 }
49         }
50         for(i=1;i<=len;i++)
51             putchar(arr[i]+'a');
52         puts("");
53     }
54 }