UVA 12232 Exclusive-OR（并查集+思想）-白红宇

UVA 12232 Exclusive-OR（并查集+思想）

阅读量：6296 次

发布时间：2019-06-22

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

题意：给你n个数，接着三种操作：

I p v ：告诉你 Xp = v

I p q v ：告诉你 Xp ^ Xq = v

Q k p1 p2 … pk：问你k个数连续异或的结果

注意前两类操作可能会出现与之前告诉你的相矛盾，此时输出“The first n（第几个I） facts are conflicting.”接着一直保持沉默，否则不输出。最后一类询问可能得不到值，就输出“I don’t know.”，否则输出结果

　　题解：告诉你时使用并查集的合并操作，可以记录权值为此点异或父亲节点的值，祖先节点的权值一定为0（其他值异或0不变），因为：X^X1^X1^X2=X^X2 则可以进行路径压缩。

　　但是我们知道一个集合的关系时，却不一定知道每个元素各自的大小，所以再记录一个权值2，当一个集合祖先的权值2非负时，表示祖先确定大小了，而这个集合就一定可以知道每个元素的大小，否则就不知道。我们合并时就要注意某子树是否知道每个元素的大小。

　　询问是首先将明确其大小的值计算出来。而只知道关系一些数：如果有偶数个在同一集合，那这偶数个就可以运用它们间的关系一同求出。

　　这儿还有一个小麻烦就是当输入I时，后面个数不定，所以可以使用sscanf处理。

　　真不愧是神题啊，我copy文档的“I don’t know.”居然是错的。。。。。。。。。。。。。。。。。。。。。。。。。。。。错的。。。。。。。。。。。。。。。。。。。。。。。。。。

#include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 using namespace std;#define eps 1E-8/*注意可能会有输出-0.000*/#define Sgn(x) (x<-eps? -1 :x
                 
                   0.0 ? x+eps : x-eps)//浮点数转化#define zero(x) (((x)>0?(x):-(x))
                  
                   >b)typedef long long ll;typedef unsigned long long ull;const int Inf=1<<28;const double Pi=acos(-1.0);const int Mod=1e9+7;const int Max=20010;int fat[Max],ran[Max],num[Max];int tem[20],tem1;void Init(int n){ for(int i=0; i<=n; ++i) { fat[i]=i; ran[i]=0; num[i]=-1; } return;}int Find(int x){ if(x==fat[x]) return fat[x]; int y=Find(fat[x]); ran[x]=(ran[x]^ran[fat[x]]);//异或优先级很低 return fat[x]=y;}int Union(int x,int y,int z){ int x1=Find(x); if(y==-1)//确定一个值 { if(num[x1]==-1) { num[x1]=(ran[x]^z); return 1; } if(num[x1]==(ran[x]^z)) return 1; return 0; } int y1=Find(y); if(x1==y1) { if((ran[x]^ran[y])==z) return 1; return 0; } if(num[x1]==-1)//x集合不知道每个值得权值 { fat[x1]=y1; ran[x1]=(ran[x]^ran[y]^z); return 1; } else { fat[y1]=x1; ran[y1]=(ran[x]^ran[y]^z); if(num[y1]==-1) return 1; else { if((num[x1]^num[y1])==ran[y1]) return 1; return 0; } }}int Solve(int n)//询问{ int ans=0,vis[20]; for(int i=0; i

转载于:https://www.cnblogs.com/zhuanzhuruyi/p/5863758.html

你可能感兴趣的文章