题解 P3014 【[USACO11FEB]牛线Cow Line】

上一下原链接 [YoungNeal](http://www.cnblogs.com/YoungNeal/p/8504123.html) 我们先来科普一下康托展开 ## 定义： $X=an*(n-1)!+an-1*(n-2)!+...+ai*(i-1)!+...+a2*1!+a1*0!$ $ai$为整数，并且 $0<=ai<i$ $(1<=i<=n)$ 简单点说就是，判断这个数在其各个数字全排列中从小到大排第几位。 比如 $ 1 3 2 $，在1、2、3的全排列中排第2位。 ## 康托展开有啥用呢？ 维基： $n$ 位（0~n-1）全排列后，其康托展开唯一且最大约为 $n!$ ，因此可以由更小的空间来储存这些排列。由公式可将 $X$ 逆推出对应的全排列。 它可以应用于哈希表中空间压缩， 而且在搜索某些类型题时，将VIS数组量压缩。比如：八数码，魔板等题 康托展开求法： 比如 $2 1 4 3$ 这个数，求其展开： 从头判断，至尾结束, ① 比 $2$（第一位数）小的数有多少个->$1$个 就是 $1$ ，$1*3!$ ② 比 $1$（第二位数）小的数有多少个->$0$个 $0*2!$ ③ 比 $4$（第三位数）小的数有多少个->$3$个 就是 $1,2,3$ ，但是 $1,2$ 之前已经出现，所以是 $1*1!$ 将所有乘积相加=7 比该数小的数有7个，所以该数排第8的位置。 $1234$ $1243$ $1324$ $1342$ $1423$ $1432$ $2134$ $2143$ $2314$ $2341$ $2413$ $2431$ $3124$ $3142$ $3214$ $3241$ $3412$ $3421$ $4123$ $4132$ $4213$ $4231$ $4312$ $4321$ 放一下程序的实现 ``` int contor(int x[]){ int p=0; for(int i=1;i<=n;i++){ int t=0; for(int j=i+1;j<=n;j++){ if(x[i]>x[j]) t++; } p+=t*fac[n-i]; } return p+1; } ``` ## 康托展开的逆： 康托展开是一个全排列到自然数的双射，可以作为哈希函数。 所以当然也可以求逆运算了。 逆运算的方法： 假设求 $4$ 位数中第 $19$ 个位置的数字。 ① 19减去1 → 18 ② 18 对 $3!$ 作除法 → 得3余0 ③ 0对 $2!$ 作除法 → 得0余0 ④ 0对 $1!$ 作除法 → 得0余0 据上面的可知： 我们第一位数（最左面的数），比第一位数小的数有3个，显然 第一位数为→ 4 比第二位数小的数字有0个，所以 第二位数为→1 比第三位数小的数字有0个，因为1已经用过，所以第三位数为→2 第四位数剩下 3 该数字为 $4 1 2 3$ (正解) 再上代码 ``` void reverse_contor(int x){ memset(vis,0,sizeof vis); x--; int j; for(int i=1;i<=n;i++){ int t=x/fac[n-i]; for(j=1;j<=n;j++){ if(!vis[j]){ if(!t) break; t--; } } printf("%d ",j); vis[j]=1; x%=fac[n-i]; } puts(""); } ``` ## 最后上一下本题的代码 ``` #include<cstdio> #include<cstring> #include<iostream> #define int long long using namespace std; int fac[25]={1}; int n,k,x; int val[25]; bool vis[25]; void reverse_contor(int x){ memset(vis,0,sizeof vis); x--; int j; for(int i=1;i<=n;i++){ int t=x/fac[n-i]; for(j=1;j<=n;j++){ if(!vis[j]){ if(!t) break; t--; } } printf("%d ",j); vis[j]=1; x%=fac[n-i]; } puts(""); } int contor(int x[]){ int p=0; for(int i=1;i<=n;i++){ int t=0; for(int j=i+1;j<=n;j++){ if(x[i]>x[j]) t++; } p+=t*fac[n-i]; } return p+1; } signed main(){ scanf("%lld%lld",&n,&k); for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i; while(k--){ char ch;cin>>ch; if(ch=='P') scanf("%lld",&x),reverse_contor(x); else{ for(int i=1;i<=n;i++) scanf("%lld",&val[i]); printf("%lld\n",contor(val)); } } return 0; } ```