题目解析

本题的核心是构造一个长度为 2n 的排列，使得相邻元素的按位异或值之和最小。要实现这一目标，关键在于利用格雷码（Gray Code） 的核心性质：相邻两个格雷码的二进制表示仅有一位不同。 由于两个数的按位异或结果等于其二进制不同位的权值之和，因此相邻数仅有一位不同时，单次异或结果最小（仅为该位的权值），整体异或和也能达到理论下界。而格雷码的构造公式 G(i)=i⊕(i>>1)（其中 i 从 0 到 2n−1）恰好能生成满足要求的排列，该排列是长度为 2n 的合法排列，且相邻异或和最小。

输入描述

输入一个正整数 n（1≤n≤18）。

输出描述

在一行中输出 2n 个整数，表示构造的满足相邻异或和最小的排列（若有多个合法解，输出任意一个即可）。

#include <functional>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
#define endl '\n'
int main() {
    IOS;
    int n;
    cin >> n;
    // 生成0到2^n -1的格雷码，即为所求排列
    for (int i = 0; i < (1 << n); ++i) {
        cout << (i ^ (i >> 1)) << " ";
    }
    cout << endl;
    return 0;
}

验证

测试用例 1

输入：1 输出：0 1（或 1 0，均合法） 验证：排列长度为 21=2，相邻异或和为 0⊕1=1，是理论最小值。

测试用例 2

输入：2 输出：0 1 3 2 验证： 排列长度为 22=4，是 0~3 的合法排列； 相邻异或和：0⊕1=1、1⊕3=2、3⊕2=1，总和为 4，达到理论下界。

测试用例 3

输入：3 输出：0 1 3 2 6 7 5 4 验证：排列长度为 23=8，是 0~7 的合法排列；相邻元素均仅有一位二进制位不同，异或和为理论最小值。