Exclusive-OR - UVALive 4487 - Virtual Judge (vjudge.net)
题目描述
有n个小于的非负整数
但你不知道他们的值，提供Q个信息或者问题，根据这些信息回答问题
I p v:我告诉你
I p q v;我告诉你
Q k X1 X2 ...,你需要回答的答案
如果I操作与前面的操作矛盾输出The first i facts are conflicting.
如果Q操作得不出答案输出I don’t know.
样例
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.
算法1
(带权并查集 + 异或得性质 + 建立虚根)
首先我们必须明确一个性质一个数异或另一个数偶数次则等于这个数本身，异或奇数次等于异或上另一个数
一个数异或上0是他本身
我们用带权并查集维护这样得操作
我们定义一个虚根T这个T得值是确定得为0
对于操作一 I p v我们可以将它看成一个
根据一个数抑或上0是他本身，这样我们就将操作1和操作2统一起来了
用
p[x]表示节点x得父节点，Xor[x]表示节点x和父节点得异或值在路径压缩得过程将
更新为x与连通块根节点得异或值
在这一点上我被卡住了，卡住的原因是我一直以为路径压缩之后
根 / .... / b / a / x 我认为路径压缩后Xor[x] = x ^ a ^ b ^ ... ^ 根 实际上路径压缩之后Xor[x] = x ^ 根 因为我们维护的是边的异或值，边上的权值是两个节点的异或值 即: x-——a——-b——-...—-—根 x^a a^b b^.. ..^根 路径压缩之后Xor[x] = (x^a)^(a^b)^ ...^(..^根) 由于一个数异或偶数次等于异或0 所以最后Xor[x] = x ^ 根
接着来看矛盾的情况如果查询的两个数（我们已经统一了两个I操作）的根节点相同那么他们的异或值是确定的
Xor[p] = p ^ 根 Xor[q] = q ^ 根 p ^ q = Xor[p] ^ Xor[q] = p ^ 根 ^ 根 ^ q 只要Xor[p] ^ Xor[q] != val就矛盾
我们只需要判断他们异或值是否等于val即可
如果这两个数合并
假设fp为p的根节点的值 fq为q的根节点的值 因为Xor[p] = p ^ fp Xor[q] = q ^ fq fp --- fq p^fp/ \q ^ fq / \ p q 我们需要从fp和fq之间连一条边这条边的权值是fq ^ fp 因为我们知道val = p ^ q fp ^ fq = fp ^ fq ^ (p ^ q) ^ (p ^ q) = (fp ^ p) ^ (fq ^ q) ^ val = Xor[p] ^ Xor[q] ^ val这里有个细节T节点是不能有父节点的所以如果有一个根节点为T我们需要将另一个节点的根节点街道T上，即T必须永远为根节点
对于询问的矛盾的情况根据异或偶数次等于异或0所以我们统计所有异或值得根节点
如果存在一个根节点出现了奇数次（除T外）那么就不能确定最终得答案
时间复杂度&preview=true)
参考文献
C++ 代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
// #include <unordered_map>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>
#include <map>
#define x first
#define y second
#define P 131
#define lc u << 1
#define rc u << 1 | 1
using namespace std;
typedef long long LL;
const int N = 40000;
int T = N - 1;
int p[N],Xor[N];
int kase;
char op[50];
bool st[N];
int a[N];
int n,q;
int find(int x)
{
if(p[x] != x)
{
int root = find(p[x]);
Xor[x] ^= Xor[p[x]];
p[x] = root;
}
return p[x];
}
bool check(int a,int b,int val)
{
int pa = find(a);
int pb = find(b);
if(pa == pb)
{
if((Xor[a] ^ Xor[b] ^ val) == 0) return true;
else return false;
}
if(pb == T) swap(pa,pb);
Xor[pb] = Xor[a] ^ Xor[b] ^ val;
p[pb] = pa;
return true;
}
inline void solve()
{
while(scanf("%d%d",&n,&q) == 2 && (n || q))
{
// cout << n << " "<< q << endl;
printf("Case %d:\n",++kase);
for(int i = 0;i <= n + 1;i ++)
{
p[i] = i,Xor[i] = 0;
st[i] = 0;
}
p[T] = T,Xor[T] = 0;
st[T] = 0;
bool flag = false;
int facts = 0;
while(q --)
{
scanf("%s",op);
if(*op == 'I')
{
int fir,sed,v;
gets(op);
facts ++;
if(sscanf(op,"%d%d%d",&fir,&sed,&v) == 2)
{
v = sed;
sed = T;
}
if(flag) continue;
if(!check(fir,sed,v))
{
printf("The first %d facts are conflicting.\n",facts);
flag = true;
}
}else
{
int k;
scanf("%d",&k);
int res = 0;
for(int i = 0;i < k;i ++)
{
scanf("%d",&a[i]);
int pa = find(a[i]);
res ^= Xor[a[i]];
if(pa != T)
{
st[pa] ^= 1;
}
}
bool Know = false;
for(int i = 0;i < k;i ++)
{
int pa = find(a[i]);
if(st[pa]) Know = true;
st[pa] = 0;
}
if(flag) continue;
if(Know) puts("I don't know.");
else printf("%d\n",res);
}
}
puts("");
}
}
int main()
{
int _ = 1;
// freopen("network.in","r",stdin);
// freopen("network.out","w",stdout);
// init(N - 1);
// scanf("%d",&_);
while(_ --)
{
// scanf("%lld%lld",&n,&m);
solve();
// test();
}
return 0;
}
京公网安备 11010502036488号