首页 > ACM题库 > HDU-杭电 > HDU 3759-Hands of Poker[解题报告]HOJ
2015
04-10

HDU 3759-Hands of Poker[解题报告]HOJ

Hands of Poker

问题描述 :

The standard 52-card deck consists of 52 cards divided into 4 suits: clubs, diamonds, hearts and spades.
For each suit there are 13 ranks: 2, 3, 4, 5, 6, 7, 8, 9, 10, jack, queen, king and ace, listed from the lowest to the highest.
A card is denoted by its rank (’2′. . . ’9′ for 2. . . 9, ‘T’ for 10, ‘J’ for jack, ‘Q’ for queen, ‘K’ for king, and ‘A’ for ace) followed by its suit (‘C’ for clubs, ‘D’ for diamonds, ‘H’ for hearts, and ‘S’ for spades). Cards are partially ordered by their ranks. The suit does not play a role in the cards ordering. A Poker hand is a set of five distinct cards. Each hand is said to have a certain ranking. A hand with a higher ranking beats a hand with a lower one. Two hands of the same ranking are compared using a tie-breaking rule specific for their ranking | either one of them beats the other or they are tied.
The list of poker rankings is given below, from the worst ranking to the best ranking. If a hand satisfies several rankings, only the best one is considered.

1)High Card | Does not fit into any ranking below. When comparing with another High Card hand, the ranks of the highest cards in the two hands are first compared. If there is a tie, the second highest cards in each hand are compared, and so on. (Example: QS, JH, 9C, 7H, 3D)
2)One Pair | Two cards of the same rank. Pair with higher rank beats the lower pair. In case of a tie, the remaining three cards are used as tie-breakers, compared in the descending order of their ranks (as in High Card). (Example: 6D, 6H, QD, 9H, 4S)
3)Two Pairs | Two pairs of cards of the same rank. When comparing with another Two Pairs hand, the higher pair is first compared, then the lower pair, and finally the rank of the fifth remaining card. (Example: JH, JS, TS, TD, 8S)
4)Three of a Kind | Three cards of the same rank. Three-of-a-kind with the higher rank beats the lower one. In case of a tie, the remaining two cards are used as tie-breakers, compared in the descending order. (Example: 5S, 5H, 5D, JH, 6D)
5)Straight | Five cards in consecutive rank. An ace can either be accounted above a king or below a two, but not both, so wrapping is not allowed. Two straights are compared using the rank of the highest card (in the case of A, 2, 3, 4, 5, the highest card is considered to be 5). (Example: QH,JC, TH, 9D, 8D)
6)Flush | Five cards of the same suit. When comparing two Flushes, the rank of the highest card is first considered, then the second highest and so on (as in High Card). (Example: AS, JS, 8S, 6S,5S)
7)Full House | Three cards of the same rank, and two cards of same rank. When comparing with another Full House, the rank of the three cards is first compared, then the rank of the two cards.(Example: 7S, 7H, 7C, JC, JH)
8) Four of a Kind | Four cards of the same rank. Two four-of-a-kinds are first compared by the ranks of the four cards. In case of a tie, the rank of the fifth card is used as a tie-breaker. (Example: 4C,4D, 4H, 4S, TD)
9)Straight Flush | A hand that is both a Straight and a Flush. Same tie-breaker as for a Straight. (Example: TH, 9H, 8H, 7H, 6H)

Consider the set H of all Poker hands. Let us introduce an evaluation function v : H -> {1 ,…, 7462}, such that for any two Poker hands a and b, a beats b if and only if v(a) > v(b). There exists exactly one such evaluation function v.
Given a Poker hand a, find the value of v(a).

输入:

The input begins with an integer T. The next T blocks each represents a case.
Each case contains space-separated list of five distinct card descriptions.
Each card is described with two characters denoting its rank and suit, respectively.
The ranks are denoted by `2′. . . `9′, `T’, `J’, `Q’,`K’, and `A’ (listed here in the ascending order). The suits are denoted by `C’, `D’, `H’, and `S’.

输出:

The input begins with an integer T. The next T blocks each represents a case.
Each case contains space-separated list of five distinct card descriptions.
Each card is described with two characters denoting its rank and suit, respectively.
The ranks are denoted by `2′. . . `9′, `T’, `J’, `Q’,`K’, and `A’ (listed here in the ascending order). The suits are denoted by `C’, `D’, `H’, and `S’.

样例输入:

2
3S 7S 2C 4S 5H
JH AH TH KH QH

样例输出:

1
7462

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std ;

int num[15] ;
int b[10] ;
int temp[10] , cnt = 0;
int p[10] ;
int N ;
int s[10] ;
int st[10] , ed[10] ;
char str[10][3] ;

// 1 A B C D E
// 2 A B C D D
// 3 A B B C C
// 4 A B C C C
// 5 A A+1 A+2 A+3 A+4
// 6 A A A B B
// 7 A A A A B

struct card{
 int a[5] , R;

 void insert(int list[]){
 for (int i = 0 ; i < 5 ; i++)
 b[i] = list[i] ;
 memset(num,0,sizeof(num));
 for (int i = 0 ; i < 5 ; i++)
 num[b[i]]++ ;

 // ˳�� ���� 5������
 bool flag = 0 ;
 for (int i = 0 ; i < 5 ; i++){
 if (num[b[i]]>1){
 flag=1;
 break ;
 }
 }
 if (flag==0){
 sort(b,b+5) ;
 for (int i = 0 ; i < 5 ; i++) a[i] = b[i] ;
 if (b[0]==2&&b[1]==3)
 if (b[2]==4&&b[3]==5)
 if (b[4]==14){
 b[4] = 1 ;
 sort(b,b+5);
 for (int i = 0 ; i < 5 ; i++)
 a[i] = b[i] ;
 R = 5;
 return ;
 }
 if (b[0]==b[2]-2 && b[1]==b[2]-1)
 if (b[3]==b[2]+1 && b[4]==b[2]+2)
 {
 R = 5 ;
 return ;
 }

 R = 1 ;
 return ;
 }
 int sum2 = 0 , sum3 = 0 , sum4 = 0 ;
 for (int i = 2 ; i < 15 ; i++){
 if (num[i]==2) sum2++ ;
 if (num[i]==3) sum3++ ;
 if (num[i]==4) sum4++ ;
 }
 // 4����ͬ
 if (sum4==1){
 int pos ;
 for (int i = 0 ; i < 5 ; i++)
 if (num[b[i]] != 4)
 pos = i ;
 a[0] = b[pos] ;
 R = 7 ;
 if (pos != 0){
 for (int i = 1 ; i < 5 ; i++)
 a[i] = b[0] ;
 return ;
 }
 if (pos != 1){
 for (int i = 1 ; i < 5 ; i++)
 a[i] = b[1];
 return ;
 }
 }
 // 3�� �� 2��
 if (sum2 == 1 && sum3 == 1){
 R = 6 ;
 for (int i = 0 ; i < 5 ; i++){
 if (num[b[i]] == 3){
 for (int j = 2 ; j < 5 ; j++)
 a[j] = b[i] ;
 }else
 {
 for (int j = 0 ; j < 2 ; j++)
 a[j] = b[i] ;
 }
 }
 return ;
 }
 // 3��
 if (sum3 == 1){
 cnt = 0 ; int pos = -1 ;
 for (int i = 0 ; i < 5; i++)
 if (num[b[i]] != 3)
 temp[cnt++] = b[i] ;
 else
 pos = i ;
 for (int i = 2 ; i < 5; i++)
 a[i] = b[pos] ;
 sort(temp,temp+2);
 for (int i = 0 ; i < 2 ; i++)
 a[i] = temp[i] ;
 R = 4 ;
 return ;
 }
 // 2��
 if (sum2 == 1){
 cnt = 0 ; int pos = -1 ;
 for (int i = 0 ; i < 5; i++)
 if (num[b[i]] != 2)
 temp[cnt++] = b[i] ;
 else
 pos = i ;
 for (int i = 3 ; i < 5; i++)
 a[i] = b[pos] ;
 sort(temp,temp+3);
 for (int i = 0 ; i < 3 ; i++)
 a[i] = temp[i] ;
 R = 2 ;
 return ;
 }
 // 2��2��
 R = 3 ;
 cnt = 0 ; int pos = -1 ;
 for (int i = 0 ; i < 5 ; i++)
 if (num[b[i]] != 1)
 temp[cnt++] = b[i] ;
 else
 pos = i ;
 a[0] = b[pos] ;
 sort(temp,temp+4);
 for (int i = 1 ; i < 5 ; i++)
 a[i] = temp[i-1];

 }
}state[15*15*15*15*15] ;

void check(){
 if (p[0]==p[1] && p[0]==p[2])
 if (p[0]==p[3] && p[0]==p[4])
 return ;
 state[++N].insert(p) ;
}

void dfs(int i){
 if (i > 4){
 check() ;
 return ;
 }
 for (int j = 2 ; j < 15 ; j++)
 {
 p[i] = j ;
 dfs(i+1) ;

 }
}

int get(char c){
 if (c>='0' && c<='9') return c - '0' ;
 if (c=='T') return 10 ;
 if (c=='J') return 11 ;
 if (c=='Q') return 12 ;
 if (c=='K') return 13 ;
 if (c=='A') return 14 ;
}

int Cmp(card &A , card &B){
 if (A.R < B.R) return -1 ;
 if (A.R > B.R) return 1 ;
 for (int i = 4 ; i >= 0 ; i--){
 if (A.a[i] < B.a[i])
 return -1 ;
 if (A.a[i] > B.a[i])
 return 1 ;
 }
 return 0 ;
}
bool cmp(const card &A , const card &B){
 if (A.R != B.R) return A.R < B.R ;
 for (int i = 4 ; i > 0 ; i--)
 if (A.a[i] != B.a[i])
 return A.a[i] < B.a[i];
 return A.a[0] < B.a[0] ;
}
int search(int L,int R,card A){
 int ret ;
 while (L<=R){
 int mid = (L+R)>>1 ;
 if (Cmp(state[mid],A)>=0){
 R = mid - 1 ;
 ret = mid ;
 }else
 L = mid + 1 ;
 }
 return ret ;
}

int main(){
 N = 0 ;
 dfs(0) ;
 sort(state+1,state+N+1,cmp);
 int cnt = 1 ;
 for (int i = 2 ; i <= N ; i++){
 if (Cmp(state[i],state[i-1])==0) continue ;
 state[++cnt] = state[i] ;
 }
 N = cnt ; memset(s,0,sizeof(s));
 memset(st,0,sizeof(st));

 for (int i = 1 ; i <= N ; i++){
 s[state[i].R]++ ;
 if (st[state[i].R]==0) st[state[i].R]=i ;
 ed[state[i].R] = i ;
 }

 int Q ;
 scanf("%d",&Q) ;
 int sum[10];
 sum[0] = 0 ;
 for (int i = 1 ; i <= 5 ; i++)
 sum[i] = sum[i-1] + s[i] ;
 while (Q--){
 for (int j = 0 ; j < 5 ; j++)
 scanf("%s",str[j]);
 card now ;
 for (int j = 0 ; j < 5 ; j++)
 b[j] = get(str[j][0]);
 now.insert(b);
 bool samesuit = true ;
 for (int j = 1 ; j < 5 ; j++)
 if (str[j][1] != str[0][1]) samesuit = false ;
 int rank = now.R ;
 int pos = search(st[rank],ed[rank],now) - st[rank] + 1;
 int Tonghua = s[1] ;

 if (!samesuit){
 if (rank <= 5){
 printf("%d\n",sum[rank-1] + pos) ;
 }
 else{
 if (rank == 6)
 printf("%d\n",sum[5] + Tonghua + pos);
 else
 printf("%d\n",sum[5] + Tonghua + s[6] + pos) ;
 }
 }else
 {
 if (rank == 5){
 printf("%d\n",sum[5] + Tonghua + s[6] + s[7] + pos) ;
 }
 else
 printf("%d\n",sum[5] + pos);

 }
 }
 /*cout << s[1] << endl ;
 cout << s[2] << endl ;
 cout << s[3] << endl ;
 cout << s[4] << endl ;
 cout << s[5] << endl ;
 cout << s[6] << endl ;
 cout << s[7] << endl ;
 cout << 2*s[1]+s[2]+s[3]+s[4]+s[5]+s[6]+s[7]+10<<endl;*/
 return 0;
}

  1. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count

  2. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥