菜鸡一个。

题解 CF107C 【Arrangement】

2020-11-14 09:02:14


更好的阅读体验:点这里

网上的题解大都不是很明白(注释都没有),我这里参考了一下这篇题解:点这里,同时加入了很多注释方便大家理解。

首先,$n$很小,容易想到状压。

我们可以依次确定排列中每一位应该坐哪个人。那么,我们只需要知道某一位选辈分为$j$的人的方案数。

设$f_{i,j}$表示当前状态的方案数,其中$i$是一个二进制数,值为$1$的位表示对应的座位已经安排给了辈分为$1 \sim cnt_i$的人($1$为最老,$cnt_i$表示$i$在二进制下$1$的位数),$j$表示第$x$个座位确定由辈分为$j$的人来坐。

最终结果是$f_{{2^n-1},y}$,$y \in [1,n]$。

如何转移呢?我们可以枚举辈分$cnt_i+1$的人坐哪个位置,进行转移即可。(具体见代码中的注释)

Code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int BIT=(1<<17),M=110,N=25;
int n,m,cnt[BIT],a[M];
ll f[BIT][N],b[N],p[N],year;
//f[i][j]
//i中1的位表示对应的座位已经安排给了辈分为1~cnt[i]的人(1为最老)
//j表示第x位确定安排给辈分为j的人坐
//b[i]表示辈分为i的人在哪个位置

//辈分为1~n,1为最老,n为最年轻
void solve(int x){
    memset(f,0,sizeof(f));
    f[0][0]=1;int maxb=(1<<n);
    //按辈分从老到年轻依次安排座位
    for(int i=0;i<maxb;i++){
        for(int j=0;j<=n;j++){
            int y=cnt[i]+1;
            if(b[y]){//若辈分为cnt[i]+1的人已经安排了座位
                //安排过的座位不满足这一个座位的要求,continue
                if((a[b[y]]&i)!=a[b[y]]) continue;
                //当前座位已经被占用了,也continue
                if((1<<(b[y]-1)&i)==(1<<b[y]-1)) continue;
                //如果辈分为cnt[i]+1的人刚好坐在x位置上,那么j=cnt[i]+1
                if(b[y]==x) f[i|(1<<b[y]-1)][y]+=f[i][j];
                //否则继续保持原来的j
                else f[i|(1<<b[y]-1)][j]+=f[i][j];
            }
            else{
                for(int k=1;k<=n;k++){//枚举辈分为cnt[y]+1的人应该放哪个位置
                    if(!(i&(1<<k-1))){
                        if((a[k]&i)!=a[k]) continue;
                        //与上面类似的转移
                        if(k==x) f[i|(1<<k-1)][y]+=f[i][j];
                        else f[i|(1<<k-1)][j]+=f[i][j];
                    }
                }
            }
        }
    }
}

int main(){
    scanf("%d%lld%d",&n,&year,&m);year-=2000;
    //cnt[i]表示i在二进制下1的个数
    for(int i=1;i<BIT;i++) cnt[i]=cnt[i^(i&(-i))]+1;
    for(int i=1;i<=m;i++){
        int x,y;scanf("%d%d",&x,&y);
        a[y]|=(1<<x-1);
        //a[i]是一个二进制数,其中1的位表示 这一位对应的
        //座位上坐的人 的辈分 必须比 i座位上坐的人 的辈分 大
    }
    for(int i=1;i<=n;i++){
        solve(i);ll sum=0;
        for(int j=1;j<=n;j++){
            if(!b[j]&&sum+f[(1<<n)-1][j]>=year){
                //刚好加上这个位置坐辈分为j的人的方案数可以大过year
                b[j]=i;p[i]=j;
                year-=sum;break;
            }
            sum+=f[(1<<n)-1][j];
        }
        if(!p[i]){//这一位无法确定,无解
            puts("The times have changed");
            return 0;
        }
    }
    for(int i=1;i<=n;i++) printf("%lld ",p[i]);
    puts("");
    return 0;
}