| CCF CAT NAEC 2025 (Final) |
|---|
| Закончено |
对于非负整数 $$$x$$$,我们定义 $$$\mathrm{pos} (x, i)$$$ 表示 $$$x$$$ 的第 $$$i$$$ 个二进制位(其中 $$$i \geq 0$$$)。即:
$$$$$$ \mathrm{pos} (x, i) = \left \lfloor \frac{x}{2^i} \right \rfloor - 2 \left \lfloor \frac{x}{2^{i+1}} \right \rfloor $$$$$$
对于两个非负整数 $$$x$$$ 和 $$$y$$$($$$0 \leq x,y \lt 2^{30}$$$),我们定义它们的按位或非 $$$\mathrm{nor} (x, y)$$$ 为:
$$$$$$ \mathrm{nor} (x, y) = \sum_{i=0}^{29} \left [\mathrm{pos} (x, i) = 0 \land \mathrm{pos} (y, i) = 0 \right ] 2^i $$$$$$
其中 $$$[P]$$$ 表示艾弗森括号,当命题 $$$P$$$ 为真时,$$$[P]$$$ 的值为 $$$1$$$,否则为 $$$0$$$。$$$\land$$$ 符号表示逻辑与运算。
也就是说,当且仅当 $$$x$$$ 和 $$$y$$$ 的第 $$$i$$$ 位都为 $$$0$$$ 的时候,$$$\mathrm{nor} (x, y)$$$ 的第 $$$i$$$ 位为 $$$1$$$;其余情况下,$$$\mathrm{nor} (x, y)$$$ 的第 $$$i$$$ 位都为 $$$0$$$。
对于两个非负整数 $$$x$$$ 和 $$$y$$$,我们定义它们的按位异或 $$$x \oplus y$$$ 为:
$$$$$$ x \oplus y = \sum_{i=0}^{\infty} \left [\mathrm{pos} (x, i) \neq \mathrm{pos} (y, i) \right ] 2^i $$$$$$
给定一个 $$$n$$$ 个节点的无向完全图,节点编号为 $$$0$$$ 到 $$$n-1$$$。对于每一对满足 $$$0 \leq u \lt v \lt n$$$ 的节点 $$$u$$$ 和 $$$v$$$,$$$u$$$ 和 $$$v$$$ 之间有一条边权为 $$$\mathrm{nor} (u, v)$$$ 的边。
请你找出该图的一个生成树,使得生成树中,所有边的边权的按位异或结果尽可能的小。
第一行包含一个整数 $$$T$$$($$$1 \leq T \leq 10^5$$$),表示一共有 $$$T$$$ 组测试数据。
对于每组测试数据:
保证测试数据的 $$$n$$$ 的总和不超过 $$$2 \times 10^5$$$。
对于每组测试数据:
256
0 2 3 1 3 4 2 4 0 1 1 3 2 5 3 5 4 5
样例的两组数据中,生成树的形态如下图所示。
注意:样例输出中的空行是为了让两组数据的输出更易区分而添加的,你的程序不必输出该空行。
| Название |
|---|


