自动搬运

查看原文

来自洛谷，原作者为

	Presentation_Emitter Tu fui ego eris.

搬运于2025-08-24 22:29:01，当前版本为作者最后更新于2022-11-13 14:38:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

有用的信息共有两种：公布的“某个集合里存在某种数字的卡片”的信息和每一回合喊出“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;
}