Exclusive-OR
题意:输入n个点和Q次操作(1 <= n <= 20,000, 2 <= Q <= 40,000).操作和叙述的点标号k(0 < k < n)
操作分为I & Q两种,I又分为 I a v表示val[a] = v和 I a b v 即val[a] ^ val[b] = v; Q k X0,X1...Xk-1表示求出X0^X1^...^Xk-1 = ?
对于每个Q操作，结果分为 I don't know.即不能求解或输出确定值，对于每组叙述操作，若叙述与之前的矛盾则输出改标号:The first 2 facts are conflicting.且该组后面的操作直接忽略；
Sample Input (只是一组)
2 6
I 0 1 3
Q 1 0
Q 2 1 0
I 0 2
Q 1 1
Q 1 0
0 0Sample Output
Case 1:
I don't know.
3
1
2
思路:根据压缩路径的同时可以得到每个子节点到根节点的XOR的相对值；即XOR[i] = XOR[i] ^ XOR[root];将该异或结果存储在子节点中。当根节点未知时，不能确定子节点的值；但是根据XOR的特性可知，当子节点的个数为偶数时，就可以将根节点消去，这就是在求解Q 操作时，对于每个id[]都是分集合(同根节点)求解的。此题有一个区别就是可以根据I操作知道若干个节点的值，并且可以根据XOR的关系推出其他节点的值。这个特性甚是无语啊。。(难点)那么是否就需要另外存储每一个节点的值？这么想会发现很复杂，因为这脱离了并查集；每次需要判断是否是确定值，并且之间的推断感觉不好编码，这是需要转化为并查集；
构造：构造出一个节点n，表示所有已知值的根节点；这时可以将已知节点的值直接看成是该节点与根节点n的XOR值，和未知值节点的共性；
细节:对于在_union()中，判断fa是否为n,这一点是为了维护n一定是已知值节点的根节点；不能认为a反正不会是n，而去除；
code是参考了ACM_cxlove (是我网上看到除了notonlySuccess的线段树之外，写得最好的code,顶一个，风格和我差不多。。)后自己写的；痕迹明显。。
#include<iostream> #include<cstdio> #include<cstring> #include<string.h> #include<algorithm> #include<map> #include<queue> #include<vector> #include<cmath> #include<stdlib.h> #include<time.h> using namespace std; #define rep0(i,l,r) for(int i = (l);i < (r);i++) #define rep1(i,l,r) for(int i = (l);i <= (r);i++) #define rep_0(i,r,l) for(int i = (r);i > (l);i--) #define rep_1(i,r,l) for(int i = (r);i >= (l);i--) #define MS0(a) memset(a,0,sizeof(a)) #define MS1(a) memset(a,-1,sizeof(a)) const int MAXN = 20020; int n,f[MAXN]; int XOR[MAXN],id[MAXN<<1];//每个点到根节点(压缩之后)的XOR，以及Q查询的id; int Find(int a)//** { if(a == f[a]) return a; int fa = Find(f[a]); XOR[a] ^= XOR[f[a]]; return f[a] = fa; } bool _union(int a,int b,int v) { int fa = Find(a),fb = Find(b); if(fa == fb){//同一个集合就可以计算出两个点之间的异或值；和下面的偶数一致 if((XOR[a] ^ XOR[b]) != v) return false; return true; } if(fa == n) swap(fa,fb);//是对于输入了a,b,v来看的，并不是对a v,b = n来设置的 f[fa] = fb; XOR[fa] = XOR[b]^v^XOR[a]; return true; } char op[1000]; int vis[20]; int Query(int k) { MS0(vis); int ans = 0; rep0(i,0,k){ int cnt = 0; int root = Find(id[i]); rep0(j,i,k){ if(!vis[j] && Find(id[j]) == root){//同属一个集合； cnt++; vis[j] = true; ans ^= XOR[id[j]]; } } if(root != n && (cnt & 1)) return -1; } return ans; } int main() { int Q,kase = 1; while(scanf("%d%d",&n,&Q) == 2 && n + Q){ rep1(i,0,n) f[i] = i,XOR[i] = 0; printf("Case %d: ",kase++); int cnt_i = 0,flag = 0; while(Q--){ scanf("%s",op); if(op[0] == 'I'){ int space = 0,a,b,v; cnt_i++; getchar();gets(op); rep0(i,0,strlen(op))if(op[i] == ' ') space++; if(space & 1){ sscanf(op,"%d%d",&a,&v); b = n; }else{ sscanf(op,"%d%d%d",&a,&b,&v); } //printf(" %d %d %d ",a,b,v); if(!flag && !_union(a,b,v)){ printf("The first %d facts are conflicting. ",cnt_i); flag = 1; } }else{ int k; scanf("%d",&k); rep0(i,0,k){ scanf("%d",id+i); } if(flag)continue; int ret = Query(k); if(ret == -1) puts("I don't know."); else printf("%d ",ret); } } puts(""); } return 0; }