題意：
? ? ? 給你n個未知的正整數，有三總操作
? ? ? I P V ? ? ? ? ? ?P的值是V
? ? ? I P Q V ? ? ? ? ?P XOR Q = V
? ? ? Q K x1 x2....xk ?求這k個數所有異或后的值
思路：
? ? ? 帶權并查集，感覺這個題目用的很巧，設計到以下知識，a ^ b = c ,a ^ c = b ,b?

^ c = a他們三個是等價的，還有就是a ^ b ^ a = b ,這個題目自己好好畫畫就出來了，確定好帶權并查集后可以虛擬出來一個點，把它做為真實點，就是如果誰的根是他那么這個值就已經確定了，我虛擬的是0點，把其他的點都映射成+1，還有就是這個題目的核心部分就是查詢的那個地方，除了確定的點，其他的必須是每個集合都出現了偶數個的時候才能算出來，原因就是“性質不同的數不能乘在一起，要么就是相對位置相乘，要么就是確定的數字相乘，兩個相對位置相乘的到的是確定的數字，確定的數字相乘得到的還是確定的數字”，這個題目設計到很多細節，我就不說了，誰做誰知道啊！ 還有就是提醒個最坑的地方 a ^?b != c 他和 (a ^ b) != c不是等價的，優先級的原因。其他的做的時候就知道了，今天手殘，這個題目做了17次才AC.

#include<stdio.h> #include<string.h>#define N 22000 int mer[N] ,Xor[N]; int ss[N];int finds(int x) {if(x == mer[x]) return x;int t = mer[x];mer[x] = finds(mer[x]);Xor[x] = Xor[x] ^ Xor[t];return mer[x]; }int main () {int n ,m ,i ,j ,num ,p ,q ,v ,k;int n1 ,n2 ,n3 ,cas = 1 ,fact ,stop;char str[10] ,c;while(~scanf("%d %d" ,&n ,&m) && n + m){printf("Case %d:\n" ,cas ++);for(i = 0 ;i <= n ;i ++)mer[i] = i ,Xor[i] = 0;for(stop = fact = 0 ,i = 1 ;i <= m ;i ++){scanf("%s" ,str);if(str[0] == 'I'){fact ++; int ii = 0;while(1){scanf("%d%c" ,&num ,&c);ii ++;if(ii == 1) n1 = num;if(ii == 2) n2 = num;if(ii == 3) n3 = num;if(c == '\n') break;}if(stop) continue;if(ii == 2){p = n1 + 1 ,v = n2;int x = finds(p);if(!x){if(Xor[p] == v) continue;stop = 1;printf("The first %d facts are conflicting.\n" ,fact ++);}else{mer[x] = 0;Xor[x] = Xor[p] ^ v;}}if(ii == 3){p = n1 + 1 ,q = n2 + 1 ,v = n3;int x = finds(p) ,y = finds(q);if(x == y){if((Xor[p] ^ Xor[q]) == v) continue;stop = 1;printf("The first %d facts are conflicting.\n" ,fact ++);}else{if(y){mer[y] = x;Xor[y] = Xor[p] ^ Xor[q] ^ v; }else{mer[x] = y;Xor[x] = Xor[p] ^ Xor[q] ^ v; }}}}else{scanf("%d" ,&k);memset(ss ,0 ,sizeof(ss));int sum = 0 ,mk = 0;for(j = 1 ;j <= k ;j ++){scanf("%d" ,&num);num ++;ss[finds(num)] ++;sum = sum ^ Xor[num];}for(j = 1 ;j <= n ;j ++)if(ss[j] & 1) mk = 1;if(stop) continue;if(mk) puts("I don't know.");else printf("%d\n" ,sum);}}puts("");}return 0; }

總結

以上是生活随笔為你收集整理的hdu3234 带权并查集（XOR）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。