POJ 2443 Set Operation（压位加速）

题意：

有1000个集合，每个集合有至多10000个数，之后输入多个询问，判断询问的两个数是否位于同一个集合。

思路：

位运算...很强大！！

用二进制来判断是否位于这个集合，0表示不在，1表示处于在的。

那么对于1000个集合来说，就需要1000位的二进制，一个int型的数可以保存32的二进制，32*32>1000，所以我们只需要32位的数组就可以表示出这1000个集合。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<vector>
 6 #include<queue>
 7 #include<cmath>
 8 #include<map>
 9 using namespace std;
10 
11 int n,q;
12 int s[10005][35];
13 
14 int main()
15 {
16     //freopen("D:\input.txt","r",stdin);
17     while(~scanf("%d",&n))
18     {
19         for(int i=0;i<n;i++)
20         {
21             int num;
22             scanf("%d",&num);
23             while(num--)
24             {
25                 int x;
26                 scanf("%d",&x);
27                 int bit=1<<(i%32);
28                 s[x][i/32]|=bit;
29             }
30         }
31         scanf("%d",&q);
32         int x,y;
33         while(q--)
34         {
35            scanf("%d%d",&x,&y);
36            bool flag=false;
37            for(int i=0;i<32;i++)
38            {
39                if(s[x][i]&s[y][i])
40                {
41                    flag=true;
42                    break;
43                }
44            }
45            if(flag)  puts("Yes");
46            else puts("No");
47         }
48     }
49 }