Tree and Xor题解

sidekick257 · 2024-01-15 19:44:40 · 题解

update on 2023.2.15 感谢 @lalaouye 指出错误

无解当且仅当 n=3。

不难发现树高最多三层，接下来给出证明：

在第二层没接满的时候显然接到第三层不如接到第二层，在第二层满的时候第二层的点数一定可以加一而不是连到第三层，因为答案至少是 \lfloor\frac{n}{2}\rfloor（设 k=\lfloor\frac{n}{2}\rfloor，如果 n 是偶数则 1 下面接 k 个，2 下面接 k-1 个，如果是奇数则考虑 k 的奇偶性，如果是奇数则 2 下面接 k-2 个点，3 和 4 下面接 1 个，是偶数则 1 下面接 k+1 个点，2 下面接 k-1 个点 ）。

接下来考虑第二层有 k 的点所需要的最少的总点数。

显然最优情况是对于 k 的每一个二进制上是 1 的位 x，都存在一个第二层的点下面接了 2^x-1 个点，即 2k-\text{count}(k)，这样就可以轻易找到对于输入的 n 第二层接了多少个点了。

接下来我们会发现我们会有最优构造完了之后剩下的点，我们可以花 1 的代价把最优构造中每一个第二层中的点转接到一个接了点的的点下面，我们选择将他接到 2 号点下面。

因为我们接的点的数量都是互不相同的二进制上的某一位，所以转接是不会冲突的，而为什么是最优因为如果用两个一样的来抵消一定是没有这样转接有优的，因为用两个一样的只有一半可以接到 2 下面。

最后如果剩下来一个点可以直接接到 2 下面不会冲突。

（PS：据说存在转成 2n-2 个点的序列的做法，但是我不会证。）