首页 > 代码库 > UVa 131 - The Psychic Poker Player

UVa 131 - The Psychic Poker Player

题目:手里有五张牌,桌上有一堆牌(五张),你可以弃掉手中的k张牌,然后从牌堆中取最上面的k个。

            比较规则如下:(按优先级排序)

            1.straight-flush:同花顺,牌面为T(10) - A,这里不论花色是否相同;

            2.four-of-a-kind:四条,牌面有4个相同的值;

            3.full-house:船牌,牌面有3个相同值,剩下2个也相同值;

            4.flush:同花,五张牌的花色相同,不是同花顺;

            5.straight:顺子,五张牌的值连续,A可以作为1也可以作为14;

            6.three-of-a-kind:三条,牌面有3个相同的值;

            7.two-pairs:两对,牌面有2个对子;

            8.one-pair:一对,牌面有一个对子,即2个同值;

            9.highest-card:大牌,没有以上牌型。

分析:搜索、枚举。枚举换牌数从0-5的每种情况,判断,取出优先值最高的即可。

说明:读题是重点。

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>

#define min(x,y) ((x)<(y)?(x):(y))

using namespace std;

char temp[5][3];
char card[10][3];
int  maps[5][13];

char output[11][20] = {
	"","straight-flush","four-of-a-kind",
	"full-house","flush","straight","three-of-a-kind",
	"two-pairs","one-pair","highest-card",""};

int  value( char ch )
{
	if ( ch == 'T' ) return 9;
	if ( ch == 'J' ) return 10;
	if ( ch == 'Q' ) return 11;
	if ( ch == 'K' ) return 12;
	if ( ch == 'A' ) return 0;
	return ch - '1';
}

int  color( char ch )
{
	if ( ch == 'S' ) return 0;
	if ( ch == 'H' ) return 1;
	if ( ch == 'D' ) return 2;
	if ( ch == 'C' ) return 3;
}

int  tests()
{
	//royal-flush | straight-flush
	for ( int i = 0 ; i < 5 ; ++ i )
		if ( maps[i][0]&maps[i][9]&maps[i][10]&maps[i][11]&maps[i][12] )
			return 1;
	//four-of-a-kind
	for ( int i = 0 ; i < 13 ; ++ i )
		if ( maps[4][i] == 4 ) return 2;
	//full-house
	int three = 0,two = 0;
	for ( int i = 0 ; i < 13 ; ++ i ) {
		if ( maps[4][i] == 2 ) two ++;
		if ( maps[4][i] == 3 ) three ++;
	}
	if ( two && three ) return 3;
	//flush
	for ( int i = 0 ; i < 4 ; ++ i ) {
		int count = 0;
		for ( int j = 0 ; j < 13 ; ++ j )
			count += maps[i][j];
		if ( count >= 5 ) return 4;
	}
	//straight
	for ( int i = 0 ; i < 10 ; ++ i )
		if ( maps[4][i]&maps[4][i+1]&maps[4][i+2]&maps[4][i+3]&maps[4][(i+4)%13] )
			return 5;
	//three-of-a-kind
	if ( three ) return 6;
	//two-pairs
	if ( two > 1 ) return 7;
	//one-pair
	if ( two ) return 8;
	return 9;
}

void change()
{
	for ( int i = 0 ; i < 5 ; ++ i ) 
		strcpy(temp[i],card[i+5]);
	memset( maps, 0, sizeof(maps) );
	for ( int i = 0 ; i < 5 ; ++ i ) {
		maps[color(temp[i][1])][value(temp[i][0])] = 1;
		maps[4][value(temp[i][0])] ++;
	}
	int Min = tests();
	
	for ( int k = 1 ; k <= 5 ; ++ k ) {  
    	int xx,yy,comb = (1<<k)-1;
        while ( comb < 32 ) {    
            // 计算当前状态对应的集合     
            int j = 0,count = 0,move = 5;
            do {    
                if ( (1<<j)&comb )
					strcpy(temp[count ++],card[j]);
                j ++;
            }while ( j < 5 );
            
            while ( count < 5 ) 
				strcpy(temp[count ++],card[move ++]);
			
			memset( maps, 0, sizeof(maps) );
			for ( int i = 0 ; i < 5 ; ++ i ) {
				maps[color(temp[i][1])][value(temp[i][0])] = 1;
				maps[4][value(temp[i][0])] ++;
			}
			
			Min = min(Min,tests());
            // 位运算计算下一组合  
            xx = comb&-comb,yy = comb+xx;
            comb = ((comb&~yy)/xx>>1)|yy;
        }
    }
    printf("%s\n",output[Min]);
}

int main()
{
	while ( ~scanf("%s",card[0]) ) {
		for ( int i = 1 ; i < 10 ; ++ i )
			scanf("%s",card[i]);
		
		printf("Hand: ");
		for ( int i = 0 ; i < 5 ; ++ i )
			printf("%s ",card[i]);
		printf("Deck: ");
		for ( int i = 5 ; i < 10 ; ++ i )
			printf("%s ",card[i]);
		printf("Best hand: ");
		change();
	}
	return 0;
}