题解 P7352 【炉心融解】

· · 题解

你谷绿题恐怖如斯。建议评紫/黑。

有用的信息共有两种：公布的“某个集合里存在某种数字的卡片”的信息和每一回合喊出“Meltdown！”的人的集合。

由于 n 很小，考虑状压，令 f_{i,S} 表示第 i 次公布信息后 S 是否满足所有已知的信息，g_{i,S} 表示若当前所有 \texttt{1} 的集合为 S，则第 i 次喊话后第一次喊的人组成的集合。

对于每个集合 S，出现以下两种情况时该集合即为非法：与公布的信息矛盾，或者 g_{i,S} \neq g_{i,V}，其中 V 表示所有 \texttt{1} 的集合。

对于 g_{i,S}，每次暴力枚举所有人，然后对于每个人判断在所有合法的集合中是否存在多个能推断出来的值即可。

时间复杂度 \Theta(2^n(nm+\sum k))。

Code:

int n,q,m,S,ans[17],f[1<<16],g[1<<16],st[(1<<16)|1],vis[1<<16][2],t,tt,lt;
int main()
{
    n=rd();q=rd();for(int i=0;i<n;++i)S|=rd()<<i,ans[i]=-1;
    cst int lim=1<<n;for(int i=0;i<lim;++i)st[++t]=i,f[i]=1;
    for(int ti=1;ti<=q;++ti)
    {
        //cerr<<t<<endl;for(int i=1;i<=tt;++i)cerr<<st[i]<<" \n"[i==tt];
        m=rd();while(m --> 0)
        {
            int c=rd(),s=0;while(c --> 0)s|=1<<rd();
            int b=rd();if(vis[s][b])continue;
            vis[s][b]=1;tt=t;t=0;
            for(int i=1;i<=tt;++i)if((st[i]&s)==(b?0:s))f[st[i]]=0;else st[++t]=st[i];
        }
        if(t==lt)continue;
        //cerr<<t<<endl;for(int i=1;i<=tt;++i)cerr<<st[i]<<" \n"[i==tt];
        for(int j=1,s;j<=t;++j)
        {
            g[s=st[j]]=0;assert(f[s]);
            for(int i=0,posl=n-1,posr=1;i<n;++i,++posl,++posr)
            {
                if(~ans[i])continue;
                if(posl>=n)posl-=n;
                if(posr>=n)posr-=n;
                int s1=(s|(1<<posl))|(1<<posr),s2=(s|(1<<posl))&~(1<<posr),s3=(s&~(1<<posl))|(1<<posr),s4=(s&~(1<<posl))&~(1<<posr);
                //cerr<<ti<<' '<<s<<' '<<i<<' '<<((s>>i)&1)<<' '<<g[s]<<' '<<s1<<' '<<s2<<' '<<s3<<' '<<s4<<endl;
                if((s>>i)&1){if((((s>>posl)&1)^((s>>posr)&1))?!f[s1]&&!f[s4]:!f[s2]&&!f[s3])g[s]|=1<<i;}
                else{if((((s>>posl)&1)|((s>>posr)&1))?!f[s4]:!f[s1]&&!f[s2]&&!f[s3])g[s]|=1<<i;}
                //cerr<<ti<<' '<<s<<' '<<i<<' '<<((s>>i)&1)<<' '<<g[s]<<' '<<s1<<' '<<s2<<' '<<s3<<' '<<s4<<endl;
            }
            //cerr<<ti<<' '<<t<<' '<<j<<' '<<s<<' '<<g[s]<<endl;
        }
        lt=t;t=0;for(int j=1,s;j<=lt;++j){if(g[s=st[j]]^g[S])f[s]=0;else st[++t]=s;}
        for(int i=0;i<n;++i)if(((g[S]>>i)&1)&&!~ans[i])ans[i]=ti;
        //cerr<<t<<endl;for(int i=1;i<=tt;++i)cerr<<st[i]<<" \n"[i==tt];
    }
    for(int i=0;i<n;++i)prt(ans[i]," \n"[i==n-1]);
    ret 0;
}