题解 P2524 【Uim的情人节礼物·其之弐】
顾z
2018-08-05 18:29:01
~~因为某人@ZAGER挖坑让我讲一下康托展开,所以发现了这个题,顺便说一下康托展开是个什么东西~~
**题目概括**
给定n与一个数列,要求求出给定数列在n的全排列中的排名(按照字典序从小到大排列)
**康托展开**
先放**概念**:
康托展开是一个全排列到一个自然数的双射,常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序,因此是可逆的。
--来源于[度娘](https://baike.baidu.com/item/%E5%BA%B7%E6%89%98%E5%B1%95%E5%BC%80/7968428?fr=aladdin)
~~双射的概念我也不是很理解~~
所以直接给出**康托展开的作用**:
康托展开的作用是求n个数的全排列中某一个序列在所有排列中的次序(该排列次序(亦称之为排名)以字典序从小到大排序)
还是不理解?
**栗子:**
求:在n=3的全排列中,{1,3,2}排第几位。
可以写出n=3的全排列 {1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}
(在这里我们按照字典序从小到大排序)
所以容易看出{1,3,2} Rank 2
如果还是不理解请打开上面的'度娘'↑,里面有详细解释
**康托展开的公式**:
X=a[n] * [(n-1)!] +a[n-1]*[(n-2)!]+....+a[1] * [0!]。
其中X代表当前排列小的排列的个数,
a[i]代表当前排列里从i位置右侧比i位置的数小的数的个数。
**详细解释;**
在n=5的全排列中,计算{3,4,1,5,2}的康托展开值。
首位是3,则小于3的数有两个,为1和2,a[5]=2,则首位小于3的所有排列组合为a[5]*(5-1)!
第二位是4,则小于4的数有两个,为1和2,注意这里3并不能算,因为3已经在第一位,所以其实计算的是在第二位之后小于4的个数。因此a[4]=2。
第三位是1,则在其之后小于1的数有0个,所以a[3]=0。
第四位是5,则在其之后小于5的数有1个,为2,所以a[2]=1。
最后一位就不用计算啦,因为在它之后已经没有数了,所以a[1]固定为0.
根据公式:
rank=2*(4!)+2*(3!)+0*(2!)+1*(1!)+0*(0!)=61.
所以比{3,4,1,5,2}小的组合有61个,即{3,4,1,5,2}排名62。
以上内容来自[度娘](https://baike.baidu.com/item/%E5%BA%B7%E6%89%98%E5%B1%95%E5%BC%80/7968428?fr=aladdin)+个人认为.
所以就这么多了,还有一个逆康托展开,没有怎么学,网络上讲这个的还是不少的,想继续学的可以自行找寻度娘的~
---------------代码--------------
```cpp
#include<bits/stdc++.h>
#define IL inline
#define RI register int
const int fac[]={1,1,2,6,24,120,720,5040,40320,362880};//阶乘
char s[108];
int n;
IL int Contor(char s[],int n)
{
int ans=0;
for(RI i=0;i<n;i++)
{
//std::cout<<ans<<std::endl;
int smaller=0;
for(RI j= i+1 ;j<n;j++)
{
if(s[i] > s[j])smaller++;
}
ans += smaller*fac[n-i-1];
}
return ans+1;
}
int main()
{
std::cin>>n;
std::cin>>s;
std::cout<<Contor(s,n);
}
```