首页 > 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. 什么是人?人是具有创造力和发现力的高等动物。人作为生命个体,无可争议的拥有免于恐惧的权利。人和动物的根本区别在于人具有创造力和发现力,创造和发现来自于自由,因此自由的权利是人与生俱来的。人权就是免于恐惧的权利和自由的权利。自由就是只要不使人恐惧,就可以做

  3. 什么是人?人是具有创造力和发现力的高等动物。人作为生命个体,无可争议的拥有免于恐惧的权利。人和动物的根本区别在于人具有创造力和发现力,创造和发现来自于自由,因此自由的权利是人与生俱来的。人权就是免于恐惧的权利和自由的权利。自由就是只要不使人恐惧,就可以做

  4. 什么是人?人是具有创造力和发现力的高等动物。人作为生命个体,无可争议的拥有免于恐惧的权利。人和动物的根本区别在于人具有创造力和发现力,创造和发现来自于自由,因此自由的权利是人与生俱来的。人权就是免于恐惧的权利和自由的权利。自由就是只要不使人恐惧,就可以做

  5. 什么是人?人是具有创造力和发现力的高等动物。人作为生命个体,无可争议的拥有免于恐惧的权利。人和动物的根本区别在于人具有创造力和发现力,创造和发现来自于自由,因此自由的权利是人与生俱来的。人权就是免于恐惧的权利和自由的权利。自由就是只要不使人恐惧,就可以做

  6. 什么是人?人是具有创造力和发现力的高等动物。人作为生命个体,无可争议的拥有免于恐惧的权利。人和动物的根本区别在于人具有创造力和发现力,创造和发现来自于自由,因此自由的权利是人与生俱来的。人权就是免于恐惧的权利和自由的权利。自由就是只要不使人恐惧,就可以做

  7. 我没看懂题目
    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
    不知道题目例子是怎么得出来的

  8. 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])