压位加速-poj-2443-Set Operation-白红宇

压位加速-poj-2443-Set Operation

阅读量：6003 次

发布时间：2019-06-20

本文共 1565 字，大约阅读时间需要 5 分钟。

题目链接：

题目意思：

有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
    
     #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 11000int 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

转载地址：http://fidmx.baihongyu.com/

你可能感兴趣的文章