「AtCoder AGC035-C」Skolem XOR Tree

Description

构造一棵 $2n$ 个点的树,点的编号为 $1 \sim 2n$,其中编号为 $i$ 和 $n + i$ 的点的权值为 $i\ (1 \leq i \leq n)$,使得 $i$ 到 $n + i$ 的路径上所有点的点权异或和为 $i$(包括 $i$ 和 $n + i$ 本身)。

$(1 \leq n \leq 10^5)$

Source

[AtCoder]AGC035-C

Solution

考虑转化问题,对于编号为 $i$ 和 $n + i$ 的点,设它们路径上除自己外所有点的异或和为 $sum$,则有 $i \oplus sum \oplus i = i$,化简可得 $sum = i$ 。所以我们必须要找到若干个点,满足点权异或和为 $i$ 。

首先当 $n$ 是 $2$ 的幂时无解(包含 $n = 1$),因为此时不存在任何其它点的异或和为 $n$($n$ 二进制下最高位的 $1$ 肯定无法得到)。

一种可行的构造方法是:

把节点 $1$ 当做根。我们可以把 $x$ 和 $x \oplus 1$ 与根连接(如图)。

Zb5Dnx.png

这样恰好可以同时使 $x$ 和 $x \oplus 1$ 符合条件,而且不需要其它权值的节点。当 $x$ 是偶数时,$x \oplus 1 = x + 1$,所以我们可以把除根节点之外的点分成若干组:$\{2,3\},\{4,5\},\{6,7\},\cdots$,每一组都用上述方法构造。至于最后多出来的节点 $n + 1$,因为 $x \oplus (x \oplus 1) = 1$,所以可以接在第三层中任意一个节点的下面,为了方便这里把 $n + 1$ 接在了 $3$ 的下面。

下图是一个例子($n = 7$):

Zb5sHK.png

注意这样做当 $n$ 为偶数时会多出 $2$ 个节点 $n$ 和 $n + n$ 。考虑怎么在已构造的树上放置这 $2$ 个节点。

此时我们可以找到 $n$ 在二进制下最高位上的 $1$ 在第 $bit$ 位,然后把 $n$ 接在权值为 $2^{bit} \oplus 1$ 的点下面(由于 $2^{bit}$ 一定是偶数,所以等价于 $2^{bit} + 1$)。很容易证明这个值是大于 $1$ 且小于 $n$ 的,且一定能在树的第二层找到权值为这个值的点(这个值是奇数,所以点的编号应为 $(2^{bit} \oplus 1) + n$)。$n$ 到根的异或和(不含自己)为 $2^{bit} \oplus 1 \oplus 1 = 2^{bit}$,我们只需要把 $n + n$ 接在 $n \oplus 2^{bit}$ 的下方,就能符合题目的条件(因为 $2^{bit} \oplus (n \oplus 2^{bit}) = n$,且能够保证 $n \oplus 2^{bit} < n$,还是一个偶数,同样可以在第二层找到权值为这个值的点)。

下图是一个例子($n = 6$):

ZqBdYV.png

Remarks

Special Judge 写法:假设 $1$ 号节点为根,预处理出所有节点到根的路径异或和,枚举权值 $i$,用树上差分求路径异或和。

Code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
x = 0;
char c = getchar();
bool f = 0;
for (; !isdigit(c); c = getchar()) f ^= c == '-';
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
x = f ? -x : x;
}

template <class T>
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
T y = 1;
int len = 1;
for (; y <= x / 10; y *= 10) ++len;
for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

int n, m, bit;

inline void printEdge(int u, int v) {//输出无向边 u -> v
write(u);
putchar(' ');
write(v);
putchar('\n');
}

int main() {
read(n);
for (int i = 0; (1 << i) <= n; ++i)
if (n == (1 << i)) {//判断是否为 2 的幂
puts("No");
return 0;
}
puts("Yes");
for (int i = 2; i + 1 <= n; i += 2) {
printEdge(1, i), printEdge(i, i + 1);
printEdge(1, i + n + 1), printEdge(i + n + 1, i + n);
//对于每组 { x, x ^ 1 } 连边
}
printEdge(3, n + 1);//把 n + 1 接在 3 的下面
if (!(n & 1)) {// n 是偶数
for (int i = 0; (1 << i) <= n; ++i)
if (n & (1 << i)) bit = i;//找到最高位的 1
printEdge(((1 << bit) ^ 1) + n, n), printEdge(n ^ (1 << bit), n << 1);
}
return 0;
}

本文标题:「AtCoder AGC035-C」Skolem XOR Tree

文章作者:Heartlessly

发布时间:2019年07月16日 - 18:25:49

最后更新:2019年10月01日 - 15:25:46

原始链接:https://heartlessly.github.io/problems/atcoder-agc035-c/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%