【题解】[牛客网NOIP赛前集训营-提高组(第二场)]C.集合划分 状压DP
看了题解后还是没写对,只能去看Komachi大佬咋写的了。
#include<cstdio>
#include<cstring>
const int N=18,MX=(1<<18)+5;
int n,m,k,ban[N][MX],pre[MX],f[MX];
int main()
{
//freopen("in.txt","r",stdin);
scanf("%d%d%d",&n,&m,&k);
for(int i=1,x;i<=m;i++)//一定给小s的集合
{
scanf("%d",&x);
for(int i=0;i<n;i++)
if(x&(1<<i))
ban[i][x]=1;//标记集合x中的i位
}
for(int i=0;i<n;i++)
for(int j=0;j<(1<<n);j++)
if(ban[i][j])
for(int k=0;k<n;k++)
if(!(j&(1<<k)))
ban[i][j|(1<<k)]=1;
f[0]=1;int S=(1<<n)-1;
for(int i=0;i<(1<<n);i++)
if(f[i])
{
int t=0;
for(int j=0;j<n;j++)
t+=(i>>j)&1;
t=1<<n-t-1;
for(int j=0;j<n;j++)
if(!(i&(1<<j))&&((k&t)||(!ban[j][S^i])))
pre[i|(1<<j)]=i,f[i|(1<<j)]=1;
}
if(!f[S])puts("-1");
else
{
memset(f,0,sizeof(f));
for(int t=0,p=S;p;p=pre[p],t++)
if(k&(1<<t))
{
int d=p^pre[p],i=p^S;
for(int j=i;j;j=(j-1)&i)
f[d|j]=1;
f[d]=1;
}
for(int i=1;i<(1<<n);i++)
putchar(f[i]^48);
puts("");
}
return 0;
}
总结
状压DP+输出方案