压位加速-poj-2443-Set Operation - c++编程基础

题目意思：

有n个集合（n<=1000),每个集合有m个数ai（m<=10000,1=

解题思路：

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

两种解法

解题思路一：

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

代码：

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#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

解法二：

用STL里面的bitset来做。

代码：

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#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