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

2018-03-04 11:16:44


上一下原链接 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;
}