HDU 3234 Exclusive-OR 09年武漢地区試合E題

また1本の不思議な並列調査集で、以前POJの上で並列調査集をして、いわゆるオフセットベクトルを使ったことがあって、息子と父の関係は1つのベクトル値で表して、それから息子と息子の間の関係もいくつかのベクトル関係を通じて転化することができて、この問題も並列調査集のオフセットベクトルの運用であるべきで、ただその点だけ複雑で、異或演算になって、それから挿入する时いくつかの小さいすばらしい考えがあって、それから他の人の考えを见てやっと発见して、本当に耻ずかしくて、このようにやっとACしました.
挿入する時、2つの数、あるいは3つの数の情況が現れて、実はすべて3つの数に転化することができて、私達はすべて1つの数と0の異或値がすべて彼自身であることを知っていて、それでは賦値演算を1つの値が0のノードと異或に等価にすればいいので、このノードをnにして、それから互いに関係があるのはすべて1つの集合の中に置いて、オフセットベクトルを観察すると,実際にはいくつかのノードの異種または値が父親ノードの異種または値と再び異種に変換され,父親ノードの個数が偶数であれば結果に影響を及ぼさないことが明らかになった.奇数であれば,父親ノードの値が知れば計算できる.符号nのノード値はすでに知っているので、できるだけ親ノードにしなければならない.そうすれば、与えられたノードはすべてnの集合内にある.明らかに、既知の2つのノードの異或値と1つのノードの値が現れ、別のノードの値を求める場合、このノードの親ノードはnであるため、では、この点に関連するノードがnの集合と結合すれば、値も出てくるので、値が知っているノードがnの集合内にある限り、親ノードがnではないノードの値は必然的に分からない.では最後に判断してみましょう.

/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define LOCA
#define MAXN 500005
#define INF 100000000
#define eps 1e-7
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
int n, delta[20005];
int father[20005];
void init()
{
    for(int i = 0; i <= n; i++)
    {
        father[i] = i;
        delta[i] = 0;
    }
}
int find(int x)
{
    if(father[x] == x)
    return x;
    int t = find(father[x]);
    delta[x] ^= delta[father[x]];
    father[x] = t;
    return t;
}
bool join(int x, int y, int v)
{
    int fx = find(x);
    int fy = find(y);
    if(fx == fy)
    {
        return v == (delta[x] ^ delta[y]);
    }
    else if(fx == n)
    {
        father[fy] = fx;
        delta[fy] = delta[x] ^ delta[y] ^ v;
    }
    else if(fy == n)
    {
        father[fx] = fy;
        delta[fx] = delta[x] ^ delta[y] ^ v;
    }
    else
    {
        father[fx] = fy;
        delta[fx] = delta[x] ^ delta[y] ^ v;
    }
    return 1;
}
int main()
{
#ifdef LOCAL
    freopen("d:/data.in","r",stdin);
    freopen("d:/data.out","w",stdout);
#endif
    int i, j, q, x, y, v, k, tmp, ca = 1;
    char s[105];
    char nu[5];
    while(scanf("%d%d", &n, &q) != EOF)
    {
        if(n == 0 && q == 0) break;
        bool error = false;
        init();
        int fact = 0;
        printf("Case %d:
",ca++);
        while(q--)
        {
            scanf("%s", nu);
            if(nu[0] == 'I')
            {
                fact++;
                gets(s);
                if(error) continue;
                int ct = sscanf(s, "%d %d %d", &x, &y, &v);
                if(ct == 2)
                {
                    v = y;
                    y = n;
                    if(!join(x, y, v))
                    {
                        error = true;
                        printf("The first %d facts are conflicting.
", fact);
                    }
                }
                else
                {
                    if(!join(x, y, v))
                    {
                        error = true;
                        printf("The first %d facts are conflicting.
", fact);
                    }
                }
            }
            else
            {
                scanf("%d", &k);
                map<int, int>mp;
                int ans = 0;
                bool can = true;
                for(i = 0; i < k; i++)
                {
                    scanf("%d", &tmp);
                    if(error) continue;
                    int t = find(tmp);
                    mp[t]++;
                    ans ^= delta[tmp];
                }
                map<int, int>::iterator it;
                for(it = mp.begin(); it != mp.end(); it++)
                {
                    if(it -> second % 2) //          
                    {
                        if(it -> first != n) //      n，     ，       
                        {
                            can = false;
                            break;
                        }
                    }
                }
                if(error) continue;
                if(can)
                printf("%d
", ans);
                else printf("I don't know.
");
            }
        }
        puts("");
    }
    return 0;
}