我是靠谱客的博主 朴实电脑,这篇文章主要介绍UVA -2232(并查集 + 位运算),现在分享给大家,希望可以做个参考。

首先,说些关于异或的信息,异或满足交换律和结合律,这为用并查集创造了条件。

又有 a^b= x, b^c=y; a^c=x^y;

本题目有三种操作,两种存,一种查。对于建立并查集时候要维护两个信息,第一个就是当前节点和root异或的值,当前集合是否存在已知量(之需要确保根部知道这个情况就可以,一个集合里有一个一致,那么该集合任一元素都可以通过异或得到)

查的时候分为两种情况,第一种该元素所在集合没有已知值得点,那么这个集合里的元素在要查集合里有且仅有两个该集合才有解。

剩下的元素,一个个算就可以了。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <set> #include <algorithm> using namespace std; #define rep(i,n) for(int (i)=0;(i)<(n);(i)++) const int maxn = 51000; int p[maxn],d[maxn],hav[maxn]; int find(int x){ if(p[x] == x) return x; if(hav[p[x]]==-1){ hav[p[x]]=hav[x]; } int root=find(p[x]); d[x]^=d[p[x]]; return p[x]=root; } int a[maxn],n,m,val[maxn]; void init(){ rep(i,n){ p[i]=i; d[i]=0; hav[i]=-1; } } char str[maxn]; void cal(int& cnt){ int len = strlen(str); rep(i,len){ if(isdigit(str[i])){ int j,num=0; for(j=i;j<len;j++){ if(!isdigit(str[j])) break; num=num*10+str[j]-'0'; } a[cnt++]=num; i=j; } } } int cmp(int i,int j){ return find(i)<find(j); } int main () { int kase=1; while(scanf("%d %d",&n,&m)==2&&n){ printf("Case %d:n",kase++); init(); gets(str); int ok = 1,counter=0; rep(gg,m){ gets(str); if(!ok) continue; int cnt = 0; cal(cnt); if(str[0]=='I'){ counter++; if(cnt == 2){ int px=find(a[0]); if(hav[px]!=-1){ find(hav[px]); if( (val[hav[px]]^d[hav[px]]^d[a[0]])!=a[1]){ ok = 0; } } else { hav[px] = a[0]; val[a[0]] = a[1]; } } else{ int px=find(a[0]),py=find(a[1]); if(px==py){ if((d[a[0]]^d[a[1]])!=a[2]) ok = 0; } else { d[px]=(d[a[0]]^a[2]^d[a[1]]); p[px]=py; find(px); } } } else { int hav_ans = 1,res=0; sort(a+1,a+cnt,cmp); for(int i=1;i<cnt;i++){ int px=find(a[i]); if(hav[px]==-1){ int ju[2]={0}; if(i+1<cnt&&find(a[i+1])==px) ju[0]=1; if(i+2>=cnt||(i+2<cnt&&find(a[i+2])!=px)) ju[1]=1; if(ju[0]&&ju[1]) { res = (res^d[a[i]]^d[a[i+1]]); i+=1; } else hav_ans = 0; } else { find(hav[px]); res=res^(val[hav[px]]^d[hav[px]]^d[a[i]]); } if(!hav_ans) break; } if(!hav_ans) printf("I don't know.n"); else printf("%dn",res); } if(!ok) printf("The first %d facts are conflicting.n",counter); } printf("n"); } return 0; }


最后

以上就是朴实电脑最近收集整理的关于UVA -2232(并查集 + 位运算)的全部内容,更多相关UVA内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(72)

评论列表共有 0 条评论

立即
投稿
返回
顶部