题目描述回顾

我们有一个多人纸牌游戏“Hit or Miss”，规则如下：

1. 使用一副标准的52张牌（数字1-13，每种数字4张，花色不影响）。
2. 玩家按顺序数数（1,2,...,13循环），检查牌堆顶的牌：
   • 匹配：移除牌并传给下一个玩家（最后一个玩家直接丢弃）
   • 不匹配：将牌移到底部
3. 所有玩家同步执行：
   • 阶段1：计数和匹配
   • 阶段2：传递牌（收到的牌放到底部）
4. 胜利条件：所有牌被最后一个玩家丢弃
5. 失败条件：进入无限循环

解题思路

1. 数据结构选择：

   • 使用队列表示每个玩家的牌堆
   • 数组记录每个玩家的当前计数值

2. 游戏流程模拟：

   • 初始化各玩家的牌堆和计数
   • 循环执行两个阶段，直到游戏结束或检测到循环

3. 终止条件判断：

   • 胜利：最后一个玩家的丢弃牌数=52
   • 失败：检测到重复状态（玩家牌堆和计数相同）

4. 优化措施：

   • 设置最大循环次数防止无限运行
   • 记录最后丢弃的牌

代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>

using namespace std;

struct GameState {
    vector<vector<int> > playerDecks;  // Fixed: space between '>' for older C++
    vector<int> nextCounts;
    
    bool operator<(const GameState& other) const {
        if (nextCounts != other.nextCounts)
            return nextCounts < other.nextCounts;
        return playerDecks < other.playerDecks;
    }
};

int main() {
    int n;
    cin >> n;
    for (int caseNum = 1; caseNum <= n; ++caseNum) {
        int playerCount;
        cin >> playerCount;
        vector<int> initialDeck(52);
        for (int i = 0; i < 52; ++i)
            cin >> initialDeck[i];
        
        vector<queue<int> > players(playerCount);  // Fixed: space between '>' for older C++
        for (size_t i = 0; i < initialDeck.size(); ++i)  // Replaced range-based for loop
            players[0].push(initialDeck[i]);
        
        vector<int> nextCount(playerCount, 1);
        vector<int> lastDiscarded(playerCount, -1);
        int totalDiscarded = 0;
        set<GameState> seenStates;
        bool winnable = false;
        
        while (true) {
            GameState currentState;
            currentState.nextCounts = nextCount;
            currentState.playerDecks.resize(playerCount);
            for (int i = 0; i < playerCount; ++i) {
                queue<int> q = players[i];
                vector<int>& deck = currentState.playerDecks[i];
                while (!q.empty()) {
                    deck.push_back(q.front());
                    q.pop();
                }
            }
            
            if (seenStates.find(currentState) != seenStates.end()) {
                break;
            }
            seenStates.insert(currentState);
            
            vector<int> passedCards(playerCount, -1);
            bool anyAction = false;
            
            for (int i = 0; i < playerCount; ++i) {
                if (!players[i].empty()) {
                    anyAction = true;
                    int currentNum = nextCount[i];
                    int card = players[i].front();
                    players[i].pop();
                    
                    if (card == currentNum) {
                        lastDiscarded[i] = card;
                        if (i == playerCount - 1) {
                            totalDiscarded++;
                        } else {
                            passedCards[i + 1] = card;
                        }
                        nextCount[i] = (currentNum % 13) + 1;
                    } else {
                        players[i].push(card);
                        nextCount[i] = (currentNum % 13) + 1;
                    }
                }
            }
            
            for (int i = 1; i < playerCount; ++i) {
                if (passedCards[i] != -1) {
                    players[i].push(passedCards[i]);
                }
            }
            
            if (totalDiscarded == 52) {
                winnable = true;
                break;
            }
            
            bool allEmpty = true;
            for (size_t i = 0; i < players.size(); ++i) {  // Replaced range-based for loop
                if (!players[i].empty()) {
                    allEmpty = false;
                    break;
                }
            }
            if (allEmpty) {
                break;
            }
            
            if (!anyAction) {
                break;
            }
        }
        
        cout << "Case " << caseNum << ": ";
        if (winnable) {
            for (int i = 0; i < playerCount; ++i) {
                if (i > 0) cout << " ";
                cout << lastDiscarded[i];
            }
            cout << endl;
        } else {
            cout << "unwinnable" << endl;
        }
    }
    
    return 0;
}

复杂度分析

• 时间复杂度：O(N×P×52)，其中N是最大迭代次数
• 空间复杂度：O(P×52)存储牌堆状态

注意事项

1. 游戏状态需要包括牌堆和当前计数
2. 必须严格按阶段顺序执行操作
3. 注意处理玩家牌堆为空的情况
4. 合理设置最大迭代次数防止超时

这个解法通过模拟游戏过程并检测重复状态来判断是否可解，能够正确处理题目描述中的所有情况。