很好的题，想了半天，官方题解的解法更好
这种异或问题的包含性在北邮的校赛里就出现过，需要认真学习一下
/* y和所有合法的x合并，如果没有剪枝，那么复杂度爆炸总共要判(2^n*2^n) 可以考虑如下优化：如果x & y==0 ，那么所有x的子集也是合法的 所以现在可以将y和x的集合都加边，即在并查集里将y和x的集合合并起来 另一个y' & x==0 那么y'只要和x合并即可，只要判断一次 那么现在问题转化为如何预处理上面的x的集合，还是用大的集合包含小的集合 即如果f[x-(1<<i)]=1,那么f[x]=1因为如果x对于y合法，那么x-(1<<i)必定也合法 */ #include<bits/stdc++.h> using namespace std; #define maxn 5000000 int n,m,a[maxn],f[maxn],fa[maxn]; int find(int x){ return fa[x]==x?x:fa[x]=find(fa[x]); } void bing(int x,int y){ x=find(x);y=find(y); if(x!=y)fa[x]=y; } void dfs(int x,int y){ if(f[x]==0)return; if(find(x)==find(y))return; bing(x,y); for(int i=0;i<n;i++) if(x & (1<<i)) dfs(x^(1<<i),y); } int main(){ cin>>n>>m; int mask=(1<<n); for(int i=1;i<=m;i++)scanf("%d",&a[i]),f[a[i]]=1; for(int i=0;i<mask;i++)fa[i]=i; for(int i=0;i<mask;i++)//预处理用来剪枝的集合 for(int j=0;j<n;j++) if(i & (1<<j)) f[i]|=f[i ^ (1<<j)]; for(int i=1;i<=m;i++) dfs(mask-a[i]-1,a[i]); int ans=0; for(int i=1;i<=m;i++) ans+=(fa[a[i]]==a[i]); cout<<ans<<'\n'; }
转载于:https://www.cnblogs.com/zsben991126/p/11164868.html
