nth Permutation LightOJ - 1060

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

新老客户大回馈,云服务器低至5折

nth Permutation LightOJ - 1060

题意:给定一个小写字母组成的字符串,对其中所有字母进行排列(排列组合的排列),将所有生成的排列按字典序排序,求排序后第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 }

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:[NOIP模拟题] 位运算入门详解+富有诗意的模拟题

下一篇:51nod1004 n^n的末位数字