Link

http://acm.hdu.edu.cn/showproblem.php?pid=3234

Problem

You are not given n non-negative integers X0, X1, …, Xn-1 less than 2 20 , but they do exist, and their values never change.

I’ll gradually provide you some facts about them, and ask you some questions.

There are two kinds of facts, plus one kind of question:

Mean

有N个数,初始不知道他们的值。有Q次事实或询问。

事实有两种:第p个数的值为v;第p个数异或第q个数的值为v。

询问为查询N(<=15)个数的异或值。

Analysis

巧妙又典型的带权并查集,同时又利用了异或的性质:A^B=1, B^C=2, ∴A^C = 1^2 = 3.

根据这个性质,就可以用并查集将有异或关系的数并到同一集合,这样集合内任意两个数的异或值便已知。

新建虚拟节点N,值为0。将所有已知值的集合并到节点N上。

查询时,如果是以N为根结点的集合中,则全部已知。如果是在其他集合中,如果在某一集合中出现了偶数次则可计算,奇数次不可计算。

Code

#include <bits/stdc++.h>
using namespace std;

const int maxn = 20480;
int N, Q;
int pa[maxn], val[maxn];
char op[30];

int K, qu[30];
vector<int> rv;

void init() {
    for(int i = 0; i < maxn; ++i) {
        pa[i] = i;
        val[i] = 0;
    }
}

int Find(int x) {
    if(pa[x] == x)
        return x;
    int rt = Find(pa[x]);
    val[x] ^= val[pa[x]];
    return pa[x] = rt;
}

bool Union(int x, int y, int d) {
    int rx = Find(x), ry = Find(y);
    if(rx == ry)
        return (val[x] ^ val[y]) == d;
    if(rx == N) {
        swap(x, y);
        swap(rx, ry);
    }
    pa[rx] = ry;
    val[rx] = val[x] ^ val[y] ^ d;
    return true;
}

int query() {
    rv.clear();
    for(int i = 0; i < K; ++i)
        rv.push_back(Find(qu[i]));
    sort(rv.begin(), rv.end());
    if(rv.back() != N && rv.size() % 2)
        return -1;
    for(int i = 1; i < rv.size(); i += 2)
        if(rv[i] != rv[i-1])
            return -1;
    int ans = 0;
    for(int i = 0; i < K; ++i)
        ans ^= val[qu[i]];
    return ans;
}

int main() {
    int kase = 0;
    while(scanf("%d%d", &N, &Q), N || Q) {
        printf("Case %d:\n", ++kase);
        init();
        bool ok = true;
        int cnt = 0;
        for(int i = 0; i < Q; ++i) {
            scanf("%s", op);
            if(op[0] == 'I') {
                cnt += 1; gets(op);
                if(!ok) continue;
                int p, q, v;
                if(sscanf(op, "%d%d%d", &p, &q, &v) == 2)
                    v = q, q = N;
                if(!Union(p, q, v)) {
                    ok = false;
                    printf("The first %d facts are conflicting.\n", cnt);
                }
            }
            else if(op[0] == 'Q') {
                scanf("%d", &K);
                for(int i = 0; i < K; ++i)
                    scanf("%d", qu + i);
                if(!ok) continue;
                int ans = query();
                ans == -1 ? puts("I don't know.") : printf("%d\n", ans);
            }
        }
        puts("");
    }
    return 0;
}

欢迎留言