压位加速-poj-2443-Set Operation

题目意思：

有n个集合（n<=1000),每个集合有m个数ai（m<=10000,1=<ai<=10000),同一个集合中可能有相同的数.有q个查询（q<=200000),对于每个查询a,b，问是否存在一个集合同时包含a和b.

解题思路：

题目意思很简单，但时间和内存限制比较大，需要压位加速处理。

两种解法

解题思路一：

将每一个集合看成是一行，也成了一个1000*10000的0、1矩阵，对于每个数来书，它所在的列的0、1分布情况也就是它所在集合的情况。但问题是现在一共有1000行，2^1000肯定不行，但考虑到一个int可以存32位（2^32），1000<32*32,所以可以开32个整数，每个整数的二进制的每一位代表每一行，这样就可以在q*32的可接受的时间复杂度内查询出结果。将扫描1000变为扫描32，利用整数的位操作减少为1/32。

代码：

#include<iostream>  
#include<cmath>  
#include<cstdio>  
#include<cstdlib>  
#include<string>  
#include<cstring>  
#include<algorithm>  
#include<vector>  
#include<map>  
#include<set>  
#include<stack>  
#include<list>  
#include<queue>  
#include<ctime>  
#define eps 1e-6  
#define INF 0x3f3f3f3f  
#define PI acos(-1.0)  
#define ll __int64  
#define lson l,m,(rt<<1)  
#define rson m+1,r,(rt<<1)|1  
#pragma comment(linker, "/STACK:1024000000,1024000000")  
using namespace std;  
  
#define Maxn 11000  
int sa[Maxn][35];//sa[i][j]表示i这个数在[32*j,32*j+31]集合区间的出现情况  
//一个int可以保存32个集合的信息，一共只有1000个集合所有只用32个整型即可  
  
int main()  
{  
   int n;  
  
   while(~scanf("%d",&n))  
   {  
       for(int i=0;i<n;i++)  
       {  
           int num;  
           scanf("%d",&num);  
           for(int j=1;j<=num;j++)  
           {  
               int a;  
               scanf("%d",&a);    //i/32代表该集合在那个整数里面  
               int bit=1<<(i%32); //i%32代表该集合在该整数中的第几位 位置  
               //if((sa[a][i/32]&bit)==0) //之前没有出现，因为一个集合可能有多个相同的数  
                sa[a][i/32]|=bit;  
           }  
       }  
       int q;  
       scanf("%d",&q);  
       for(int i=1;i<=q;i++)  
       {  
           int a,b;  
           scanf("%d%d",&a,&b);  
           bool flag=false;  
           for(int i=0;i<32;i++)  
                if(sa[a][i]&sa[b][i])  
                {  
                    flag=true;  
                    break;  
                }  
            if(flag)  
                printf("Yes\n");  
            else  
                printf("No\n");  
       }  
   }  
   return 0;  
}

解法二：

用STL里面的bitset来做。

代码：

#include<iostream>  
#include<cmath>  
#include<cstdio>  
#include<cstdlib>  
#include<string>  
#include<cstring>  
#include<algorithm>  
#include<vector>  
#include<map>  
#include<set>  
#include<stack>  
#include<list>  
#include<queue>  
#include<ctime>  
#include<bitset>  
#define eps 1e-6  
#define INF 0x3f3f3f3f  
#define PI acos(-1.0)  
#define ll __int64  
#define lson l,m,(rt<<1)  
#define rson m+1,r,(rt<<1)|1  
  
#pragma comment(linker, "/STACK:1024000000,1024000000")  
using namespace std;  
  
bitset<1100>myb[11000],temp;  
  
int main()  
{  
   int n;  
  
   while(~scanf("%d",&n))  
   {  
       for(int i=1;i<=10000;i++)  
            myb[i].reset(); //清0  
       for(int i=0;i<n;i++)  
       {  
           int num;  
           scanf("%d",&num);  
           for(int j=1;j<=num;j++)  
           {  
               int a;  
               scanf("%d",&a);  
               myb[a].set(i); //置1  
           }  
       }  
       int q;  
       scanf("%d",&q);  
       for(int i=1;i<=q;i++)  
       {  
           int a,b;  
           scanf("%d%d",&a,&b);  
           temp=myb[a]&myb[b];  
           if(temp.any()) //是否存在1  
                printf("Yes\n");  
           else  
                printf("No\n");  
       }  
   }  
   return 0;  
}

补充：软件开发 , C++ ,