UVALive 4487 Exclusive-OR 加权并查集神题

已知有 x[0-(n-1)],但是不知道具体的值，题目给定的信息只有 I P V，说明 Xp=V，或者 I P Q V，说明 Xp ^ Xq=v,然后要求回答每个询问，询问的是某任意的序列值 Xp1^Xp2,,,,X^pk

这个题目用加权并查集是这么处理的：

1. f[]照样是代表父节点，照样进行路径压缩，把每个 V[i]=V[i]^V[f[i]]，即节点存储的值实际是它与它父亲的异或的值。为什么要这样呢，因为异或首先满足交换律，而且异或同一个数偶数次，即相当于本身，那么这个题目的其中一个要求是探测冲突，则如果两个点同属一个集合,那么他们的 Xp^Xq=Xp^Xf^Xq^Xf=v[p]^v[q],就是利用了异或偶数次等于本身的原理，在真正计算的时候，也是这样，只有父节点被异或了偶数次才可以被消除，求得真正的值，只有其中有一个或者以上的父节点经过了奇数次的异或，说明根本就求不出来，输出 I don't know.

2.为了应对I P V 这种直接赋值的做法，人为添加一个超级父节点T，v[T]=0每次让它跟T来异或，这样就不用特殊处理了

3.每次合并的时候，T一定要是父节点，特判一下。find的时候，进行路径压缩，同时对加权进行合并，通过异或偶数等于本身的特性，将底下的节点顺利的转化为父节点的子节点。

4.注意一下！运算的优先级高于^,为了这个WA了几次，以后涉及位运算的，多写括号，感觉不是第一次被优先级给坑了。

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int N = +;

int f[N],v[N];

int vis[N],a[];

int T=N-;

void init(int n)

{

    for (int i=;i<=n+;i++){

        f[i]=i;

        v[i]=;

        vis[i]=;

    }

    f[T]=T;

    v[T]=;

}

int findset(int x)

{

    if (x!=f[x]){

        int tmp=f[x];

        f[x]=findset(f[x]);

        v[x]^=v[tmp];//因为v[x]本身就包括了异或上一层父节点的值，此时与上一层再异或一次，就抵消了

    }

    return f[x];

}

bool uset(int p,int q,int val)

{

    int r1=findset(p);

    int r2=findset(q);

    if (r1==r2){

        if ((v[p]^v[q])!=val) return ;

        else return ;

    }

    if (r1==T) swap(r1,r2);

    f[r1]=r2;

    v[r1]=v[p]^v[q]^val;//这里要注意，实际V[r1]=xr1^xr2，而Vp和Vq包含这两项，并且用val把他们自身给抵消了，就剩下那两项了，异或确实是很奇妙

    return ;

}

int main()

{

    int n,Q,p,q,val,kase=;

    char ch[];

    char s[];

    while(scanf("%d%d",&n,&Q))

    {

        if (!(n+Q)) break;

        init(n);

        printf("Case %d:\n",++kase);

        bool err=;

        int facts=;

        for (int i=;i<=Q;i++){

            scanf("%s",ch);

            if (ch[]=='I'){

                facts++;

                gets(s);

                if (sscanf(s,"%d%d%d",&p,&q,&val)==) {

                    val=q;q=T;

                }

                //cout<<p<<" "<<q<<" "<<val<<endl;

                if (err) continue;

                if (!uset(p,q,val)){

                    printf("The first %d facts are conflicting.\n",facts);

                    err=;

                }

            }

            else {

                int k,ans=;

                scanf("%d",&k);

                for (int i=;i<=k;i++){

                    scanf("%d",&a[i]);

                    if(err) continue;

                    int r=findset(a[i]);

                    ans^=v[a[i]];

                    a[i]=r;

                    vis[r]^=;

                }

                if (err) continue;

                bool flag=;

                for (int i=;i<=k;i++){

                    if (vis[a[i]]){//这里判断是否是奇数次

                        if (a[i]!=T){//如果奇数次是超级父节点，没关系，因为他的值已知

                            flag=;

                        }

                         vis[a[i]]=;

                    }

                }

                if (flag) printf("%d\n",ans);

                else printf("I don't know.\n");

            }

        }

        puts("");

    }

return ;

}

巴特西

UVALive 4487 Exclusive-OR 加权并查集神题

最新文章

热门文章