首页 > ACM题库 > HDU-杭电 > HDU 3234-Exclusive-OR-并查集-[解题报告]HOJ
2014
03-09

HDU 3234-Exclusive-OR-并查集-[解题报告]HOJ

Exclusive-OR

问题描述 :

You are not given n non-negative integers X0, X1, …, Xn-1 less than 220 , 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:

Download Manager

输入:

There will be at most 10 test cases. Each case begins with two integers n and Q (1 <= n <= 20,000, 2 <= Q <= 40,000). Each of the following lines contains either a fact or a question, formatted as stated above. The k parameter in the questions will be a positive integer not greater than 15, and the v parameter in the facts will be a non-negative integer less than 220. The last case is followed by n=Q=0, which should not be processed.

输出:

There will be at most 10 test cases. Each case begins with two integers n and Q (1 <= n <= 20,000, 2 <= Q <= 40,000). Each of the following lines contains either a fact or a question, formatted as stated above. The k parameter in the questions will be a positive integer not greater than 15, and the v parameter in the facts will be a non-negative integer less than 220. The last case is followed by n=Q=0, which should not be processed.

样例输入:

2 6
I 0 1 3
Q 1 0
Q 2 1 0
I 0 2
Q 1 1
Q 1 0
3 3
I 0 1 6
I 0 2 2
Q 2 1 2
2 4
I 0 1 7
Q 2 0 1
I 0 1 8
Q 2 0 1
0 0

样例输出:

Case 1:
I don't know.
3
1
2
Case 2:
4
Case 3:
7
The first 2 facts are conflicting.

/*
 *  解法: 带权并查集神题.
 *        设置了一个超级根, 如果树中的一个数可以确认, 则将这棵树连接到超级根上.
 *        这样就简化了算法复杂性.
 */
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 20005;
int N, Q, pare[maxn], cnt;
__int64 edge[maxn];
bool flag;
void init()
{
    cnt = 0;
    flag = 1;
    memset(pare, -1, sizeof(pare));
}
void Conflict()
{
    flag = 0;
    printf("The first %d facts are conflicting./n", cnt);
}
void find(int x, int &r, __int64 &v)
{
    if (pare[x] == -1)
    {
        r = x;
        v = 0;
    }
    else
    {
        find(pare[x], r, v);
        v = v ^ edge[x];
        edge[x] = v;
        pare[x] = r;
    }
}
void mearge(int x, int y, __int64 v)
{
    if (x > y)
        swap(x, y);
    pare[x] = y;
    edge[x] = v;
}
void Ifunc()
{
    char str[20];
    __int64 a, b, c;
    gets(str);
    if (!flag)
        return;
    cnt++;
    if (sscanf(str, "%I64d %I64d %I64d", &a, &b, &c) == 3)
    {
        int r1, r2;
        __int64 v1, v2;
        find(a, r1, v1);
        find(b, r2, v2);
        if (r1 == r2)
        {
            if (c != (v1 ^ v2))
            {
                Conflict();
            }
        }
        else
        {
            mearge(r1, r2, v1 ^ v2 ^ c);
        }
    }
    else
    {
        int r;
        __int64 v;
        find(a, r, v);
        if (r == N)
        {
            if (b != v)
            {
                Conflict();
            }
        }
        else
        {
            mearge(r, N, v ^ b);
        }
    }
}
void Qfunc()
{
    int k, x, i, r, ary[16], idx = 0;
    __int64 ans = 0, v;
    scanf("%d", &k);
    for (i = 0; i < k; i++)
    {
        scanf("%d", &x);
        find(x, r, v);
        ans = ans ^ v;
        if (r != N)
            ary[idx++] = r;
    }
    getchar();
    if (!flag)
        return;
    if (idx % 2 == 1)
    {
        printf("I don't know./n");
        return;
    }
    sort(ary, ary + idx);
    for (i = 0; i < idx; i += 2)
        if (ary[i] != ary[i+1])
            break;
    if (i != idx)
        printf("I don't know./n");
    else
        printf("%I64d/n", ans);
}
void InputCmd()
{
    char cmd;
    scanf("%c", &cmd);
    if (cmd == 'I')
        Ifunc();
    else
        Qfunc();
}
int main()
{
    int i, cas = 1;
    while (scanf("%d %d", &N, &Q), N || Q)
    {
        getchar();
        printf("Case %d:/n", cas++);
        init();
        for (i = 0; i < Q; i++)
        {
            InputCmd();
        }
        printf("/n");
    }
    return 0;
}

参考:http://blog.csdn.net/RaceBug2010/article/details/6095418


  1. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  2. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])