首页 > ACM题库 > HDU-杭电 > HDU 4032-Fight the Landlord[解题报告]HOJ
2015
04-15

HDU 4032-Fight the Landlord[解题报告]HOJ

Fight the Landlord

问题描述 :

Fight the Landlord (斗地主) is a card game for three players. In each hand one player, the "landlord", plays alone and the others form a team(may called two peasants). The landlord’s aim is to be the first to play out all his cards in valid combinations, and the team wins if any one of them manages to play all their cards before the landlord.

A complete deck consists of 52 standard cards plus 2 jokers, red and black. The cards rank from high to low: R(Red Joker), B(Black joker), 2, A, K, Q, J, T(10), 9, 8, 7, 6, 5, 4, 3. Each rank of standard card has 4 cards.

The landlord plays first, and may play a single card or any legal combination. Each subsequent player in anticlockwise order must either pass (play no card) or beat the previous play by playing a higher combination of the same number of cards and same type. There are just two exceptions to this: a rocket can beat any combination, and a bomb can beat any combination except a higher bomb or rocket – see definitions below.

In this game, there are thirteen types of combination that can be played:

1.  Single card - ranking from 3 (low) up to red joker (high) as explained above.
2.  Pair – two cards of the same rank, from 3 (low) up to 2 (high), for example 3-3, A-A.
3.  Triplet – three cards of the same rank, for example 9-9-9.
4.  Triplet with an attached card – a triplet with a single card added, the single card must be different from the triplet, for example 6-6-6-8. These rank according to the rank of the triplet – so for example 9-9-9-3 beats 8-8-8-A.
5.  Triplet with an attached pair – a triplet with a pair added, the ranking being determined by the rank of the triplet – for example Q-Q-Q-6-6 beats 10-10-10-K-K.
6.  Sequence – at least five cards of consecutive rank, from 3 up to ace – for example 8-9-10-J-Q. 2 and jokers cannot be used.
7.  Sequence of pairs - at least three pairs of consecutive ranks, from 3 up to A. 2 and jokers cannot be used. For example 10-10-J-J-Q-Q-K-K.
8.  Sequence of triplets - at least two triplets of consecutive ranks from 3 up to A. 2 cannot be used. For example 4-4-4-5-5-5.
9.  Sequence of triplets with attached cards – an extra card is added to each triplet. Only the triplets have to be in sequence, for example 7-7-7-8-8-8-3-6. The attached cards must be different from all the triplets and from each other. Although triplets of 2 cannot be included in the triplets sequence, a 2 or a joker or one of each can be attached, but not both jokers.
10.  Sequence of triplets with attached pairs – an extra pair is attached to each triplet. Only the triplets have to be in sequence – for example 8-8-8-9-9-9-4-4-J-J. The pairs must be different in rank from each other and from all the triplets. Although triplets of 2 cannot be included in the triplets sequence, a pair of 2 can be attached. Note that attached single cards and attached pairs cannot be mixed – for example 3-3-3-4-4-4-6-7-7 is not valid.
11.  Bomb – four cards of the same rank. A bomb can beat everything except a rocket or a bomb with higher rank.
12.  Rocket – a pair of jokers. It is the highest combination and beats anything else, including bombs.
13.  Quadplex set – there are two types: a quad (four cards of the same rank) with two single cards of different ranks attached, such as 6-6-6-6-8-9, or a quad with two pairs of different ranks attached, such as J-J-J-J-9-9-Q-Q. 2 and jokers can be attached, but you cannot use both jokers in one quadplex set. Quadplex sets are ranked according to the rank of the quad. Note that a quadplex set can only beat a lower quadplex set of the same type, and cannot beat any other type of combination. Also a quadplex set can be beaten by a bomb made of lower ranked cards.

At the beginning of each round, the landlord has 20 cards and the others each get 17 cards, can the landlord has a strategy to bring out his cards all the way alone until he wins the game and leave no chance for the others to play?

输入:

The first line of the input is T, which stands for the number of test cases you need to solve.

For each case, three lines are given. The first line contains 20 characters describes 20 cards in landlord’s hand. The following two lines each contains 17 characters describe the two peasants’ cards. It is guaranteed that the given 54 cards make up a complete deck.

输出:

The first line of the input is T, which stands for the number of test cases you need to solve.

For each case, three lines are given. The first line contains 20 characters describes 20 cards in landlord’s hand. The following two lines each contains 17 characters describe the two peasants’ cards. It is guaranteed that the given 54 cards make up a complete deck.

样例输入:

6
34567TJQKA2222BRKKKA
45678AAQQJJTT3339
45566778889994TJQ
3456789TJQ2222BRKKK3
456789TJQKAAA3344
5566778899TTJJQQA
3456789TJQKKK4BR2222
456789TJQKA9TTJJQ
AAA3334556677889Q
33445566778899JJJ222
B2AAAKQQTT3456789
RKKKAQQTT3456789J
BR33336666KKKK222245
TTTT7777445JJQQAA
99998888455QQJJAA
AAAKKKQQQJJJTTT98765
BR234555666777888
222333444999TJQKA

样例输出:

Case 1: Yes
Case 2: Yes
Case 3: No
Case 4: Yes
Case 5: No
Case 6: Yes

Hint
A lot of test cases, pay attention to the efficiency of your program.

#include<iostream>
#include<cstring>
using namespace std;//012345678901234
char translate[16] = "3456789TJQKA2BR";
char tot[16] =       "444444444444411";
int a[3][16];
int b[15];
int limit[5] = {0, 5, 3, 0, 0};
int big[5][16];//a[i][j] &plusmn;&iacute;&Ecirc;&frac34;&Iuml;&agrave;&Iacute;&not;&times;&Ouml;&Auml;&cedil;&Ecirc;&yacute;&Aacute;&iquest;&Icirc;&ordf;i?&not;&Aacute;&not;&Aring;&AElig;&Otilde;&Aring;&Ecirc;&yacute;&Icirc;&ordf;j&micro;&Auml;&times;&icirc;&acute;&oacute;&micro;&Auml;&AElig;&eth;&Ecirc;&frac14;&Icirc;&raquo;&Ouml;&Atilde; 
bool rocket;
int attach[16][3];//attach[i][j] &plusmn;&iacute;&Ecirc;&frac34;&Aacute;&not;&ETH;&oslash;i&cedil;&ouml;&Egrave;&yacute;&Otilde;&Aring;&Aring;&AElig;?&not;&acute;&oslash;j&Otilde;&Aring;&Aring;&AElig;&micro;&Auml;&times;&icirc;&acute;&oacute;&AElig;&eth;&Ecirc;&frac14;&Icirc;&raquo;&Ouml;&Atilde; 
int get(char c){
	for (int i = 0; i < 15; ++i)
		if (translate[i] == c) return i;
}
	 
void init(int i, string s){
	memset(a[i], 0, sizeof(a[i]));
	for (int j = 0; j < s.size(); ++j)
		++a[i][get(s[j])];
}
void init(int index){
	if (!index){
		memset(big, 255, sizeof(big));
		memset(attach, 255, sizeof(attach));
		rocket = false;
		return;
	}
	if (a[index][14]&&a[index][13]) rocket = true;
	int b[3] = {0, 0, 0};
	for (int i = 0; i < 15; ++i)
		for (int k = 1; k < 3; ++k)
			if (a[index][i] >= k) ++b[k];
	//cout<<b[1]<<' '<<b[2]<<endl;
	for (int i = 0; i < 15; ++i)
		for (int cardnumber = 1; cardnumber < 5; ++cardnumber)
			for (int len = 1; i + len <= 15; ++len){
				if ((len > 1)&&(i + len > 12)) break;
				int ok = true;
				if (a[index][i + len - 1] >= cardnumber){
					big[cardnumber][len] = max(big[cardnumber][len], i);
					if ((cardnumber == 3)&&(b[1] >= 2 * len))
						attach[len][1] = max(attach[len][1], i);
					if ((cardnumber == 3)&&(b[2] >= 2 * len))
						attach[len][2] = max(attach[len][2], i);
				}
				else break;
				//cout<<"___"<<i<<' '<<cardnumber<<' '<<len<<endl;
				}
}
bool dfs(int remain, int level, bool fail);
bool dfs(int cardnumber, int remain, int i, int len, int index, int begin, int fail){
	//cout<<cardnumber<<' '<<i<<' '<<len<<' '<<index<<' '<<begin<<endl;
	if (index == len){
		if ((len >= 2)&&(b[len - 1] + b[len - 2] == 27)) return false;
		return dfs(remain - (3 + cardnumber) * len, 4000 + i + len, fail);
	}
	for (int j = begin; j < 15; ++j){
		if (j == i) j = i + len;
		//cout<<a[0][j]<<endl;
		if (a[0][j] >= cardnumber){
			a[0][j] -= cardnumber;
			b[index] = j;
			if (dfs(cardnumber, remain, i, len, index + 1, j + 1,fail)) return true;
			a[0][j] += cardnumber;
		}
	}
	return false;
}
bool dfs(int remain, int level, bool fail){
	/*
	int tot = 0;
	cout<<a[4][1]<<endl;
	cout<<remain<<' '<<level<<' '<<fail<<endl;
	for (int i = 0; i < 15; ++i){
		for (int j = 0; j < a[0][i]; ++j)
			cout<<translate[i];
		tot += a[0][i];
	}
	cout<<"    "<<tot<<endl;
	*/
	if (remain == 0) return true;
	//rocket
	if (level == 0){
		if (a[0][14]&&a[0][13]){
			--a[0][14];
			--a[0][13];
			if (dfs(remain - 2, 1000, fail)) return true;
			++a[0][14];
			++a[0][13];
		}
		return dfs(remain, 1000, fail);
	}
	// bomb
	if (level / 1000 == 1){ 
		for (int i = level % 1000; i < 15; ++i)
			if (a[0][i] == 4){
				if (fail&&(i < big[4][1])) continue;
				a[0][i] -= 4;
				if (dfs(remain - 4, 1000 + i + 1, fail||(i < big[4][1]))) return true;
				a[0][i] += 4;
			}
		return dfs(remain, 2000, fail);
	}
	//cout<<remain<<' '<<level<<' '<<fail<<endl;
	if ((big[4][1] > -1)&&(fail)) return false;
	//cout<<remain<<' '<<level<<' '<<fail<<endl;
	//4 and 2
	if (level / 1000 == 2){
		for (int i = level % 1000; i < 15; ++i)
			if (a[0][i] == 4){
				a[0][i] -= 4;
				for (int p = 1; p <= 2; ++p)
				for (int j = 0; j < 13; ++j)
				if (a[0][j] >= p)
				for (int k = j + 1; k < 15; ++k)
				if (a[0][k] >= p){
					a[0][j] -= p;
					a[0][k] -= p;
					if (dfs(remain - 2 * p - 4, 2000 + i + 1, fail|(big[4][1] >= 0))) return true;
					a[0][k] += p;
					a[0][j] += p;
				}
				a[0][i] += 4;
			}
		return dfs(remain, 3000, fail);
	}
	//cout<<remain<<' '<<level<<' '<<fail<<endl;
	//&Euml;&sup3;&times;&Oacute; 
	if (level / 1000 == 3){
		//cout<<"_____"<<big[1][5]<<endl;
		for (int i = level % 100; i < 15; ++i)
		for (int cardnumber = 1; cardnumber < 4; ++cardnumber)
		for (int len = 1; len + i <= 16; ++len){
			//cout<<i<<len<<endl;
			if ((!((len > 1)&&(i + len > 12)))&&(a[0][i + len - 1] >= cardnumber)){
				//cout<<remain<<' '<<level<<' '<<fail<<endl;
				//cout<<i<<len<<endl;
				a[0][i + len - 1] -= cardnumber;
				if (((!(big[cardnumber][len] > i))||(!fail))&&((len >= limit[cardnumber])||(len == 1)))
					if (dfs(remain - cardnumber * len, 3000 + i, fail||(big[cardnumber][len] > i)))
						return true;
			}else{
				for (int j = 0; j < len - 1; ++j)
					a[0][i + j] += cardnumber;
				break;
			}
		}
		return dfs(remain, 4000, fail);
	}
	//attach
	for (int i = level % 1000; i < 15; ++i)
	for (int cardnumber = 1; cardnumber < 3; ++cardnumber)
	for (int len = 1; len + i <= 16; ++len){
		if ((!((len > 1)&&(i + len > 12)))&&(a[0][i + len - 1] >= 3)){
			a[0][i + len - 1] -= 3;
			if ((!(attach[len][cardnumber] > i))||(!fail)){
				if (dfs(cardnumber, remain, i, len, 0, 0, (attach[len][cardnumber] > i)||fail)) return true;
			}
		}else{
			for (int j = 0; j < len - 1; ++j)
				a[0][i + j] += 3;
			break;
		}
		
	}
	return false;
}
int main(){
	/*
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	*/
	int t, _t;
	for (scanf("%d ", &_t), t = 0; t < _t; ++t){
		for (int i = 0; i < 3; ++i){
			string s;
			cin>>s;
			//cout<<s<<endl;
			init(i, s);
			/*
			for (int j = 0; j < 15; ++j)
				if (a[i][j]) cout<<"("<<j<<")"<<translate[j]<<a[i][j]<<" ";
			cout<<endl;
			*/ 
		}
		for (int i = 0; i < 3; ++i)
			init(i);
		for (int i = 0; i < 15; ++i){
			//cout<<translate[i]<<' '<<a[0][i] + a[1][i] + a[2][i]<<endl;
			if (a[0][i] + a[1][i] + a[2][i] != tot[i] - '0') a[0][i] = a[0][i] / (a[0][i] - a[0][i]);
		}
		if (rocket) big[4][1] = 100;
		if (big[4][1] >= 0){
			for( int i = 1; i <= 3; ++i)
				for (int j = 1; j < 16; ++j)
					big[i][j]  = 100;
			for (int i = 1; i <= 2; ++i)
			for (int j = 0; j < 16; ++j)
				attach[j][i] = 100;
			}
		/* 
		for (int i = 1; i <= 4; ++i)
			for (int j = 1; j <=15; ++j)
				cout<<i<<' '<<j<<' '<<big[i][j]<<endl;
		for (int i =1; i <= 15; ++i)
			cout<<i<<' '<<attach[i][1]<<' '<<attach[i][2]<<endl;
			*/ 
		if (dfs(20, 0, 0)){
			printf("Case %d: Yes\n", t + 1);
		}else printf("Case %d: No\n", t + 1);
	}
}

  1. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

  2. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  3. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }

  4. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。