luogu P7352 炉心融解

记 \(f_S\) 为所有人以当前信息推断出 \(S\) 这种情况是否合法，\(g_S\) 表示假如真实情况是 \(S\)，应该有哪些人喊出来了。

每一轮中，通过告诉你的 \(k\) 条消息可以推断出哪些集合不合法，将其 \(f_S\) 赋为 \(0\)，然后根据新的 \(f_S\)，有些人可能可以据此喊了，所以根据新的 \(f_S\) 更新 \(g_S\)。那本质上真实集合确定，如果某种可能的情况喊的人与真实喊的人不一致，即 \(g_S \neq g_X\)，\(X\) 为真实情况，则这种情况不可能，将 \(f_S\) 设成 \(0\)。

#include <bits/stdc++.h>
using namespace std;
const int maxn=20;
int n,m,S,U,f[(1<<16)],g[(1<<16)];
int t[maxn];
bool check(int X,int i,int pre,int nxt,int type)
{
    int tnow=(U^(1<<pre)^(1<<nxt))&X;
    int t00=f[tnow],t01=f[tnow|(1<<nxt)],t10=f[tnow|(1<<pre)],t11=f[tnow|(1<<nxt)|(1<<pre)];
    if(type==1)
    {
        if((!t00&&!t11)||(!t01&&!t10))return 1;
    }
    if(type==0)
    {
        if((!t00)||(!t01&&!t10&&!t11))return 1;
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++)t[i]=-1;
    for(int i=0,x;i<n;i++)
    {cin>>x;S|=x<<i;}
    U=(1<<n)-1;
    vector<int> now;
    for(int i=0;i<(1<<n);i++)f[i]=1,now.push_back(i);
    for(int i=1;i<=m;i++)
    {
        vector<int> nxt;
        int k,p,x,T,v;cin>>k;
        for(int j=1;j<=k;j++)
        {
            cin>>p;T=0;
            for(int t=1;t<=p;t++){cin>>x;T|=(1<<x);}
            cin>>v;nxt.clear();
            for(int s:now)
                if(((v==0?(~s):(s))&T))nxt.push_back(s);
                else {f[s]=0;}
            swap(now,nxt);
        }
        for(int s:now)
            for(int j=0;j<n;j++)
            {
                if(g[s]&(1<<j))continue;
                int pre=(j?j-1:n-1),nxt=(j==n-1?0:j+1);
                if(check(s,j,pre,nxt,(s>>j)&1))g[s]|=(1<<j);
            }
        for(int j=0;j<n;j++)if(t[j]==-1&&((g[S]>>j)&1))t[j]=i;
        nxt.clear();
        for(int s:now)
            if(g[s]==g[S])nxt.push_back(s);
            else f[s]=0;
        swap(now,nxt);
    }
    for(int i=0;i<n;i++)cout<<t[i]<<' ';
    return 0;
}