CF367D题解

0 前言

这道题是一道比较经典的状压DP.

需要先将题目里的条件稍作转化,然后再来处理,进行DP.

1 题意

lg上这道题已经翻译成了形式化题面,这里不再赘述.

2 思路

观察数据范围,发现 $m\leq 20$,从而联想到状压DP.

考虑可以用 $f_i=1/0$ 表示 $i$ 这种选择方案是否合法.但是我们发现,这样的话不好直接转移,所以需要进一步处理后再转移.

由于所有集合的并为 $[1,n]$,那么我们可以将选集合转化为在 $[1,n]$中选数.

我们将题目中对于 $b$ 的三个限制条件列出来:

• $b_1\leq d$

• $b_{i+1}-b_i\leq d$

• $n-d+1\leq b_{|b|}$

我们对其稍作转化:

• 前 $d$ 个数内至少选一个数

• 中间任意长为 $d$ 的区间内至少选一个数

• 后 $d$ 个数内至少选一个数

所以,这样就转化为了一个条件:数列中任意长为 $d$ 的区间内,$b$ 至少包含一个数

这样的话,我们就可以提前处理一下.

我们来遍历 $[1,n]$,并且开桶记录仪下每个集合的数在目前的长度为 $d$ 的区间内出现了多少次.然后记录仪下当前状态(即当前区间包含了哪几个集合),然后显而易见的,如果这些集合都不包含(即当前选择集合状态的补集),那么一定非法.

写得一点都不好的示例代码如下:

for(int i=1;i<=n;++i){
    if(i>d){
        bckt[whe[i-d]]--;//移除出区间的数字
        if(!bckt[whe[i-d]]){now&=(all-(1<<whe[i-d]-1));}//如果这个数字所在集合没有一个数在这个区间,那么直接删掉这个集合
    }
    bckt[whe[i]]++;//记录当前数字所在集合
    now|=(1<<(whe[i]-1));//记录这个集合
    if(i>=d){f[all^now]=0;}//如果这些集合都不包含,那么一定非法
}

然后,进行转移.

我们发现,如果一个状态是非法的,那么它的所有非空真子集一定也是非法的.反之合法.

然后,根据题目要求,要求我们输出选择集合最少的方案,那么也就是对于每个状态 $i$,$\operatorname{popcount}(i)$ 最小的方案.

那么思路十分明了,代码如下:

int ans=0x3f3f3f3f;
for(int i=all;i>0;--i){
    if(f[i]==1)ans=min(ans,popct(i));
    elif(!f[i]){
        for(int j=i;j;j=i&(j-1)){f[j]=2;}//枚举i的子集,并且打上标记防止重复计算
    }
}
printf("%lld",ans);

3 整体实现

写的很不好看的示例代码如下:

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define lowbit(x) (x&-x)
#define elif else if
int read(){
    int f=1,s=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){s=(s<<1)+(s<<3)+(c-'0');c=getchar();}
    return f*s;
}
// const int N=1e7+1145;
int n,m,d;
int f[2097152],whe[114514],bckt[114514];
int popct(int x){
    int res=0;
    while(x){
        x^=lowbit(x);
        res++;
    }
    return res;
}
signed main(){
    fill(f,f+2097151,1);
    n=read(),m=read(),d=read();
    for(int i=1;i<=m;++i){
        int ni=read();
        for(int j=1;j<=ni;++j){
            int numj=read();whe[numj]=i;
        }
    }
    int all=(1<<m)-1,now=0;
    for(int i=1;i<=n;++i){
        if(i>d){
            bckt[whe[i-d]]--;
            if(!bckt[whe[i-d]]){now&=(all-(1<<whe[i-d]-1));}
        }
        bckt[whe[i]]++;//记录当前这个数字所在集合编号
        now|=(1<<(whe[i]-1));
        if(i>=d){f[all^now]=0;}
    }
    int ans=0x3f3f3f3f;
    for(int i=all;i>0;--i){
        if(f[i]==1)ans=min(ans,popct(i));
        elif(!f[i]){
            for(int j=i;j;j=i&(j-1)){f[j]=2;}
        }
    }
    printf("%lld",ans);
}

4 后记

感谢zqq。