2-XOR-SAT （种类并查集）-白红宇

2-XOR-SAT （种类并查集）

阅读量：6829 次

发布时间：2019-06-26

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

写了那么多模拟题这题算是最难的了QAQ

好神，，，我于是补了一下并查集。。

并查集很神。。。。。。

orz

种类并查集。。。orz

对于维护sat，我们可以这样想：

如果x和y的xor是true，那么x和y肯定不一样，那么我们有s[x]=s[y]^1

否则s[x]=s[y]

我们需要维护的是一系列的x和y之间的关系，那么我们考虑用并查集维护这个区间！

注意这个一定是区间的概念！

因为只有区间才能满足区间性质！

比如

x xor y xor z = true

而我们得知了x xor y的值，那么我们就能知道x xor z的值！

所以x y z可以看成并查集的一条链，然后假设一开始我们只知道y xor z=true 那么连边fa[y]=z 然后 s[y]=s[x]^1

那么当我们得知x xor y=true 时，我们可以将fa[x]=y 然后s[x]=s[y]^1

而现在的图就是

x -> y -> z

我们可以尝试着压缩x到z的路径，使得得出x->z的值即 fa[x]=z, s[x]^=s[y] 也就是说 x xor z = false

很神奇是不。。

现在我们开始重新定义s数组！

s[i]表示i到i的树根（并查集中的）的xor值

那么根据xor的性质，我们可以在路径压缩里这样写

int f=find(fa[x]); s[x]^=s[fa[x]]; p[x]=f;

那么就可以维护出s了！再一次强调，s表示的是x到树根的xor值！不是它真正的值！（否则就想我一样，一开始怎么想也想不通。。。）

然后我们在合并时，和并查集差不多，只是要维护一下s。即

fx=find(x), fy=find(y)

if(fx!=fy && (x xor y == true)) p[fx]=fy; s[fx]=s[x]^s[y]^1; //这样做的原因很简单，自己想想。。就是根据x xor y=true/false 和 x xor fx=true/false 和 y xor fy=true/false 现在只是要知道fx xor fy = ?。。注意一定不是s[fy]=...因为你看看s的定义。。。。如果是s[fy]=的话，那么p[fx]后边就都乱了。。。

x xor y==false 时也很简单 s[fx]=s[x]^s[y]

判断无解的话就是如果fx == fy 且 x到fx和y到fy的值与所给的x xor y的值不符，那么就是无解。。。

构造解也很简单。我们假设所有的根全都是true

那么问题就简单了。。。。

再路径压缩过后，每个节点到根就是一条路径，那么我们已经知道了根是true。。那么。。不用我说了吧。。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             using namespace std;typedef long long ll;#define pii pair
              
               #define mkpii make_pair
               
                #define pdi pair
                
                 #define mkpdi make_pair
                 
                  #define pli pair
                  
                   #define mkpli make_pair
                   
                    #define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << (#x) << " = " << (x) << endl#define error(x) (!(x)?puts("error"):0)#define printarr2(a, b, c) for1(_, 1, b) { for1(__, 1, c) cout << a[_][__]; cout << endl; }#define printarr1(a, b) for1(_, 1, b) cout << a[_] << '\t'; cout << endlinline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }inline const int max(const int &a, const int &b) { return a>b?a:b; }inline const int min(const int &a, const int &b) { return a