士兵與卡牌遊戲（Codeforces 540B / War 模擬）：隊列模擬、循環檢測、複雜度分析與 C++ 實現

士兵與卡牌遊戲（Codeforces 540B / War 模擬）：隊列模擬、循環檢測、複雜度分析與 C++ 實現

兩名士兵用 n 張牌（1..n，無重複）玩「戰爭」遊戲：每輪各出頂牌，大牌勝，將兩張牌按「先對手牌、再自己牌」順序置於自己牌堆底。一方牌盡則輸。n ≤ 10，狀態空間極小，直接模擬並檢測循環即可。

一、遊戲規則形式化

• 狀態：兩個隊列 q1, q2，元素為卡牌值（1..n）。
• 轉移：x = q1.pop(), y = q2.pop()；若 x > y 則 q1.push(y), q1.push(x)，否則 q2.push(x), q2.push(y)。
• 終止：某隊列為空 → 另一方勝；狀態重複 → 無限循環，輸出 -1。

二、循環檢測策略

n ≤ 10，總排列數 n! ≤ 3,628,800，但實際可達狀態遠少。兩種檢測方法：

1. 步數上限法：設置最大步數（如 100,000 或 1e6），超過判定循環。最簡單，足夠通過。
2. 狀態集合法：用 set 記錄 q1序列 + "|" + q2序列，遇到重複即循環。嚴格正確，額外 O(step * n log n) 開銷。

三、C++ 完整實現（步數上限法，AC 代碼）

#include 
using namespace std;

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

    int n;
    if (!(cin >> n)) return 0;
    queue q1, q2;
    int k1, x;
    cin >> k1;
    for (int i = 0; i < k1; ++i) { cin >> x; q1.push(x); }
    int k2; cin >> k2;
    for (int i = 0; i < k2; ++i) { cin >> x; q2.push(x); }

    const int MAX_STEPS = 1000000; // 經驗值，n=10 實際循環週期極短
    int steps = 0;
    while (!q1.empty() && !q2.empty() && steps < MAX_STEPS) {
        int x = q1.front(); q1.pop();
        int y = q2.front(); q2.pop();
        ++steps;
        if (x > y) {
            q1.push(y);
            q1.push(x);
        } else {
            q2.push(x);
            q2.push(y);
        }
    }

    if (q1.empty()) {
        cout << steps << " 2\n"; // 玩家 2 勝
    } else if (q2.empty()) {
        cout << steps << " 1\n"; // 玩家 1 勝
    } else {
        cout << -1 << "\n"; // 循環
    }
    return 0;
}

四、複雜度分析

五、狀態集合法實現（嚴格正確版）

// 替換 while 條件部分
set seen;
auto encode = [&](queue a, queue b) {
    string s;
    while (!a.empty()) { s += to_string(a.front()); a.pop(); s += ','; }
    s += '|';
    while (!b.empty()) { s += to_string(b.front()); b.pop(); s += ','; }
    return s;
};

while (!q1.empty() && !q2.empty()) {
    string state = encode(q1, q2);
    if (seen.count(state)) { cout << -1 << "\n"; return 0; }
    seen.insert(state);
    // ... 同前模擬步驟
}

六、測試用例