2014
03-09

# 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.

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

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;
}

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]）