Exclusive-OR

链接 HDU - 3234

---

$补充知识、$
$有axorb==c则axorc==b，bxorc==a$
$axora=0$
$axor0=a$
$解题的主体思路是用节点与根节点的异或值来完成插入与查询操作$
$最核心的理解就是find函数中d[x]异或等于d[p[x]]这一步就是确保每次插入后$
$d[x]都是x节点与x的祖先节点的异或值，这里就用到了axora==0这个性质了$
$还有一个核心操作就是每次尽可能让n当祖先节点$
$因为n为祖先的时候，因为n节点的值是0，用到了axor0=a性质，所以d[x]就是x本身的值$
$查询操作就是匹配祖先节点，两两匹配就可以抵消掉祖先节点的值得到两个节点值异或的值$
$当a,b祖先都是g的时候d[a]xord[b]=v[a]xorv[b]xorv[c]xorv[c]xorv[c]$
$所以祖先相同时d[a]xord[b]=v[a]xorv[b],所以查询就是找偶数个相同祖先的异或起来，这样就能得到真实值异或起来的值$
$当祖先为n时就可以不管个数时奇数偶数了，因为这时候d[a]=v[a]，所以插入的时候需要尽可能把祖先节点靠在n上$
$而不是改变n的祖先，如果改变n的祖先就乱套了，v[n]就可能不等于0了，可以多想一下这里$
$第一种插入就转变为第二种插入操作，用n代替原本的b因为d[n]=0$
$判断单值就是看是否祖先为n,不是的话就加上祖先，是的话就判断d[a]xord[n]等不等c，这时候d[a]xord[n]=d[a]=v[a]$

$代码$

---

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<sstream>
#include<unordered_map>

using namespace std;

const int N = 1e6+20000;

int n, q, idx, th;
int d[N], p[N], st[20];
bool con;

unordered_map<int,int> cnt;

int find(int x)
{
    
      
	if(x != p[x])
	{
    
      
		int root = find(p[x]);
		//因为祖先变的有先有后，所以要确保
		//d[x]不管谁是祖先的时候都是和当前祖先节点的异或值，而不是
		//和各个祖先节点的异或累加
		//d[x] ^= d[root];
		d[x] ^= d[p[x]];
		p[x] = root;
	}
	return p[x];
}

void init()
{
    
      
	for(int i = 0; i <= n; i ++) p[i] = i;
	memset(d, 0, sizeof(d));
}

void solve(int a,int b,int c)
{
    
      
	int pa = find(a);
	int pb = find(b);
	if(pa == pb)
	{
    
      
		if((d[a] ^ d[b]) != c)
		{
    
      
			printf("The first %d facts are conflicting.\n", th);
			con = true;
		}
	}
	else
	{
    
      
		if(pa == n) swap(pa, pb);
		p[pa] = pb;	
		d[pa] = d[a] ^ d[b] ^ c;
		        //d[pa] = v[pa] ^ v[pb]
				//d[a] = v[a] ^ v[pa]
				//d[b] = v[b] ^ v[pb]
				//v[a] ^ v[b] = c
				//d[a] ^ d[b] = v[a] ^ v[b] ^ v[pa] ^ v[pb]
				//d[a] ^ d[b] ^ c = v[pa] ^ v[pb]
	}
}

int main()
{
    
      
	int thi = 0;
	while((cin >> n >> q), (n && q))
	{
    
      
	con = false;
	thi++;
	init();
	th = 0;
	char op;
	getchar();
	printf("Case %d:\n",thi);
	while(q --)
	{
    
      
	idx = 0;
	string s;
	getline(cin, s);
	stringstream ssin(s);
	ssin.tie(0);
	ssin >> op;
	while(ssin >> st[idx]) idx++;
	if(con) continue;
	if(op == 'I')
	{
    
      
		th ++;
		if(idx == 2)
		{
    
      
			//v[a] ^ v[n] = b;
			int a = st[0];
			int b = st[1];
			solve(a, n, b);	
		}
		else if(idx == 3)
		{
    
      
			int a = st[0];
			int b = st[1];
			int c = st[2];
			solve(a, b, c);
//		
		}
	}
	else if(op == 'Q')
	{
    
      
		int k = st[0]; 
		int res = 0;
		cnt.clear();
		for(int i = 1; i <= k; i ++)
		{
    
      
			int a = st[i];
			int pa = find(a);
			
			res ^= d[a];//这个bug找半天
			if(pa != n)
			{
    
      
				cnt[pa] ++;
			}
		}	
		bool fg = false;
		unordered_map<int,int>::iterator it = cnt.begin();
		for(; it != cnt.end(); ++ it)
		{
    
      
			int b = it->second;
			if(b % 2)
			{
    
      
			fg = true;
			break;	
			}
		}	
			if(fg) puts("I don't know.");	
			else
			printf("%d\n", res);
			
		}	
	}
	puts("");
	}
	
	return 0;
}

---