nyoj 139 我排第幾個(康拓展開)

2019-11-08 02:28:47

字體：大中小

來源：轉載

供稿：網友

我排第幾個

時間限制：1000 ms | 內存限制：65535 KB難度：3描述

現在有"abcdefghijkl”12個字符，將其所有的排列中按字典序排列，給出任意一種排列，說出這個排列在所有的排列中是第幾小的？

輸入第一行有一個整數n（0<n<=10000）;隨后有n行，每行是一個排列；輸出輸出一個整數m，占一行，m表示排列是第幾位；樣例輸入

3abcdefghijklhgebkflacdjigfkedhjblcia樣例輸出1302715242260726926
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是第三個大數。