🔗 CF2179D Blackslex and Penguin Civilization

rating: 1343

Problem Statement

題目簡述

給定 $n$ ，求一個 $0$ 到 $2^n - 1$ 的排列 $p$ ，首先使得 $S(p) = \sum_{i=0}^{2^n-1} \operatorname{popcount}(p_0 \mathbin{\&} \cdots \mathbin{\&} p_i)$ 最大，其次要求該排列的字典序最小。

Constraints

約束條件

$1 \le t \le 16$
$1 \le n \le 16$
$\sum 2^n \le 2^{16}$

思路：貪心構造

這道題有兩個目標：

最大化 $S(p)$ ：
$\text{popcount}(z)$ 是 $z$ 的二進位表示中 $1$ 的個數。 $S(p)$ 是所有前綴 AND 值的 popcount 總和。
前綴 AND 的值只會隨著序列長度增加而減少（或不變）。要最大化總和，我們希望前綴 AND 的每一位 $1$ 能維持越久越好。
對於 $n$ 個位元中的任意一位 $j$ ，在排列中最多只有 $2^{n-1}$ 個數的第 $j$ 位是 $1$ 。因此，第 $j$ 位為 $1$ 的前綴長度上限是 $2^{n-1}$ 。
顯然，我們可以構造出一種排列，使得不同位元的「生存時間」分別為 $1, 2, 2^1, \dots, 2^{n-1}$ 。其總和是固定的。
字典序最小：
為了讓排列的字典序最小，我們希望數值越小的元素越早出現。
數值小意味著高位元是 $0$ 。
因此，我們應該儘早放棄高位元的限制（讓高位元在前綴 AND 中變為 0），並盡可能保留低位元為 $1$ 。
這意味著我們應該優先輸出低位元全為 $1$ 的數。

具體構造策略

我們可以根據數字二進位表示中尾部連續 $1$ 的數量（Trailing Ones）將所有數字分組，依序處理 $k = n, n-1, \dots, 0$ ：

具 $n$ 個連續 1 ( $k=n$ )：即 $2^n-1$ 。這是唯一的，必須放在最前面。
具 $k$ 個連續 1 ( $0 \le k < n$ $0 \leq k < n$ )：這些數字需滿足：
- 低 $k$ 位元全為 1：確保加入這些數後，前綴 AND 最少還有 $k$ 個 1。
- 第 $k+1$ 位元為 0：區分屬於更低階的群組（否則若第 $k+1$ 位為 1，則應屬於 $k+1$ 群組）。

對於每個 $k$ （從 $n-1$ 遞減至 $0$ ），該分組中最小的數為 $2^k - 1$ （低 $k$ 位為 1，第 $k+1$ 位為 0，高位全 0）。
後續符合條件的數字可以通過不斷加上 $2^{k + 1}$ （即跳過第 $k+1$ 位，只動高位）來生成。
這形成了一個首項為 $2^k - 1$ 、公差為 $2^{k + 1}$ 、且末項 $< 2^{n} - 1$ 的等差數列：range((1 << k) - 1, (1 << n) - 1, (1 << (k + 1)))。
此順序自然滿足字典序最小的要求。

範例

n=4, U=15

$U=15$ 先加入。
$k=3$ : 起始 0111 ( $7$ $7$ ), 公差 10000 ( $16$ $16$ )。
- $\to 7$ 。
$k=2$ : 起始 0011 ( $3$ $3$ ), 公差 1000 ( $8$ $8$ )。
- $\to 3, 11$ 。
$k=1$ : 起始 0001 ( $1$ $1$ ), 公差 0100 ( $4$ $4$ )。
- $\to 1, 5, 9, 13$ 。
$k=0$ : 起始 0000 ( $0$ $0$ ), 公差 0010 ( $2$ $2$ )。
- $\to 0, 2, 4, 6, 8, 10, 12, 14$ 。

注意：初始時會先將 $U=15$ 加入答案。
最終排列：15, 7, 3, 11, 1, 5, 9, 13, 0, 2, 4, 6, 8, 10, 12, 14。

複雜度分析

時間複雜度： $\mathcal{O}(2^n)$ ，每個數字只被訪問並輸出一次。
空間複雜度： $\mathcal{O}(2^n)$ 用於存儲排列。

Code

def solve():
    n = int(input())
    
    U = (1 << n) - 1
    ans = [U]
    for k in range(n - 1, -1, -1):
        ans.extend(range((1 << k) - 1, U, (1 << (k + 1))))
    print(*ans)

if __name__ == "__main__":
    t = int(input())
    for _ in range(t):
        solve()

寫在最後

PROMPT

這裡什麼都沒有。