2013
12-16

# The Psychic Poker Player

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 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.

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

Hand: TH JH QC QD QS Deck: QH KH AH 2S 6S Best hand: straight-flush
Hand: 2H 2S 3H 3S 3C Deck: 2D 3D 6C 9C TH Best hand: four-of-a-kind
Hand: 2H 2S 3H 3S 3C Deck: 2D 9C 3D 6C TH Best hand: full-house
Hand: 2H AD 5H AC 7H Deck: AH 6H 9H 4H 3C Best hand: flush
Hand: AC 2D 9C 3S KD Deck: 5S 4D KS AS 4C Best hand: straight
Hand: KS AH 2H 3C 4H Deck: KC 2C TC 2D AS Best hand: three-of-a-kind
Hand: AH 2C 9S AD 3C Deck: QH KS JS JD KD Best hand: two-pairs
Hand: 6C 9C 8C 2D 7C Deck: 2H TC 4C 9S AH Best hand: one-pair
Hand: 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. 首先预处理：统计最大同点数，不同花数，不同点数。然后再判断。

/*0.019s*/

#include<cstdio>
#include<cstring>
const int N = 20;
{
"highest-card", "one-pair", "two-pairs", "three-of-a-kind", "straight",
"flush", "full-house", "four-of-a-kind", "straight-flush"
};
const 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 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;
else
B[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++;
///
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 (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;
}
// Print
printf("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);
}
return 0;
}

1. 第一句可以忽略不计了吧。从第二句开始分析，说明这个花色下的所有牌都会在其它里面出现，那么还剩下♠️和♦️。第三句，可以排除2和7，因为在两种花色里有。现在是第四句，因为♠️还剩下多个，只有是♦️B才能知道答案。

2. #include <cstdio>
#include <algorithm>

struct LWPair{
int l,w;
};

int main() {
//freopen("input.txt","r",stdin);
const int MAXSIZE=5000, MAXVAL=10000;
LWPair sticks[MAXSIZE];
int store[MAXSIZE];
int ncase, nstick, length,width, tmp, time, i,j;
if(scanf("%d",&ncase)!=1) return -1;
while(ncase– && scanf("%d",&nstick)==1) {
for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
for(time=-1,i=0;i<nstick;++i) {
tmp=sticks .w;
for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
if(j==time) { store[++time]=tmp; }
else { store[j+1]=tmp; }
}
printf("%dn",time+1);
}
return 0;
}

3. 给你一组数据吧：29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的，耗时却不短。这种方法确实可以，当然或许还有其他的优化方案，但是优化只能针对某些数据，不太可能在所有情况下都能在可接受的时间内求解出答案。

4. L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-1]）这个地方也也有笔误
应改为L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-2]）