我排第几个
时间限制: 1000 ms | 内存限制: 65535 KB 难度: 3
- 描述
- 现在有"abcdefghijkl”12个字符,将其所有的排列中按字典序排列,给出任意一种排列,说出这个排列在所有的排列中是第几小的?
- 输入
-
第一行有一个整数n(0<n<=10000);
随后有n行,每行是一个排列;
输出 - 输出一个整数m,占一行,m表示排列是第几位; 样例输入
-
3 abcdefghijkl hgebkflacdji gfkedhjblcia
样例输出 -
1 302715242 260726926
-
康托展开:
-
康托展开
康托展开 康托展开就是一种特殊的哈希函数,它的使用范围是对于n个数的排列进行状态的压缩和存储,例如要对9的全排列进行判重.没有必要 开一个10^9的数组,同时内存也不允许开到那么大的数组.对此,有人提出了优化,即对于一个n的排列数,没有必要开到10^n,因为在一个排列中每个数只出现一次,所以只要前n-1位确定了,前N位就确定了. 但是以上的想法仍不是可行的,因为N可以很大,例如15,所以便引入了康托展开:只需要确定这个排列在总的排列情况中是第几小的就可以了. 例如:我想知道321是{1,2,3}的排列中第几个大的数可以这样考虑第一位是3,当第一位的数小于3时,那排列数小于321 如 123 213 小于3的数有1,2 所以有2*2!个 再看小于第二位2的小于2的数只有一个就是1 所以有1*1!=1 所以小于321的{1,2,3}排列数有2*2!+1*1!=5个所以321是第6个大的数。 2*2!+1*1!是康托展开. 下面给出康托展开的代码: -
int hash(s[12]) { int ktzk=0; for ( int i=1;i<=12;i++) { int tot=0; for ( int j=i+1;j<=12;j++) if (s[j]>s[i]) tot++; ktzk+=(tot*mi[12-i]); //mi[I]数组中记录了i的阶乘. } return ktzk; }
-
-
#include<stdio.h> #include<string.h> #include<iostream> using namespace std; int a[12]= {39916800,3628800,362880,40320,5040,720,120,24,6,2,1,1};//记录0,1,2,3,4,5,6,7,8,9,10,11的阶乘 char b[1000]; int c[1000]; int main() { int t; scanf("%d",&t); while(t--) { scanf("%s",b); int l; l=strlen(b); for(int i=0; i<l; i++) { c[i]=b[i]-'a'; } int p; int sum=0; for(int i=0; i<l; i++) { p=0; for(int j=11; j>i; j--) { if(c[i]>c[j]) { p++; } } sum+=p*a[i]; } printf("%d\n",sum+1); } }
-