题意:输入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.且该组后面的操作直接忽略；
#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:\n",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\n",a,b,v); if(!flag && !_union(a,b,v)){ printf("The first %d facts are conflicting.\n",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\n",ret); } } puts(""); } return 0; }
原文：http://www.cnblogs.com/hxer/p/5185823.html
