POJ 2443 Set Operation 题解

题意:

给定一堆集合和一堆询问,每次询问给出两个数 (x,y),如果 (x)(y) 出现在了同一个集合内,则输出 Yes,否则输出 No

考虑把每个数字所出现的位置记下来,并使用 bitset。

每次询问的时候,就将两个 bitset 做一个与运算,只要有一个为 (1) 就直接输出。

时间复杂度 (O(N imes c_i+2000 imes Q))

如下为 (C^{ ext{艹}}) 代码:

bitset<1010> bit[10010],t;
int n,x,y,q;
int main() {
 scanf("%d",&n);
 for(int i=1;i<=n;i++) {
  scanf("%d",&x);
  for(int j=1;j<=x;j++) {
   scanf("%d",&y);
   bit[y][i]=1;
  }
 }
 scanf("%d",&q);
 while(q--) {
  scanf("%d %d",&x,&y);
  t=bit[x]&bit[y];
  if(t.any())
   puts("Yes");
  else
   puts("No");
 }
}
原文地址:https://www.cnblogs.com/lajiccf/p/13019682.html