nyoj 143 第几是谁(康拓展开的逆运算)

╰半夏微凉° 2024-02-17 19:11 20阅读 0赞

### 第几是谁？ ###

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

难度： 3

描述

现在有"abcdefghijkl”12个字符，将其按字典序排列，如果给出任意一种排列，我们能说出这个排列在所有的排列中是第几小的。但是现在我们给出它是第几小，需要你求出它所代表的序列.

输入

第一行有一个整数n（0<n<=10000）;  
随后有n行，每行是一个整数m，它代表着序列的第几小；

输出

输出一个序列，占一行，代表着第m小的序列。

样例输入

3
    1
    302715242
    260726926

样例输出

abcdefghijkl
    hgebkflacdji
    gfkedhjblcia

AC代码如下：

#include<cstdio>
    #include<cstring>
    using namespace std;
    const int maxn=12+2;
    char a[]="abcdefghijkl";
    char b[maxn];
    int stratum(int n){
    	int sum=1;
    	for(int i=1;i<=n;i++){
    		sum*=i;
    	}
    	return sum;
    }
    
    void cantor(int t){
    	int c[maxn];
    	memset(c,0,sizeof(c));
    	for(int i=0;i<12;i++){
    		int temp=t/stratum(11-i);     //比当前位小的个数 
    		for(int j=0;j<=temp;j++) 
    			if(c[j])temp++;
    		c[temp]=1;
    		b[i]=a[temp];
    		t%=stratum(11-i);
    	}
    }
    int main(){
    	int n;
    	scanf("%d",&n);
    	while(n--){
    		int tmp;
    		scanf("%d",&tmp);
    		cantor(tmp-1);
    		for(int i=0;i<12;i++)
    		printf("%c",b[i]);
    		printf("\n");
    	}
    	return 0;
    }

如何判断给定一个位置，输出该位置上的数列，康拓展开的逆运算，例如：

\{1,2,3,4,5\}的全排列，并且已经从小到大排序完毕，请找出第96个数：

首先用96-1得到95

用95去除4! 得到3余23，即有3个数比该数位上的数字小，则该数位的数字为4；

用23去除3! 得到3余5，即有3个数比该数位上的数字小，理应为4，但4已在前面的高位中出现过，所以该数位的数字为5；

用5去除2!得到2余1，即有2个数比该数位上的数字小，则该数位的数字为3；

用1去除1!得到1余0，即有1个数比该数位上的数字小，则该数位的数字为2；

最后一个数只能是1；

所以这个数是45321