1025 -康托展开&逆康托展开 - Cow Line[USACO11FEB]

传送门

分析

本来以为好难好难 结果除了不知道为什么，还是很简单的嘛[笑哭] 我们就记结论，并理解代码就好了

康托展开

先上定义：

康托展开是一个全排列到一个自然数的双射，常用于构建hash表时的空间压缩。设有n个数（1，2，3，4,…,n），可以有组成不同(n!种)的排列组合，康托展开表示的就是 当前排列组合在n个不同元素的全排列中的名次。

再讲作用： 对于一个具体的1~n的排列P，康托展开可以求出这个排列在 n！种有序排列中位于第几个，怎么求呢？？机智的Contor告诉了我们答案： $$X=An\ast (n-1)!+An-1\ast (n-2)!+\cdots +Ai\ast (i-1)!+\cdots +A2\ast 1!+A1\ast 0!$$ （Ai表示排列 P 中第 i 个数的后面有多少个数小于当前的值） 这个算出来的就是在排列 P 前有X个排列小于它，那它的排名就是$X+1$

举个例子： 1～5的排列，1 3 2 5 4 排在第几个呢？ 首先看看：第一个数字1之后没有比1小的数字，所以 An=0；在3之后有一个比它小的2，所以 $A_{n-1}=1$。依此类推： 0∗(5−1)!+1∗(4−1)!+0∗(3−1)!+1∗(2−1)!+0∗(1−1)!=7 比这个排列还要小的排列有7个，所以它排在第8个。 下面我们枚举验证：

1 2 3 4 5 1 2 3 5 4 1 2 4 3 5 1 2 4 5 3 1 2 5 3 4 1 2 5 4 3 1 3 2 4 5 1 3 2 5 4

代码实现

ll contor(){ ll res=0; for(int i=1;i<=n;++i){ int t=0; for(int j=i+1;j<=n;++j) if(a[j]<a[i]) t++; res+=t*1ll*fac[n-i]; } return res+1; }

很简单吧~~

逆康托展开

所谓逆康托展开，就是给出排列的名次X，求这个具体的排列P 再来公式： 先将X - 1，这能明白 然后$X/(n-i)!$就得出了有多少个数小于排列P第 i 个位置上的数

举个例子 在（1，2，3，4，5）给出61可以算出排列组合为 34152。由上述的计算过程可以容易的逆推回来，具体过程如下： 用 61 / 4! = 2余13，说明a[5]=2,说明比首位小的数有2个，所以首位为3。 用 13 / 3! = 2余1，说明a[4]=2，说明在第二位之后小于第二位的数有2个，所以第二位为4。 用 1 / 2! = 0余1，说明a[3]=0，说明在第三位之后没有小于第三位的数，所以第三位为1。 用 1 / 1! = 1余0，说明a[2]=1，说明在第二位之后小于第四位的数有1个，所以第四位为5。 最后一位自然就是剩下的数2啦。 通过以上分析，所求排列组合为 34152。

代码

void reverse_contor(ll x){ x--;int i,j; memset(vis,0,sizeof(vis)); for(i=1;i<=n;++i){ ll t=x/fac[n-i]; for(j=1;j<=n;++j) if(!vis[j]){ if(!t) break; t--; } b[i]=j; vis[j]=1; x%=fac[n-i]; } }

那么知识铺垫完啦，这道题就是板子题咯~~~ 完整代码献上

#include<bits/stdc++.h> #define ll long long using namespace std; int n,k,a[30],b[30]; ll fac[30]; bool vis[30]; void reverse_contor(ll x){ x--;int i,j; memset(vis,0,sizeof(vis)); for(i=1;i<=n;++i){ ll t=x/fac[n-i]; for(j=1;j<=n;++j) if(!vis[j]){ if(!t) break; t--; } b[i]=j; vis[j]=1; x%=fac[n-i]; } } ll contor(){ ll res=0; for(int i=1;i<=n;++i){ int t=0; for(int j=i+1;j<=n;++j) if(a[j]<a[i]) t++; res+=t*1ll*fac[n-i]; } return res; } int main(){ scanf("%d%d",&n,&k); int i,j; fac[0]=1; for(i=1;i<=20;++i) fac[i]=fac[i-1]*1ll*i; ll q;char ch; for(i=1;i<=k;++i){ cin>>ch; if(ch=='P'){ scanf("%lld",&q);//查询1~n的排列中第 q 大的是多少 reverse_contor(q); for(j=1;j<=n;++j) printf("%d ",b[j]); printf("\n"); } else{ for(j=1;j<=n;++j) scanf("%d",&a[j]); printf("%lld\n",contor()+1); } } return 0; }