题解 | #小红的完全二叉树构造#

1. 问题分析）

• 是偶数 是偶数。
• 只有当 和 均为奇数时，乘积才为奇数。

因此，该约束等价于：在二叉树中，任何两个相邻（父子关系）的节点不能同时为奇数。

构造一个 个节点的完全二叉树，其拓扑结构是唯一确定的。我们需要将 的排列填入这个固定的结构中。

• 奇数集合 ()：数量为 。
• 偶数集合 ()：数量为 。

在图论术语中，我们需要在二叉树（作为一种特殊的二部图）中找到一个独立集（Independent Set），其大小至少为 ，用来放置所有的奇数。

2. 算法

2.1 二部图染色

任何树结构都是二部图（Bipartite Graph）。我们可以通过对节点进行二染色（例如颜色 0 和颜色 1），使得任意一条边的两个顶点颜色不同。

• 令 为颜色为 0 的节点集合（例如深度为奇数的节点）。
• 令 为颜色为 1 的节点集合（例如深度为偶数的节点）。

由于二叉树是二部图，这两个集合内部不存在任何边。也就是说， 和 各自都是一个独立集。

2.2 鸽巢原理

根据鸽巢原理，在 个节点的二叉树中，。 已知奇数的个数 恰好等于 。 因此，必然存在至少一个颜色集合的大小大于或等于奇数的总数。

2.3 构造

1. 计算深度奇数层和偶数层的节点索引集合。
2. 统计两组集合的大小。
3. 选择容量较大的集合（或足以容纳 的集合）优先填入奇数。
4. 剩余的位置填入偶数。

这种策略保证了所有的奇数节点都被放置在同一色组内，或者其邻居全在另一色组且另一色组全部被（或部分被）偶数占据。由于奇数节点之间不相邻，满足“任何边不存在两个奇数”的条件。

3. 代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    vector<int> odds, evens;
    for (int i = 1; i <= n; ++i) {
        if (i % 2 != 0) odds.push_back(i);
        else evens.push_back(i);
    }

    // 将完全二叉树的节点索引按二部图染色（根据深度奇偶性）
    // p0 存储颜色为 0 的节点索引，p1 存储颜色为 1 的节点索引
    vector<int> p0, p1;
    vector<int> color(n + 1);
    for (int i = 1; i <= n; ++i) {
        if (i == 1) {
            color[i] = 0; // 根节点设为颜色 0
        } else {
            color[i] = 1 - color[i / 2]; // 颜色与其父节点相反
        }

        if (color[i] == 0) p0.push_back(i);
        else p1.push_back(i);
    }

    vector<int> res(n + 1);
    vector<int>* target_p, *other_p;
    if (p0.size() >= odds.size()) {
        target_p = &p0;
        other_p = &p1;
    } else {
        target_p = &p1;
        other_p = &p0;
    }

    int odd_idx = 0;
    for (; odd_idx < odds.size(); ++odd_idx) {
        res[(*target_p)[odd_idx]] = odds[odd_idx];
    }

    int even_idx = 0;

    for (int j = odd_idx; j < target_p->size(); ++j) {
        res[(*target_p)[j]] = evens[even_idx++];
    }

    for (int j = 0; j < other_p->size(); ++j) {
        res[(*other_p)[j]] = evens[even_idx++];
    }

    for (int i = 1; i <= n; ++i) {
        cout << res[i] << (i == n ? "" : " ");
    }
    cout << endl;

    return 0;
}