题目链接:Click here~~
题意:
有n个数X0~Xn-1,开始时你不知道它们的值,逐步给你信息:1、直接给出 Xp 的值v。2、给出Xp ^ Xq的值v。然后在线询问某些(15个) Xi 异或的值。
解题思路:
好神奇的并查集啊,据说是偏移向量,基本完全仿照别人的,主要说下思路。
对于这种询问,我们并不一定要知道每个 Xi 的值,就可知道结果。
由于 Xp ^ 0 = Xp,我们可以虚拟一个数 Xn = 0,对于第1种信息,就等价于给出 Xp ^ Xn = v,与第2种信息格式一致。
从而,所有的信息都是两两相关的。那么,能不能和并查集联系起来呢?
我们YY一下,把与互相有关的信息全部放入一个集合。
那么,对于集合间节点间的异或运算,由于没有信息,我们无从下手。
所以,我们只能先将每一个集合内的异或运算计算完毕后,再将所得到的值做异或运算得到最终的解。
而对于集合内节点间的异或运算可以看做节点与根节点异或的值间做异或运算。
并且当且仅当有奇数个数字参与运算的时候,才与根节点的值有关。并且,只有 Xn 所在的集合才知道根节点的值(想一想,为什么)。
所以为了方便,对于 Xn 的集合内我们以 Xn 为根,如果与它的值有关,也是 ^0,对结果无影响。
这样,我们只要维护好这个节点与根节点异或的值就可以不用知道每个节点的值从而将问题更好的解决。
而对于维护操作,就留给读者参照代码自己慢慢理解了。其中有很多细节,好几处代码的顺序不能颠倒,望有心人自己发现。
#include <map>
#include <stdio.h>
#include <string.h>
using namespace std;
#define N 20012
int n,pre[N],val[N];
int Root(int x)
{
if(pre[x] == -1)
return x;
int rt = Root(pre[x]); //fantasy~
val[x] ^= val[pre[x]]; //as above
return pre[x] = rt;
}
bool Union(int a,int b,int v)
{
int r1 = Root(a);
int r2 = Root(b);
if(r1 == r2)
return (val[a]^val[b]) == v; //the priority of '^' is lower than '=='.
if(r2 == n)
swap(r1,r2);
val[r2] = val[a]^val[b]^v; //think about why
pre[r2] = r1;
return true;
}
int main()
{
int Q,p,q,v,k,ncase=0;
char cmd,ccmd[30];
map<int,int> M;
while(scanf("%d%d%*c",&n,&Q),n)
{
printf("Case %d:\n",++ncase);
memset(pre,-1,sizeof(pre));
memset(val,0,sizeof(val));
bool No = false;
int facts = 0;
while(Q--)
{
scanf("%c",&cmd);
if(cmd == 'I')
{
gets(ccmd);
if(No)
continue;
facts++;
if(sscanf(ccmd,"%d%d%d",&p,&q,&v) == 2)
v = q , q = n;
if(!Union(p,q,v))
{
No = true;
printf("The first %d facts are conflicting.\n",facts);
}
}
else
{
M.clear();
int ans = 0;
scanf("%d",&k);
while(k--)
{
scanf("%d",&p);
if(No)
continue;
q = Root(p); //can't exchange the order with the follow line
ans ^= val[p];
M[q]++;
}
getchar();
if(No)
continue;
bool Uncertain = false;
for(map<int,int>::iterator it=M.begin();it!=M.end();it++)
{
if(it->first != n && it->second & 1)
{
Uncertain = true;
break;
}
}
if(Uncertain)
puts("I don't know.");
else
printf("%d\n",ans);
}
}
puts("");
}
return 0;
}
分享到:
相关推荐
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
ACM题库,一些题目和答案,以及解题报告,传上来共享
杭州电子科技大学ACM Steps中Chapter One-Section One的答案集。不要直接抄哦~~ 如需题解请上我的博客~ 博客地址呈上:http://blog.csdn.net/xu_zh
可拆卸核心板滤波电容电源指示灯排针复位F103--R10不焊F207--R9不焊第19引脚F103--C4焊0欧姆,C3不焊Tuesday, August 31
杭州电子科技大学ACM Steps中Chapter One-Section Two的答案集。不要直接抄哦~~ 如需题解请上我的博客~ 博客地址呈上:http://blog.csdn.net/xu_zh
杭电OnlineJudge 200-2099的解题报告
HDU 里面的2000~2099道题目的源码。谢谢支持
排母,核心板接口ADC 电位器扩展接口,预留模拟量Tuesday, August 31, 2021Tuesday, August 31, 2021Tuesday
杭电ACM2000-2099题的解题报告
杭电ACM课件2014版之 (HDUACM201403版_06)并查集(最小生成树)
求多源点到单终点的最短路(反向建图),ACM竞赛中应用的小程序。
基础算法类 ACM 入门 杭电OJ 11页题目题解,算法入门的时候刷题可以参考 搜集整理起来了比单个去搜题解方便快捷
(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树
示例 1:输出:[1,2,3,7,8,11,12,9,10,4,5,6]输入的多级列表如下图所示:扁平化后的链表如下图:示例 2:输出:[1,3,2]解释:输入
其中一类查询要求 更新 数组 nums 下标对应的值另一类查询要求返回数组 nums 中索引 left 和索引 right 之间( 包含 )的nums元素的 和
示例 1:示例 2:解答:大小写转换: n = n ^ 32转小写: n = n | 32转大写: n = n & -33const toLowerCase =
2016. 增量元素之间的最大差值题目描述:给你一个下标从 0 开始的整数数组 nums ,该数组的大小为 n ,请你计算 nums[j] - nums[i]