最可做的斗地主系列题(?)
显然的想法是爆搜可怜的牌,然后接着找是否有合法出牌方案.因为总的方案数只有几百万种,所以可以直接枚举每种方案
然后是优化check过程.首先可以发现对子三张牌顺子连对三顺可以拆成若干单牌,飞机可以拆成若干三带一或三带二,所以只有我们只用考虑单牌,三带一,三带二,四带二.如果只考虑单牌,那么一定是两者的牌分别排好序后,可怜某张牌要严格小于网友的对应位置的牌才合法,所以这个可以从大到小枚举牌大小,然后看可怜的每种牌是否都有网友的更大的牌可以配上对,复杂度为(O(14)),也就是牌的种类数
然后考虑剩下的三种(x)带(y).我们把所有(x)带(y)看成先选好(x),然后选(y).所以就可以让两个人先只打三张或四张一样的牌,并且记录下三张牌或四张牌的个数,然后对应带的一些散牌后面处理.因为这些散牌没有限制大小关系,所以实际上(x)带(y)的作用是把一些点数大导致配不上对的牌先消掉.一组三张牌可以带单牌或对子,一组四张牌可以带两张单牌,所以我们可以枚举打几次对子,注意到对子不用枚举各种打法,因为我们要尽量消掉可怜的大的牌,所以最优的方法是每次选择可怜最大的对子消掉;同样贪心的考虑,我们用网友最小的对子与其配对,显然也是最优的.最后还剩下一些三张牌或四张牌没有带上东西(设有(a)组三张牌,(b)租四张牌),因为前面枚举了对子,那么剩下的三张牌我们强制其带单牌,所以就是还可以选出至多(a+2b)单牌配对,剩下的牌就只能用单牌一一对应去check.具体来讲,如果在单牌check过程中有(c)张牌没被配对,那么如果满足(cle a+2b),那么这个就是合法方案,这是因为两个人都会有(c)张牌没被配对好,那么这(c)张牌被三张牌或四张牌带上就行了.复杂度(O(能过))
#include<bits/stdc++.h>
#define LL long long
#define uLL unsigned long long
#define db double
using namespace std;
int rd()
{
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
char cc[20];
int mpp[127];
void inii()
{
mpp['4']=0;
mpp['5']=1;
mpp['6']=2;
mpp['7']=3;
mpp['8']=4;
mpp['9']=5;
mpp['T']=6;
mpp['J']=7;
mpp['Q']=8;
mpp['K']=9;
mpp['A']=10;
mpp['2']=11;
mpp['w']=12;
mpp['W']=13;
}
int lm[14]={4,4,4,4,4,4,4,4,4,4,4,4,1,1};
int ans,ntz[14],karen[14];
bool ck(int pk,int ls,int c1,int c2)
{
int sm=0;
for(int i=13;~i;--i)
{
sm-=karen[i];
sm=max(sm,0)+ntz[i];
}
if(sm<=c1+c2*2) return 1;
int m1,m2;
bool ok=0;
for(;pk>=3;--pk)
{
m1=ls;
while(m1<=13&&karen[m1]<pk) ++m1;
while(m1<=13)
{
m2=m1+1;
while(m2<=13&&ntz[m2]<pk) ++m2;
if(m2>13) break;
while(m2<=13)
{
karen[m1]-=pk,ntz[m2]-=pk;
ok=ck(pk,m1+1,c1+(pk==3),c2+(pk==4));
karen[m1]+=pk,ntz[m2]+=pk;
if(ok) return 1;
++m2;
while(m2<=13&&ntz[m2]<pk) ++m2;
}
++m1;
while(m1<=13&&karen[m1]<pk) ++m1;
}
ls=0;
}
if(!c1) return 0;
m1=13,m2=0;
while((~m1)&&karen[m1]<pk) --m1;
while(m2<=13&&ntz[m2]<pk) ++m2;
if(m1<0||m2>13) return 0;
karen[m1]-=pk,ntz[m2]-=pk;
ok=ck(pk,ls,c1-1,c2);
karen[m1]+=pk,ntz[m2]+=pk;
return ok;
}
void dfs(int o,int nm)
{
if(nm==17)
{
if(ck(4,0,0,0)) ++ans;
return;
}
if(o>13) return;
for(int i=0;i<=lm[o]&&nm+i<=17;++i)
{
karen[o]=i;
dfs(o+1,nm+i);
}
karen[o]=0;
}
int main()
{
inii();
scanf("%s",cc+1);
for(int i=1;i<=17;++i) ++ntz[mpp[cc[i]]],--lm[mpp[cc[i]]];
dfs(0,0);
printf("%d
",ans);
return 0;
}