POJ 3087 Shuffle'm Up：洗牌模擬與循環檢測

題目描述

兩疊各 C 張籌碼 S1、S2（底部到頂部給出）。洗牌規則：從底部開始交錯合併，先取 S2 底，再 S1 底，依此類推，形成 S12（2C 張）。然後將 S12 對半分：底部 C 張為新 S1，頂部 C 張為新 S2。重複操作。給定初始 S1、S2 及目標序列，求最少洗牌次數，或判定不可能（-1）。

解題思路：直接模擬 + 狀態循環檢測

1. 將兩疊合併為單一字符串 state = S1 + S2（長度 2C）。
2. 一次洗牌操作：按規則生成新 state。
3. 記錄初始狀態 orig。模擬洗牌，每次檢查是否等於目標。若回到 orig 仍未命中，說明進入循環，輸出 -1。
4. 最大狀態數有限（(2C)!/(C!C!)），C ≤ 100 但實際循環極短，直接模擬極快。

關鍵代碼：洗牌操作實現

string shuffle(const string& s, int C) {
    string t(2*C, ' ');
    int idx = 0;
    for (int i = 0; i < C; ++i) {
        t[idx++] = s[C + i]; // S2 第 i 個（從底部）
        t[idx++] = s[i];     // S1 第 i 個
    }
    // t 即為 S12，前 C 為新 S1，後 C 為新 S2
    return t;
}

// 主流程
string cur = s1 + s2, target;
int steps = 0;
do {
    if (cur == target) { cout << steps << endl; break; }
    cur = shuffle(cur, C);
    steps++;
} while (cur != s1 + s2 && steps <= 10000); // 理論上循環前會回到初始態
if (cur != target) cout << -1 << endl;

複雜度

• 時間：O(steps × C)，實際 steps 很小（通常 < 100）。
• 空間：O(C)。