解题思路

1. 目标函数按位拆分

设需要构造两两不同的正整数序列 $b_1,\dots,b_n$。 目标为最小化

按位独立性：对任一第 $t$ 位（权值 $2^t$），若有 $c_t$ 个数该位为 1，则这一位对总和的贡献为

因为只有“一零”或“零一”的配对才贡献 $2^t$。因此每一位都希望 $c_t$ 尽量接近 0 或 n，尤其是高位（权大）必须避免被一部分数为 0、一部分数为 1。

2. 固定最高位

设 $p=2^k$ 是满足 $p\ge n$ 的最小二幂（即 $p=1\ll\lceil\log_2 n\rceil$）。 把所有数放进区间 $[p,\,p+n-1]\subseteq[p,\,2p-1]$ 中：

• 这 $n$ 个数的第 $k$ 位全为 1，因而该位贡献为 0；
• 更高位全为 0，贡献也为 0；
• 只有低于第 $k$ 位的部分会产生贡献，但这些数在 $[0,\,n-1]$ 的相对形态完全相同（与是否加上 $p$ 无关），等价于对 $0,1,\dots,n-1$ 的配对异或。

直观地看，这样做把所有数“聚在同一半区”，避免高位出现 0/1 混杂，从而使总代价最小。事实上，若把数分到两个半区，跨区的每一对都会额外贡献 $2^k$，显然更劣。

因此任选

即可达到最小值。示例：$n=3$ 时，$p=4$，输出 $4,5,6$。

3. 实现要点

• 线性输出即可；
• 先循环把 $p$ 扩到不小于 $n$ 的二幂；
• 所有数均为正，且最大值 $<3n$（因为 $p<n\cdot2$），安全无溢出。

复杂度分析

• 时间复杂度：$O(n)$，只需一次生成与打印。
• 空间复杂度：$O(1)$ 额外空间（除输出外）。

代码实现

Python

import sys

n = int(sys.stdin.readline().strip())

# 计算 p = 最小的 >= n 的二次幂
p = 1
while p < n:
    p <<= 1

# 输出 p, p+1, ..., p+n-1
ans = [str(p + i) for i in range(n)]
print(" ".join(ans))

Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();              // 读取 n
        int n = Integer.parseInt(line.trim());

        // 计算 p：最小的 >= n 的 2 的幂
        int p = 1;
        while (p < n) p <<= 1;

        // 依次输出 p, p+1, ..., p+n-1
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (i > 0) sb.append(' ');
            sb.append(p + i);
        }
        System.out.println(sb.toString());
    }
}

C++

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

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

    long long n;
    if (!(cin >> n)) return 0; // 忽略异常输入

    // 计算 p = 最小的 >= n 的二次幂
    long long p = 1;
    while (p < n) p <<= 1;

    // 输出 p, p+1, ..., p+n-1
    for (long long i = 0; i < n; ++i) {
        if (i) cout << ' ';
        cout << (p + i);
    }
    cout << '\n';
    return 0;
}

题目内容

给定一个正整数 $n$ 。请你构造一个长度为 $n$ 的数组 {$b_1,b_2,...,b_n$} 满足：

• 所有元素两两不同；

• 令目标函数为 $\sum _{1≤i≤j≤n}(b_i$ $xor$ $b_j)$ ，需要使该值尽可能小。

$xor$ 表示按位异或运算。上式的含义是把所有不同下标对的异或值相加。

输入描述

一行输入一个整数 $n (2 ≦n≦2× 10^5)$ 。

输出描述

输出 $n$ 个正整数，表示你构造出的数组元素。若有多种最优解，输出任意一种即可。要求每个 $b_i$ 满足 $1 ≦ b_i≦ 2^{31} - 1$ 。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确，注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

样例1

输入

3

输出

4 5 6

说明

对于 $b=${$4,5,6$}，三对异或分别为:$4$ $xor$ $5=1,4$ $xor$ $6=2,5$ $xor$ $6=3$ ,总和为 $1+2+3=6$ 。

样例2

输入

2

输出

6 7