題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 CF2173E. Shiro’s Mirror Duel

Problem Statement

這是一道互動題。

題目簡述

給定一個長度為 $n$ 的排列 $P_1, P_2, \ldots, P_n$ 。你需要將其排序為 $1, 2, \ldots, n$ 。

你可以進行操作：選擇兩個索引 $x, y$ ( $1 \le x, y \le n, x \neq y$ )。

系統會投擲一枚硬幣：

$50\%$ 機率交換 $p_x, p_y$ 。
$50\%$ 機率交換 $p_{n-x+1}, p_{n-y+1}$ （即 $x, y$ 的鏡像位置）。

操作後，系統會告知實際上交換的是哪兩個索引。
目標是在 $\lfloor 2.5n + 800 \rfloor$ 次操作內完成排序。

Constraints

約束條件

$1 \le n \le 4000$
$\sum n \le 2 \cdot 10^4$

思路

這是一道構造演算法題目，結合了互動與機率期望值的概念。
核心難點在於操作具有隨機性：選擇 $(x, y)$ 進行交換時，有 50% 機率交換 $(x, y)$ ，50% 機率交換其鏡像位置 $(n-x+1, n-y+1)$ 。

我們的目標是在 $2.5n$ 次操作內完成排序。
從這個限制不難推測出，我們需要將陣列分為 $\frac{n}{2}$ 對鏡像位置 $(i, n-i+1)$ ，逐對解決，且解決每一對的期望操作次數需要為 $5$ 次。

對於每一對 $(l, r)$ ：

寬鬆限制 (Loose Constraint)：首先嘗試歸位 $l$ 。此時我們不在乎 $r$ 是否被破壞（或者 $r$ 本來就還沒排好）。這是一個簡單的幾何分佈，期望需 2 次 操作。
嚴格限制 (Strict Constraint)：當 $l$ 歸位後，我們嘗試歸位 $r$ 。此時必須保證 $l$ 不被破壞（如果隨機到了鏡像交換導致 $l$ 錯位，必須修復）。這種情況下的期望需 3 次 操作。

總計每一對需要 $2+3=5$ 次操作，平均每個元素 $2.5$ 次。

嚴格限制下的期望值計算

我們定義狀態 $(S_A, S_B)$ ，其中 $0$ 代表已歸位， $1$ 代表錯位。

嚴格限制情境：假設 $A$ 已歸位，但 $B$ 需要歸位，初始狀態為 $(0, 1)$ 。
我們對 $B$ 進行操作：

$50\%$ 機率成功： $B$ 歸位，狀態變為 $(0, 0)$ 。此步花費 $1$ 。
$50\%$ 機率失敗（鏡像交換）： $A$ 被破壞，狀態變為 $(1, 1)$ 。此步花費 $1$ 。

雙重錯位情境：在狀態 $(1, 1)$ 時，我們操作任一邊（例如 $A$ ）：

$50\%$ 機率 $A$ 歸位，狀態變為 $(0, 1)$ 。
$50\%$ 機率 $B$ 歸位，狀態變為 $(1, 0)$ （對稱於 $(0, 1)$ ）。

令 $E_{01}$ 為從 $(0,1)$ 到完成的期望步數， $E_{11}$ 為從 $(1,1)$ 到完成的期望步數。
列出方程式：

$E_{01} = 1 + 0.5(0) + 0.5(E_{11}) = 1 + 0.5 E_{11}$
$E_{11} = 1 + 0.5(E_{01}) + 0.5(E_{10}) = 1 + E_{01}$ （利用對稱性 $E_{01}=E_{10}$ ）

將 (2) 代入 (1)：
$E_{01} = 1 + 0.5(1 + E_{01}) = 1.5 + 0.5 E_{01}$
$0.5 E_{01} = 1.5 \implies E_{01} = 3$

故嚴格限制下的期望次數為 3。

演算法策略

我們將陣列由外向內分為 $n/2$ 層。對於每一層 $(l, r)$ ：

優先嘗試將 $l$ 歸位（花費 2 次）。
當 $l$ 歸位後，嘗試將 $r$ 歸位。
如果在嘗試歸位 $r$ 的過程中意外破壞了 $l$ ，則退回第 1 步。

這樣每一對的期望花費是 5 次。總共有 $n/2$ 對，總期望次數為：

\text{Total Ops} = \frac{n}{2} \times 5 = 2.5n

這正好符合題目限制 $\lfloor 2.5n + 800 \rfloor$ 。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ (期望操作次數 $2.5n$ )
空間複雜度： $\mathcal{O}(n)$ (儲存排列與位置映射)

Code

def solve():
    n = int(input())
    A = [0] + list(map(int, input().split()))

    pos = [-1] * (n + 1)
    for i, x in enumerate(A):
        pos[x] = i

    def query(x, y):
        print(f"? {x} {y}", flush=True)
        u, v = map(int, input().split())
        A[u], A[v] = A[v], A[u]
        pos[A[u]], pos[A[v]] = u, v

    for l in range(1, n // 2 + 1):
        r = n + 1 - l
        while pos[l] != l or pos[r] != r:
            if pos[l] != l:
                query(pos[l], l) # 優先修復左邊 (Loose Constraint)
            else:
                query(pos[r], r) # 左邊好了，嘗試修復右邊 (Strict Constraint)
    print('!', flush=True)

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

寫在最後

PROMPT

這裡什麼都沒有。