题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4930
解题报告:斗地主,加了一个四张可以带两张不一样的牌,也可以带一对,判断打出一手牌之后,如果对手没有能够大过你的牌就输出Yes,或者如果你把手上的牌一次性打完也输出Yes,否则输出No,代码有280多行,表示光是敲代码就花了一个多小时,手速还是太慢。
1、首先判断手上的牌能不能一次打完
如果一次性打不完:
2、首先判断对方有没有一对王,有就输出No
3、判断对手有没有四张的牌,如果有,再判断自己有没有四张的牌,如果对手有自己没有就是输,如果自己有对手没有自己有就是赢,如果两个人都有就看谁的更大,如果两个人都没有,则继续判断
4、最后一步,尝试将自己的牌组合成前面的六种打法打出去,然后判断对手有没有可以大过自己的牌,如果有就继续判断,如果没有就是赢。
详细情况看代码吧,有详细的注释。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<deque>
using namespace std; void exchto(char* str,int* num) //先把输入预处理成各种牌的张数num[i]表示第i大的牌有多少张
{
int len = strlen(str);
for(int i = ;i < len;++i)
{
if(str[i] >= '' && str[i] <= '')
num[str[i]-''-]++;
if(str[i] == 'T') num[]++;
if(str[i] == 'J') num[]++;
if(str[i] == 'Q') num[]++;
if(str[i] == 'K') num[]++;
if(str[i] == 'A') num[]++;
if(str[i] == '') num[]++;
if(str[i] == 'X') num[]++;
if(str[i] == 'Y') num[]++;
}
}
int judge_once(const int* num) //判断能否一次打完或者自己有Nuke的情况
{
if(num[] && num[]) //Nuke
return ;
int n = ;
for(int i = ;i <= ;++i)
if(num[i] != ) n++;
if(n > ) return ; //牌种类数大于3不可能一次打完
if(n == ) return ; //等于1一定可以一次打完
if(n == )
{
for(int i = ;i <= ;++i)
for(int j = ;j < i;++j)
{
if(num[i] == && num[j] >= && num[j] <= )
return ;
if(num[j] == && num[i] >= && num[i] <= )
return ;
if(num[i] == && num[j] == )
return ;
if(num[j] == && num[i] == )
return ;
}
}
else if(n == )
{
int flag = -;
for(int i = ;i <= ;++i)
if(num[i] == && flag == -) flag = ;
else if(num[i] == && flag == ) flag = ;
if(flag <= ) return ; //没有4或者有多个4张的,不行
int m = ;
for(int i = ;i <= ;++i)
if(num[i] == ) m++;
if(m == ) return ;
return ;
}
return ;
}
int judge_have4(const int* num1,const int* num2) //判断双方是否存在4
{
int a = ,b = ;
for(int i = ;i >= ;--i)
if(num1[i] == )
{
a = i;
break;
}
for(int i = ;i >= ;--i)
if(num2[i] == )
{
b = i;
break;
}
if(b != && a == ) return -; //对手有4而自己没有4张的情况
if(a != && b == ) return ; //自己有4而对手没四
if(a == && b == ) return ;
if(a >= b) return ;
else if(a < b) return -;
}
/////////下面尝试前六种不同的打法,如果可以用该打法赢,返回1,否则返回0
int judge1(const int* num1,const int* num2)
{
int a = ,b = ;
for(int i = ;i >= ;--i)
if(num1[i] != )
{
a = i;
break;
}
for(int i = ;i >= ;--i)
if(num2[i] != )
{
b = i;
break;
}
return a >= b; //因为双方至少有一张牌,否则要判断是否有没找到的情况
}
int judge2(const int* num1,const int* num2)
{
int a = ,b = ;
for(int i = ;i >= ;--i)
if(num1[i] >= )
{
a = i;
break;
}
for(int i = ;i >= ;--i)
if(num2[i] >= )
{
b = i;
break;
}
if(a != && b == ) return ;
if(a == && b == ) return ;
if(a != && b != ) return a >= b;
return ;
}
int judge3(const int* num1,const int* num2)
{
int a = ,b = ;
for(int i = ;i >= ;--i)
if(num1[i] >= )
{
a = i;
break;
}
for(int i = ;i >= ;--i)
if(num2[i] >= )
{
b = i;
break;
}
if(a != && b == ) return ;
if(a == && b == ) return ;
if(a != && b != ) return a >= b;
return ;
}
int judge4(const int* num1,const int* num2)
{
int a = ,b = ,c = ,d = ;
for(int i = ;i >= ;--i)
if(num1[i] >= )
{
a = i;
break;
}
for(int i = ;i >= ;--i)
if(num2[i] >= )
{
b = i;
break;
}
if(a != )
for(int i = ;i <= ;++i)
if(i != a && num1[i] != )
{
c = ;
break;
}
if(b != )
for(int i = ;i <= ;++i)
if(i != b && num2[i] != )
{
d = ;
break;
}
if(a != && c == && (b == || d == )) return ; //当对手有三个但没有1个另外的也不满足这种打法
if(a == && b == ) return ;
if(a != && b != && c == && d == ) return a >= b;
return ;
}
int judge5(const int* num1,const int* num2)
{
int a = ,b = ,c = ,d = ;
for(int i = ;i >= ;--i)
if(num1[i] >= )
{
a = i;
break;
}
for(int i = ;i >= ;--i)
if(num2[i] >= )
{
b = i;
break;
}
if(a != )
for(int i = ;i <= ;++i)
if(i != a && num1[i] >= )
{
c = ;
break;
}
if(b != )
for(int i = ;i <= ;++i)
if(i != b && num2[i] >= )
{
d = ;
break;
}
if(a != && c == && (b == || d == )) return ; //当对手有三个但没有1个另外的也不满足这种打法
if(a == && b == ) return ;
if(a != && b != && c == && d == ) return a >= b;
return ;
}
int judge6(const int* num1,const int* num2)
{
int a = ,b = ,c = ,d = ;
for(int i = ;i >= ;--i)
if(num1[i] >= )
{
a = i;
break;
}
for(int i = ;i >= ;--i)
if(num2[i] >= )
{
b = i;
break;
}
if(a != )
for(int i = ;i <= ;++i)
if(i != a && num1[i] >= )
c++;
if(b != )
for(int i = ;i <= ;++i)
if(i != b && num2[i] >= )
d++;
if(a != && c >= && b == ) return ;
if(a == && b == ) return ;
if(a != && b != && c >= && d >= ) return a >= b;
return ;
} int main()
{
// freopen("1003.txt","r",stdin);
// freopen("out1.txt","w",stdout);
int T; char one[],two[];
int num1[],num2[];
scanf("%d",&T);
while(T--)
{
scanf("%s%s",one,two);
memset(num1,,sizeof(num1));
memset(num2,,sizeof(num2));
exchto(one,num1);
exchto(two,num2);
if(judge_once(num1)) //判断能否一次打完
{
puts("Yes");
continue;
}
if(num2[] && num2[]) //对手有Nuke直接输
{
puts("No");
continue;
}
int tt1 = judge_have4(num1,num2); //判断双方是否存在4
///////直接赢返回1,直接输返回-1,还有希望返回0
if(tt1 == || tt1 == -) //可以判断出结果
{
printf(tt1 == ? "Yes\n":"No\n");
continue;
}
/////////下面尝试前六种不同的打法,如果可以用该打法赢,返回1,否则返回0
int flag = ;
flag = max(flag,judge1(num1,num2));
flag = max(flag,judge2(num1,num2));
flag = max(flag,judge3(num1,num2));
flag = max(flag,judge4(num1,num2));
flag = max(flag,judge5(num1,num2));
flag = max(flag,judge6(num1,num2));
printf(flag? "Yes\n":"No\n");
}
return ;
}