nyoj 139 我排第几个(康拓展开)

ゝ一世哀愁。 2024-02-17 19:11 3阅读 0赞

### 我排第几个 ###

时间限制： 1000 ms | 内存限制： 65535 KB

难度： 3

描述

现在有"abcdefghijkl”12个字符，将其所有的排列中按字典序排列，给出任意一种排列，说出这个排列在所有的排列中是第几小的？

输入

第一行有一个整数n（0<n<=10000）;  
随后有n行，每行是一个排列；

输出

输出一个整数m，占一行，m表示排列是第几位；

样例输入

3
    abcdefghijkl
    hgebkflacdji
    gfkedhjblcia

样例输出

1
    302715242
     260726926

AC代码如下：

#include<cstdio>
    using namespace std;
    const int maxn=12+2;
    char s[maxn];
    int stratum(int n){    //求阶层
    	int sum=1;
    	for(int i=1;i<=n;i++){
    		sum*=i;
    	}
    	return sum;
    }
    int cantor(){        //康拓展开
    	int sum=0;
    for(int i=0;i<12;i++){
    	int temp=0;
    	for(int j=i+1;j<12;j++)
    		if(s[i]>s[j])temp++; 
    	sum+=temp*stratum(11-i);
       }
       return sum;
    } 
    int main(){
    	int n;
    	scanf("%d",&n);
    	while(n--){
    		scanf("%s",s);
    		int cnt=cantor();
    		printf("%d\n",cnt+1);
    	}
    	return 0;
    }

（1）康拓展开

所谓康拓展开是指把一个整数X展开成如下形式：

X=a\[n\]\*(n-1)!+a\[n-1\]\*(n-2)!+...+a\[i\]\*(i-1)!+...+a\[2\]\*1!+a\[1\]\*0!。（其中，a为整数，并且0<=a\[i\]<i(1<=i<=n)）

（2）应用实例

\{1,2,3,4,...,n\}表示1,2,3,...,n的排列如 \{1,2,3\} 按从小到大排列一共6个：123 132 213 231 312 321。他们间的对应关系可由康托展开来找到。

1324是\{1,2,3,4\}排列数中第几个大的数：

第一位是1小于1的数没有，是0个 0\*3! ；

第二位是3小于3的数有1和2，但1已经在第一位了，即1未出现在前面的低位当中，所以只有一个数2 1\*2! ；

第三位是2小于2的数是1，但1在第一位，即1未出现在前面的低位当中，所以有0个数 0\*1! ；

所以比1324小的排列有0\*3!+1\*2!+0\*1!=2个，1324是第三个大数。