Welcome

首页 / 软件开发 / 数据结构与算法 / UVa 131 The Psychic Poker Player:枚举&模拟好题

UVa 131 The Psychic Poker Player:枚举&模拟好题2014-10-02 csdn博客 synapse7

131 - The Psychic Poker Player

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=107&page=show_problem&problem=67

In 5-card draw poker, a player is dealt a hand of five cards (which may be looked at). The player may then discard between zero and five of his or her cards and have them replaced by the same number of cards from the top of the deck (which is face down). The object is to maximize the value of the final hand. The different values of hands in poker are given at the end of this problem.

Normally the player cannot see the cards in the deck and so must use probability to decide which cards to discard. In this problem, we imagine that the poker player is psychic and knows which cards are on top of the deck. Write a program which advises the player which cards to discard so as to maximize the value of the resulting hand.

Input and Output

Input will consist of a series of lines, each containing the initial five cards in the hand then the first five cards on top of the deck. Each card is represented as a two-character code. The first character is the face-value (A=Ace, 2-9, T=10, J=Jack, Q=Queen, K=King) and the second character is the suit (C=Clubs, D=Diamonds, H=Hearts, S=Spades). Cards will be separated by single spaces. Each input line will be from a single valid deck, that is there will be no duplicate cards in each hand and deck.

Each line of input should produce one line of output, consisting of the initial hand, the top five cards on the deck, and the best value of hand that is possible. Input is terminated by end of file.

Use the sample input and output as a guide. Note that the order of the cards in the player"s hand is irrelevant, but the order of the cards in the deck is important because the discarded cards must be replaced from the top of the deck. Also note that examples of all types of hands appear in the sample output, with the hands shown in decreasing order of value.

Sample Input

TH JH QC QD QS QH KH AH 2S 6S2H 2S 3H 3S 3C 2D 3D 6C 9C TH2H 2S 3H 3S 3C 2D 9C 3D 6C TH2H AD 5H AC 7H AH 6H 9H 4H 3CAC 2D 9C 3S KD 5S 4D KS AS 4CKS AH 2H 3C 4H KC 2C TC 2D ASAH 2C 9S AD 3C QH KS JS JD KD6C 9C 8C 2D 7C 2H TC 4C 9S AH3D 5S 2H QD TD 6S KH 9H AD QH

Sample Output

Hand: TH JH QC QD QS Deck: QH KH AH 2S 6S Best hand: straight-flushHand: 2H 2S 3H 3S 3C Deck: 2D 3D 6C 9C TH Best hand: four-of-a-kindHand: 2H 2S 3H 3S 3C Deck: 2D 9C 3D 6C TH Best hand: full-houseHand: 2H AD 5H AC 7H Deck: AH 6H 9H 4H 3C Best hand: flushHand: AC 2D 9C 3S KD Deck: 5S 4D KS AS 4C Best hand: straightHand: KS AH 2H 3C 4H Deck: KC 2C TC 2D AS Best hand: three-of-a-kindHand: AH 2C 9S AD 3C Deck: QH KS JS JD KD Best hand: two-pairsHand: 6C 9C 8C 2D 7C Deck: 2H TC 4C 9S AH Best hand: one-pairHand: 3D 5S 2H QD TD Deck: 6S KH 9H AD QH Best hand: highest-card
学英语:

8 straight-flush 同花顺:一手同花的五张牌 + 五张牌点数连续的顺子7 four-of-a-kind  四张相同 的牌6 full-house 满堂红:三张同点牌加上一对(此时存在2张不同点的牌) 5 flush 一手同花的五张牌4 straight  顺子:五张牌点数连续的顺子3 three-of-a-kind    三张相同的牌2 two-pairs 两对对子(此时存在3张不同点的牌) 1 one-pair       一对对子 0 highest-card       上面的所有情况不符合

1. 用二进制枚举。

2. 按照题目样例的给出顺序判断换牌后手里牌的类型,先判断出来的优先。

3. 首先预处理:统计最大同点数,不同花数,不同点数。然后再判断。

注意:判断是否为顺子的时候,A可以放在第一位,也可以放在最后(即K的后面)。

完整代码:

/*0.019s*/#include<cstdio>#include<cstring>const int N = 20;const char answer[][20] ={"highest-card", "one-pair", "two-pairs", "three-of-a-kind", "straight","flush", "full-house", "four-of-a-kind", "straight-flush"};// 本文URL地址:http://www.bianceng.cn/Programming/sjjg/201410/45367.htmconst int bas_two[] = {16, 8, 4, 2, 1};struct Card{char name[5];int number,suit;} hand[N];char str[N];int A[N], B[N], C[N];int is_number(char c){if (c == "A") return 1;if (c == "T") return 10;if (c == "J") return 11;if (c == "Q") return 12;if (c == "K") return 13;return c & 15;}int is_suit(char c){if (c == "C") return 0;if (c == "D") return 1;if (c == "H") return 2;return 3; ///"S"}void handle(int cur, char str[]){strcpy(hand[cur].name, str);hand[cur].number = is_number(str[0]);hand[cur].suit = is_suit(str[1]);}bool maxLink_num(int num[])///顺子检测{bool flag;for (int i = 1; i < 10; i++){if (num[i] > 1) return false;if (num[i] == 1){flag = true;for (int j = 1; j < 5; j++){if (num[i + j] != 1){flag = false;break;}}if (flag) return true;}}if (num[10] == 1 && num[11] == 1 && num[12] == 1 && num[13] == 1 && num[1] == 1)return true;return false;}int judge(int cur){memset(A, 0, sizeof(A));memset(B, 0, sizeof(B));memset(C, 0, sizeof(C));for (int i = 0; i < 5; i++){if (cur / bas_two[i])B[i] = 0;elseB[i] = 1;cur %= bas_two[i];}int cnt = 0;for (int i = 0; cnt < 5; i++){if (!B[i]){A[hand[i].number]++;C[hand[i].suit]++;cnt++;}}/// Judge color and num;int max = 0,flag_color = 0, flag_num = 0;///最大同点数,不同花数,不同点数for (int i = 1; i < 14; i++){if (A[i] > max) max = A[i];if (A[i]) flag_num++;}for (int i = 0; i < 4; i++)if (C[i]) flag_color++;bool link = maxLink_num(A);///if (flag_color == 1 && link) return 8;///5同花且是顺子if (max == 4)return 7;///4同点if (max == 3 && flag_num == 2) return 6;///3同点加上一对(有2个不同点的牌)if (flag_color == 1) return 5;///5同花if (link)return 4;///顺子if (max == 3)return 3;///3同点if (max == 2 && flag_num == 3) return 2;///两对对子(有3个不同点的牌)if (max == 2)return 1;///一对对子return 0;}int main(){int max = 0, flag = 0;while (true){memset(hand, 0, sizeof(hand));max = flag = 0;for (int i = 0; i < 10; i++){if (scanf("%s", str) != 1){flag = 1;break;}handle(i, str);}if (flag) break;for (int i = 0; i < 32; i++)///枚举{flag = judge(i);if (flag > max) max = flag;}// Printprintf("Hand: ");for (int i = 0; i < 5; i++)printf("%s ", hand[i].name);printf("Deck: ");for (int i = 5; i < 10; i++)printf("%s ", hand[i].name);printf("Best hand: %s
", answer[max]);}return 0;}