HDU 3234 Exclusive-OR

Posted on Edited on Disqus:
, ,

扩展的并查集，参考了以下两个，结合了一下，然后对Query的部分有一些改动，主要是用了map来判断出现次数的奇偶

X1...Xn−1X_1...X_{n-1}，这是题中所说的未给出的nn个数，维护一个带权的并查集，每个点有一个权ww

保证有w[k] = Xk ^ Xfa[k]，Xfa[k]表示Xk的父亲。

对于

I p q v

则对p, q进行Union操作，并利用v维护各自的权w

对于

I p v

可以加入虚拟节点nn，令Xn = 0， 这样任意以该节点为父亲的节点均有w[k] = Xk;

这样就转化成I p n v了

而对于每次查询

Q k p1 p2 ... pk

结果ans = Xp1 ^ Xp2 ^ ... ^ Xpk = w[p1] ^ w[p2] ^ ... ^ w[pk] ^ (Xfa[p1] ^ Xfa[p2] ^ ... ^ Xfa[pk]).

这里利用了性质：

任取整数a，有

a ^ a = 0;

a ^ 0 = a;

又因为 w[p1] ... w[pk] 是已知的, 只需判断 Xfa[p1] ... Xfa[pk] 是否已知即可，即看这些节点是否以Xn为根。

注意的一点是 Xfa[p1] ... Xfa[pk] 中会有重复的，只要出现了偶数次就不用计算，只用考虑出现奇数次的就行了。

另一点注意的是输入输出的形式以及输入行尾换行符的处理，我就在这个地方WA了n多次= =

#include<iostream>
#include<stack>
#include<cstring>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;

const int N = 20000 + 1;
const int K = 15;
const int LINELEN = 150;

int fa[N], w[N];
int n,q;
int nfacts;
char line[LINELEN];

void init()
{
    for(int i = 0; i<= n; i++)
        fa[i] = i;
    memset(w, 0, sizeof(w));

    nfacts = 0;
}

int Find(int x)
{
    if(x != fa[x])
    {
        int t = fa[x];
        fa[x] = Find(fa[x]);
        w[x] ^= w[t];
    }
    return fa[x];
}

bool Union(int p, int q, int v)
{
    int rp = Find(p);
    int rq = Find(q);
    if(rp == rq)
    {
        return  v == (w[p] ^ w[q]);
    }

    if(rp == n) swap(rp,rq);

    fa[rp] = rq;
    w[rp] = w[p] ^ w[q] ^ v;
    return true;
}

bool info(int a, int b, int c)
{
    bool rt = Union(a, b, c);
    if(!rt)
        printf("The first %d facts are conflicting.\n", nfacts);
    return !rt;
}

int main(int argc, char *argv[])
{
#ifdef ACM
    freopen("ttwo.in", "r", stdin);
#endif // ACM

    int ncase = 1;
    while(scanf("%d %d", &n, &q), n != 0 || q != 0)
    {
        printf("Case %d:\n", ncase++);
        init();
        bool conflict = false;

        while(q--)
        {
            char tp[5];
            scanf("%s", tp);
            if(tp[0] == 'I')
            {
                nfacts++;
                getchar();gets(line);
                int a, b, c;
                int rt = sscanf(line, "%d %d %d", &a, &b, &c);
                if(rt == 2)
                {
                    c = b; b = n;
                }

                if(conflict) continue;

                conflict = info(a, b, c);
            }
            else if(tp[0] == 'Q')
            {
                int k;
                int para;
                map<int, bool> fas;
                bool known = true;
                int ans = 0;

                scanf("%d", &k);
                for(int i = 0; i!= k; i++)
                {
                    scanf("%d", &para);

                    if(conflict) continue;

                    fas[Find(para)] = !fas[Find(para)];
                    ans ^= w[para];
                }

                if(conflict) continue;

                for(map<int, bool>::iterator it = fas.begin(); it != fas.end(); it++)
                {
                    if(it->second)
                    {
                        ans ^= w[it->first];
                        if(!(known = (Find(it->first) == n)))
                            break;
                    }
                }

                if(!known)
                {
                    puts("I don't know.");
                }
                else
                {
                    printf("%d\n", ans);
                }
            }
        }

        putchar('\n');
    }

    return 0;
}

BTW，做惯了USACO，发现对这种复杂的IO真心不习惯了= =，WA了何止10次啊…= =

最后的问题竟然是…Case的C忘了大写= =…