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

· · 题解

上一下原链接 YoungNeal

我们先来科普一下康托展开

定义：

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;
}