HDU 3234 Exclusive-OR
本文导语: 扩展的并查集，参考了以下两个，结合了一下，然后对Query的部分有一些改动，主要是用了map来判断出现次数的奇偶http://www.cppblog.com/Yuan/archive/2010/09/02/125667.html?opt=adminhttp://blog.csdn.net/acm_cxlove/article/details/8101710X1...Xn-1，这是...
扩展的并查集，参考了以下两个，结合了一下，然后对Query的部分有一些改动，主要是用了map来判断出现次数的奇偶
http://www.cppblog.com/Yuan/archive/2010/09/02/125667.html?opt=admin
http://blog.csdn.net/acm_cxlove/article/details/8101710
X1...Xn-1，这是题中所说的未给出的n个数，维护一个带权的并查集，每个点有一个权w
保证有w[k] = Xk ^ Xfa[k]; Xfa[k]表示Xk的父亲。
对于
I p q v
则对p, q进行Union操作，并利用v维护各自的权w
对于
I p v
可以加入虚拟节点n，令Xn = 0; 这样任意以该节点为父亲的节点均有 w[k] = Xk;
这样就转化成I p n v了
而对于每次查询
Q k p1 p2 ... pk
结果ans = Xp1 ^ Xp2 ^ ... ^ Xpk = w[p1] ^ w[p2] ^ ... ^ w[pk] ^ (Xfa[p1] ^ Xfa[p2] ^ ... ^ Xfa[pk]).
这里利用了性质：
任取整数a，有
a ^ a = 0;
a ^ 0 = a;
又因为 w[p1] ... w[pk] 是已知的, 只需判断 Xfa[p1] ... Xfa[pk] 是否已知即可，即看这些节点是否以Xn为根。
注意的一点是Xfa[p1] ... Xfa[pk] 中会有重复的，只要出现了偶数次就不用计算，只用考虑出现奇数次的就行了。
另一点注意的是输入输出的形式以及输入行尾换行符的处理，我就在这个地方WA了n多次= =
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 using namespace std;
9
10 const int N = 20000 + 1;
11 const int K = 15;
12 const int LINELEN = 150;
13
14 int fa[N], w[N];
15 int n,q;
16 int nfacts;
17 char line[LINELEN];
18
19 void init()
20 {
21 for(int i = 0; ipackage jie.java.test;
public class main {
public static class Holder {
private T value = null;
public Holder(T value) {
this.setValue(value);
}
public T getValue() {
return value;
}
public void setValue(T value) {
this.value = value;
}
}
private static void paramTest(Integer in, Holder o) {
// o = new Holder(100);
o.setValue(in);
}
public static void main(String[] args) {
Integer i = 10;
Holder o = new Holder(0);
paramTest(i, o);
System.out.println("o = " + o.getValue());
}
}
本站(WWW.)站内文章除注明原创外，均为转载、整理或搜集自网络。欢迎任何形式的转载，转载请注明出处。