Codeforces 264A Escape from Stones：DFS 模擬石子區間分割

題目大意

初始區間為 [0, 1]。依次進行 n 次操作，第 i 次操作在當前區間中點放入石子 i，然後根據給定的字符串指示（'l' 選左半段，'r' 選右半段）縮小區間。最終要求從左到右輸出所有石子的編號。

核心觀察

這是一個典型的二叉樹中序遍歷問題。每次在中點放石子相當於建立一個節點，'l' 代表先遍歷右子樹再訪問根節點（逆序），'r' 代表先訪問根節點再遍歷左子樹（正序）。最終的石子順序即為這棵隱式二叉樹的中序遍歷序列。

算法實現 (C++)

#include 
char s[1000005];

void dfs(int x) {
    if (s[x] == 0) return;
    if (s[x] == 'l') {
        dfs(x + 1);           // 先遞歸處理右子樹（對應區間右半段）
        printf("%d\n", x + 1); // 再輸出當前石子（根節點）
    } else { // 'r'
        printf("%d\n", x + 1); // 先輸出當前石子
        dfs(x + 1);           // 再遞歸處理左子樹
    }
}

int main() {
    scanf("%s", s);
    dfs(0);
    return 0;
}

原理圖解

以輸入 "lr" 為例：

• 石子 1 放在 [0,1] 中點 0.5，選 'l' 進入左區間 [0, 0.5]。
• 石子 2 放在 [0,0.5] 中點 0.25，選 'r' 進入右區間 [0.25, 0.5]。
• 對應樹結構：1 為根，2 為左孩子。'l' 表示左孩子在右邊（輸出序列中靠右），'r' 表示右孩子在左邊。
• 中序遍歷輸出：2, 1。

複雜度

• 時間：O(n)，每個字符處理一次。
• 空間：O(n) 遞歸棧深度（最壞情況字符串全為 'l' 或 'r'）。