康拓展开

asuldb · 2018-09-23 18:35:34 · 个人记录

并不是非常难的东西，但是听起来很高端的样子

用于实现序列和自然数的双射

就比如说这道题，这就是康拓展开的板子题

[USACO11FEB]牛线Cow Line

这个题就是两个操作

给出一个长度为n的排列，求这个排列在1到n全排列里的排名
给出一个排名，求出在1到n全排列中对应的排列

这就是康拓展开和康拓逆展开的板子了

首先先来看一下康拓展开，对应的就是操作1

比如说1到5的全排列里，3\ 4\ 1\ 5\ 2的排名

有数位dp基础的应该能很好理解

其实就是相当于数位dp里的卡上界

那我们从第一位开始卡

第一位是3，那么这一位上可以填的数是1和2剩下的可以随便填，于是就是2*(5-1)!
第二位是4，那么可以填的数有1,2,3，但是注意3在之前已经被使用了，于是就是2*(5-2)!

于是可以理解为像数位dp那样理解为保证前i-1位相同,卡第i位，之后自然是不能填之前的数了

之后剩下的就是0 * 2! + 1 * 1! + 0 * 0!

于是答案就是61

说明比这个排列小的共有61个，于是这个排列的排名就是62

代码就很简单了

inline ull Kt()
{
    ull ans=0;
    int vis[maxn]={0};
    for(re int i=1;i<=n;i++)
        a[i]=read();
    for(re int i=1;i<=n;i++)
    {
        ull cnt=0;
        for(re int j=1;j<a[i];j++)
        if(!vis[j]) cnt++;
        ans+=cnt*fac[n-i];
        vis[a[i]]=1;
    }
    return ans+1;
}

之后第二个操作，逆康拓展开，求对应排名的排列

这很简单啊，我们倒着把这个操作做一遍就好了

那就以62为例吧

首先先减一，得到有多少个排列比它小

第一位我们开始试探，找到一个最大的数使得这个数乘(5-1)!小于61，那么就会找到61/24=2，于是这一位上填的数有2比它小的数，那么这一位上就是2,同时61-2*4!=13
第二位继续试探，会找到13/3!=2，那么就会有2个比这一位上的数要小且没有被选择的数，于是就会找到3,同时13-2*3!=1

以此类推就好了，最终就会得到原来的排列

代码

inline void nKt()
{
    ull ans=read();
    ans--;
    int vis[maxn]={0};
    for(re int i=1;i<=n;i++)
    {
        ull cnt=0;
        for(re int j=0;j<n;j++)
        if(j*fac[n-i]<=ans) cnt=j;
        else break;
        ull tot=0;
        for(re int i=1;i<=n;i++)
        {
            if(!vis[i]&&tot==cnt) 
            {
                tot=i;
                break;
            }
            if(!vis[i]) tot++;
        }
        printf("%lld ",tot);
        ans-=cnt*fac[n-i];
        vis[tot]=1;
    }
    putchar(10);
}

这道题的完整代码

#include<iostream>
#include<cstring>
#include<cstdio>
#define re register
#define maxn 21
#define ull unsigned long long
int a[maxn];
int n,Q;
ull fac[maxn];
char opt;
inline ull read()
{
    char c=getchar();
    ull x=0;
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9')
      x=(x<<3)+(x<<1)+c-48,c=getchar();
    return x;
}
inline ull Kt()
{
    ull ans=0;
    int vis[maxn]={0};
    for(re int i=1;i<=n;i++)
        a[i]=read();
    for(re int i=1;i<=n;i++)
    {
        ull cnt=0;
        for(re int j=1;j<a[i];j++)
        if(!vis[j]) cnt++;
        ans+=cnt*fac[n-i];
        vis[a[i]]=1;
    }
    return ans+1;
}
inline void nKt()
{
    ull ans=read();
    ans--;
    int vis[maxn]={0};
    for(re int i=1;i<=n;i++)
    {
        ull cnt=0;
        for(re int j=0;j<n;j++)
        if(j*fac[n-i]<=ans) cnt=j;
        else break;
        ull tot=0;
        for(re int i=1;i<=n;i++)
        {
            if(!vis[i]&&tot==cnt) 
            {
                tot=i;
                break;
            }
            if(!vis[i]) tot++;
        }
        printf("%lld ",tot);
        ans-=cnt*fac[n-i];
        vis[tot]=1;
    }
    putchar(10);
}
int main()
{
    n=read();
    Q=read();
    fac[0]=1;
    for(re int i=1;i<=n;i++) fac[i]=fac[i-1]*i;
    while(Q--)
    {
        std::cin>>opt;
        if(opt=='Q') printf("%lld\n",Kt());
        else nKt();
    }
    return 0;
}

同时康拓展开用来帮助我们省空间，将原来需要n^n才能开的下的空间优化成n!

就比如说这道题

魔板 Magic Squares

就是一个大搜索，但是需要用康拓展开来判重

丑陋的代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<bitset>
#define re register
#define maxn 503250
struct node
{
    int a[9];
    int step,y;
}st,mid;
std::bitset<maxn> f;
int t[9],T;
int fac[9];
char opt[maxn];
int pre[maxn];
int tot=1;
inline int Kt_to(int a[])
{
    int ans=0;
    int vis[9]={0};
    for(re int i=1;i<=8;i++)
        {
            int cnt=0;
            for(re int j=1;j<a[i];j++)
                if(!vis[j]) cnt++;
            vis[a[i]]=1;
            ans+=fac[8-i]*cnt;
        }
    return ans;
}
void dfs(int x)
{
    if(pre[x]!=1) dfs(pre[x]);
    putchar(opt[x]); 
}
int main()
{
    for(re int i=1;i<=8;i++)
        scanf("%d",&t[i]);
    fac[0]=1;
    for(re int i=1;i<=8;i++)
        fac[i]=fac[i-1]*i;
    T=Kt_to(t);
    for(re int i=1;i<=8;i++)
        st.a[i]=i;
    st.step=0;
    st.y=1;
    std::queue<node> q;
    pre[tot]=0;
    q.push(st);
    if(!T)
    {
        puts("0");
        return 0;
    }
    while(!q.empty())
    {
        mid=q.front();
        q.pop();
        for(re int i=0;i<3;i++)
        {
            if(!i)
            {
                int b[9];
                for(re int j=1;j<=8;j++)
                    b[j]=mid.a[j];
                int now=8;
                for(re int j=1;j<=4;j++)
                    std::swap(b[j],b[now]),now--;
                int k=Kt_to(b);
                if(f[k]) continue;
                else
                {
                    if(k==T) 
                    {
                        printf("%d\n",mid.step+1);
                        dfs(mid.y),putchar(65+i);
                        return 0;
                    }
                    f[k]=1;
                    node c;
                    ++tot;
                    for(re int i=1;i<=8;i++) c.a[i]=b[i];
                    c.step=mid.step+1;
                    c.y=tot;
                    opt[tot]=65+i;
                    pre[tot]=mid.y;
                    q.push(c);
                }
            }
            if(i==1)
            {
                int b[9];
                b[2]=mid.a[1],b[3]=mid.a[2],b[4]=mid.a[3],b[1]=mid.a[4];
                b[8]=mid.a[5],b[7]=mid.a[8],b[6]=mid.a[7],b[5]=mid.a[6];
                int k=Kt_to(b);
                if(f[k]) continue;
                else
                {
                    if(k==T) 
                    {
                        printf("%d\n",mid.step+1);
                        dfs(mid.y),putchar(65+i);
                        return 0;
                    }
                    node c;
                    ++tot;
                    for(re int i=1;i<=8;i++) c.a[i]=b[i];
                    c.step=mid.step+1;
                    c.y=tot;
                    opt[tot]=65+i;
                    pre[tot]=mid.y;
                    q.push(c);
                }
            }
            if(i==2)
            {
                int b[9];
                for(re int j=1;j<=8;j++) b[j]=mid.a[j];
                b[3]=mid.a[2],b[6]=mid.a[3],b[7]=mid.a[6],b[2]=mid.a[7];
                int k=Kt_to(b);
                if(f[k]) continue;
                else
                {
                    if(k==T) 
                    {
                        printf("%d\n",mid.step+1);
                        dfs(mid.y),putchar(65+i);
                        return 0;
                    }
                    node c;
                    ++tot;
                    for(re int i=1;i<=8;i++) c.a[i]=b[i];
                    c.step=mid.step+1;
                    c.y=tot;
                    opt[tot]=65+i;
                    pre[tot]=mid.y;
                    q.push(c);
                }
            }
        }
    }
    return 0;
}