UVa 131 The Psychic Poker Player：撲克牌型判斷與最優棄牌策略完整解析

問題描述

手牌 5 張，牌堆頂 5 張（已知順序）。可棄掉手中 0~5 張，從牌堆頂補同等張數。目標：最終 5 張牌牌型等級最高。輸出最佳牌型名稱。

撲克牌型等級（從高到低）

1. Straight Flush (同花順)
2. Four of a Kind (四條)
3. Full House (葫蘆)
4. Flush (同花)
5. Straight (順子)
6. Three of a Kind (三條)
7. Two Pairs (兩對)
8. One Pair (一對)
9. Highest Card (高牌)

解題核心思路

1. 枚舉所有棄牌組合：5 張手牌每張「留/棄」二選一，共 2⁵=32 種情況
2. 模擬補牌：按棄牌數量從牌堆頂取牌
3. 牌型判斷：對生成的 5 張牌進行排序、統計、判斷
4. 取最大等級：32 種情況中牌型等級最高者為答案

關鍵代碼片段

花色/點數編碼與排序

struct Card { char str[3]; } hand[10], deck[10], best[10];

// 點數映射：A=1, 2-9, T=10, J=11, Q=12, K=13
// 為便於比較，轉換為可排序字符：'1'..'9', ':', ';', '<', '='
void convert(Card *c) {
    switch (c->str[0]) {
        case 'A': c->str[0] = '1'; break;
        case 'T': c->str[0] = ':'; break;
        case 'J': c->str[0] = ';'; break;
        case 'Q': c->str[0] = '<'; break;
        case 'K': c->str[0] = '='; break;
    }
}

// 按點數排序
int cmp(const void *a, const void *b) {
    return ((Card*)a)->str[0] - ((Card*)b)->str[0];
}

遞歸枚舉所有棄牌組合

void dfs(int idx, int kept) {
    if (idx == 5) {  // 5 張手牌決策完畢
        // 從牌堆補齊 (5 - kept) 張
        for (int i = 0; i < 5 - kept; i++)
            best[kept + i] = deck[i];
        
        qsort(best, 5, sizeof(Card), cmp);
        int rank = judge_hand();
        max_rank = max(max_rank, rank);
        return;
    }
    
    // 選擇 1：保留手牌 idx
    best[kept] = hand[idx];
    convert(&best[kept]);
    dfs(idx + 1, kept + 1);
    
    // 選擇 2：棄掉手牌 idx
    dfs(idx + 1, kept);
}

牌型判斷邏輯

int judge_hand() {
    // 統計點數出現次數 num1[]、花色出現次數 num2[]
    // 同花順：連續 5 點數 + 同花色
    // 四條：任意點數出現 4 次
    // 葫蘆：3+2 分佈
    // 同花：花色出現 5 次
    // 順子：連續 5 點數（含 A-2-3-4-5 輪轉）
    // 三條：任意點數出現 3 次
    // 兩對：兩個點數各出現 2 次
    // 一對：任意點數出現 2 次
    // 高牌：以上皆非
}

難點與技巧

• A 既可作 1 也可作 14：順子判斷需處理 A-2-3-4-5 和 10-J-Q-K-A 兩種輪轉
• 字符編碼排序：將 T/J/Q/K/A 映射為 ':',';','<','=','1' 利用 ASCII 碼自然排序
• 32 種組合全枚舉：遞歸/位掩碼均可，數據量極小無性能壓力
• 輸出格式：嚴格按題目要求 "Hand: ... Deck: ... Best hand: ..."

複雜度分析

• 時間：O(32 × 5 log 5) ≈ O(1) 每測試用例
• 空間：O(1)