NKOJ 3762 守夜人 （并查集）

发表于 |
字数统计: 1,654字 | 阅读时长 ≈ 8min

P3762守夜人

问题描述

鉴于john snow当选了新的守夜人总司令，艾里沙爵士感觉非常不爽，想搞点事情来难倒snow。艾里沙爵士告诉你有一个n项的序列X0,X1,X2…..Xn-1。（其中每一项均在int范围之内）但是你现在不知道其中的任何一项。艾里沙会逐步的告诉你一些信息并且问你一些问题。共有两种类型的信息和一种类型的询问。

I p v : 告诉你 Xp = v

I p q v : 告诉你 Xp XOR Xq = v

Q k p1 p2 . . . pk : 询问Xp1 XOR Xp2 XOR . . . XOR Xpk的值 k≤15

输入格式

会有多组测试数据但不会超过10组。
每一组数据以两个整数开始：n , Q(1 ≤ n ≤ 20, 000, 2 ≤ Q ≤ 40, 000)题目描述中的k是一个不大于15的整数。
最后一组数据为n==Q==0，不用进行运算。

输出格式

对于每组数据，输出第一行为数据的组数，接下来的每一行对应一次询问的答案。
如果根据前面给出的信息无法算出答案，则输出“I don’t know.”。
如果与已知信息冲突，输出“The first i facts are conflicting.”，并结束对于这一组数据的运算，其中i为这组数据出现过的的信息条数（不含询问，包含当前这一条信息）。

样例输入

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.

提示

注释：
鉴于两种I操作的输入比较麻烦，这里给出一种参考输入方法：
gets(s);
if(sscanf(s,”%d%d%d”,&a,&b,&v)==2)
//这一行输入了两个整数，要先除去行首的字母,具体可参考代码

这题显然是带权并查集，用$D[i]$来记录下$i$和的他父亲的异或值。考虑如何处理三个操作。

先处理路径压缩，假设fx是x的父亲，ffx是fx的父亲，由异或运算的特性可知x^ffx=x^fx^fx^ffx=D[x]^D[fx]，所以路径压缩就解决了。

考虑已知$x_p$^$x_q=v$，那么合并p，q所在集合，令fp是p的根，fq是q的根，那么将fq设为fp的父亲，有D[fp]=fp^fq=p^fp^q^fq^p^q=D[p]^D[q]^v，所以合并操作解决。

然后问题是处理操作一，这里有两种处理办法，一种是添加虚拟节点，将操作一视为操作二，并保证虚拟节点永远是根。具体可以参考THH的博文。

我用的是第二种操作，直接用数组X[i]记录下他的值即可，然后为了维护X[i]，需要将路径压缩中添加一步，即如果父亲的X值已知，那么就顺便把儿子的X值算出来，因为知道他们的异或和。同时合并时要优先将X值已知的元素作为父亲。

然后考虑如何判断矛盾，关于操作一，那么只需要和X数组比较一下即可。对于操作二稍复杂，我们需要判断两种情况：
1.给出的两个数p，q位于同一集合，那么判断给出的值是否等于D[p]^D[q]。
2.p，q不在同一集合，那么判断是否两个数的X值都已知，如果都已知就判断给出的值是否等于X[p]^X[q]

最后处理询问操作，首先将询问的k个元素中已知的元素找出来并标记，直接异或到ans中，然后处理未知的元素，这些未知的元素必然要两两配对异或起来，因此直接暴力找位于同一集合的元素异或起来并异或到答案中，如果有不能配对的元素，那么就得不到答案，如果都配对的，就找到了。这里写的时候优化一下可以$O(k)$解决。

代码：

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
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 43333
using namespace std;
int n,m,F[N],X[N],V[N],A[20];
bool mark1[20],mark2[20];
char s[N];
int GF(int x)
{
	if(F[x]==x)return x;
	int t=F[x];
	F[x]=GF(F[x]);
	if(X[t]!=-1)X[x]=V[x]^X[t];//更新X值
	V[x]^=V[t];//更新V值
	return F[x];
}
int main()
{
	int i,j,a,b,v,p,q,cnt,k,o,fx,fy,pp,T=0,ans;
	scanf("%d%d",&n,&m);
	while(n!=0)
	{
		printf("Case %d:\n",++T);
		for(i=1;i<=n;i++)F[i]=i,V[i]=0,X[i]=-1;
		cnt=0;
		for(i=1;i<=m;i++)
		{
			scanf("%s",s);
			if(s[0]=='I')
			{
				cnt++;
				gets(s);
				if(sscanf(s,"%d%d%d",&a,&b,&v)==2)
			    {
			    	a++;
			    	p=GF(a);
			    	if(X[a]!=-1&&b!=X[a])
			    	{
			    		printf("The first %d facts are conflicting.\n",cnt);
			    		break;
					}
					X[a]=b;
					F[a]=a;F[p]=a;//把他设为所在集合的根
					V[p]=V[a];V[a]=0;
					continue;
			    }
			    a++;b++;
			    p=GF(a);q=GF(b);
			    if(X[a]!=-1&&X[b]!=-1)
				{
					if((X[a]^X[b])!=v)
					{
						printf("The first %d facts are conflicting.\n",cnt);
			   		    break;
					}
				}
			    if(p==q)
				{
					if((V[a]^V[b])!=v)
					{
						printf("The first %d facts are conflicting.\n",cnt);
			    		break;
					}
				}
				if(X[p]!=-1)swap(p,q);//优先将X值已知的元素作为根
				F[p]=q;
				V[p]=V[a]^V[b]^v;
			}
			else
			{
				gets(s);
				o=sscanf(s,"%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d",&k,&A[1],&A[2],&A[3],&A[4],&A[5],&A[6],&A[7],&A[8],&A[9],&A[10],&A[11],&A[12],&A[13],&A[14],&A[15]);//智障的读入
				memset(mark1,0,sizeof(mark1));
				pp=0;ans=0;
				for(j=1;j<=k;j++)A[j]++,GF(A[j]);
				for(j=1;j<=k;j++)
				if(X[A[j]]==-1&&mark1[j]==0)//未知元素
				{
					fx=GF(A[j]);
					ans^=V[A[j]];
					mark1[j]=1;o=1;
					for(p=1;p<=k;p++)
					if(X[A[p]]==-1&&mark1[p]==0)
					{
						fy=GF(A[p]);
						if(fx==fy)
						{
							o++;ans^=V[A[p]];
							mark1[p]=1;
						}
					}
					if(o&1){pp=1;break;}//一个集合中可以一次处理完
				}
				else if(mark1[j]==0)ans^=X[A[j]],mark1[j]=1;//已知元素
				if(pp){printf("I don't know.\n");continue;}
				printf("%d\n",ans);
			}
		}
		while(i<m){gets(s);i++;}
		scanf("%d%d",&n,&m);
	}
}