2012-0018
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
题意是给13张麻将牌，然后给定胡牌的规则4组3张牌+1组对子。然后问有哪些牌你拿到就能胡牌。
具体做法是这样：
首先枚举你拿到的那一张牌，然后枚举哪一对牌作为对子，接下来检验剩下的12张牌能否凑成4*3的形式。
检验的时候，首先看Honor tiles（z），因为Honor tiles没有顺子，所以只能凑成3张一样的，故每一种Honor tile只能是1张或3张。
然后检验筒（p）、条（s）、万(m)每一种。
对于其中的一种，从1往9扫，用b[i]表示这一种花色的牌数字为i的牌的个数。
对于当前扫到的i，如果b[i]>=3,b[i]=b[i]-3.即将i凑成三张一样的形式。
判断b[i]>=3之后，如果b[i]>0（即原本b[i]=1、2或b[i]=4的情况），并且i<=7,b[i+1]>=b[i],b[i+2]<=b[i]（即能够利用<i,i+1,i+2>的顺子把i分配完），则
b[i+2]=b[i+2]-b[i],b[i+1]=b[i+1]-b[i],b[i]=0（因为使用来b[i]数量的<i,i+1,i+2>，否则的话就没有办法形成一种胡牌的形式。
下面证明这一种贪心式构成法的正确性：
假设目前构成到i，1～i-1都已经组成3张的形式来，如果b[i]<3，则只能通过顺子的形式分配i，如果b[i]>=3，形成一个<i,i,i>的3张形式必然是最优的。因为i只能通过顺子或三张一样的形式来组成胡牌形式，如果使用顺子，需要等数量的i+1和i+2(因为1~i-1已经分配完），那么b[i+1]>=b[i]>=3,b[i+2]>=b[i]>=3,因此如果在b[i]>=3的时候可以用顺子<i,i+1,i+2>将i分配，必然可以将其中三个<i,i+1,i+2>用<i,i,i><i+1,i+1,i+1><i+2,i+2,i+2>的形式展现，因此b[i]>=3的时候组成<i,i,i>情况不会变差，故这种构成方法是正确的。
下面附上我的程序：
#include <cstdio>
#include <cstring>
#include <map>
#define D if(0)
using namespace std;
map<char,int> nu;
char ch[5];
int a[10][5],b[10][5];
int x[40],y[40],l[5];;
int m;
void add(char o,char p)
{
int x,y;
x=o-'0';
y=nu[p];
a[x][y]++;
}
bool check()
{
for(int i=1;i<=3;i++)
for(int j=1;j<=9;j++) b[j][i]=a[j][i];
for(int i=1;i<=3;i++)
for(int j=1;j<=9;j++)
{
if(b[j][i]>=3) b[j][i]-=3;
if(b[j][i]>0)
{
if(j>7) return false;
if((b[j+1][i]<b[j][i])||(b[j+2][i]<b[j][i])) return false;
b[j+1][i]-=b[j][i];
b[j+2][i]-=b[j][i];
b[j][i]=0;
}
}
return true;
}
bool win()
{
bool ok=false;
for(int i=1;i<=4;i++)
for(int j=1;j<=l[i];j++)
if(a[j][i]>=2)
{
a[j][i]-=2;
ok=true;
for(int k=1;k<=7;k++)
if((a[k][4]!=0)&&(a[k][4]!=3)) ok=false;
if(ok) ok=check();
a[j][i]+=2;
if(ok) return true;
}
return false;
}
int main()
{
nu['m']=1;
nu['p']=2;
nu['s']=3;
nu['z']=4;
ch[1]='m';
ch[2]='p';
ch[3]='s';
ch[4]='z';
l[1]=9;l[2]=9;l[3]=9;l[4]=7;
while(scanf("%c%c",&o,&p)!=EOF)
{
memset(a,0,sizeof(a));
add(o,p);
for(int i=2;i<=13;i++)
{
scanf("%c%c",&o,&p);
add(o,p);
}
scanf("%*c");
m=0;
for(int i=1;i<=4;i++)
for(int j=1;j<=l[i];j++)
if(a[j][i]<4)
{
a[j][i]++;
if(win())
{
m++;
x[m]=j;
y[m]=i;
}
a[j][i]--;
}
printf("%d",m);
if(m>0)
{
printf(" ");
for(int i=1;i<=m;i++)
printf("%d%c",x[i],ch[y[i]]);
}
printf("\n");
}
return 0;
}
BY hzwlzrj 题意是给13张麻将牌，然后给定胡牌的规则4组3张牌+1组对子。然后问有哪些牌你拿到就能胡牌。
具体做法是这样：
首先枚举你拿到的那一张牌，然后枚举哪一对牌作为对子，接下来检验剩下的12张牌能否凑成4*3的形式。
检验的时候，首先看Honor tiles（z），因为Honor tiles没有顺子，所以只能凑成3张一样的，故每一种Honor tile只能是1张或3张。
然后检验筒（p）、条（s）、万(m)每一种。
对于其中的一种，从1往9扫，用b[i]表示这一种花色的牌数字为i的牌的个数。
对于当前扫到的i，如果b[i]>=3,b[i]=b[i]-3.即将i凑成三张一样的形式。
判断b[i]>=3之后，如果b[i]>0（即原本b[i]=1、2或b[i]=4的情况），并且i<=7,b[i+1]>=b[i],b[i+2]<=b[i]（即能够利用
b[i+2]=b[i+2]-b[i],b[i+1]=b[i+1]-b[i],b[i]=0（因为使用来b[i]数量的
下面证明这一种贪心式构成法的正确性：
假设目前构成到i，1～i-1都已经组成3张的形式来，如果b[i]<3，则只能通过顺子的形式分配i，如果b[i]>=3，形成一个
下面附上我的程序：
#include
#include
#include
#define D if(0)
using namespace std;
map
char ch[5];
int a[10][5],b[10][5];
int x[40],y[40],l[5];;
int m;
void add(char o,char p)
{
int x,y;
x=o-'0';
y=nu[p];
a[x][y]++;
}
bool check()
{
for(int i=1;i<=3;i++)
for(int j=1;j<=9;j++) b[j][i]=a[j][i];
for(int i=1;i<=3;i++)
for(int j=1;j<=9;j++)
{
if(b[j][i]>=3) b[j][i]-=3;
if(b[j][i]>0)
{
if(j>7) return false;
if((b[j+1][i] b[j+1][i]-=b[j][i]; b[j+2][i]-=b[j][i]; b[j][i]=0; } } return true; } bool win() { bool ok=false; for(int i=1;i<=4;i++) for(int j=1;j<=l[i];j++) if(a[j][i]>=2) { a[j][i]-=2; ok=true; for(int k=1;k<=7;k++) if((a[k][4]!=0)&&(a[k][4]!=3)) ok=false; if(ok) ok=check(); a[j][i]+=2; if(ok) return true; } return false; } int main() { nu['m']=1; nu['p']=2; nu['s']=3; nu['z']=4; ch[1]='m'; ch[2]='p'; ch[3]='s'; ch[4]='z'; l[1]=9;l[2]=9;l[3]=9;l[4]=7; while(scanf("%c%c",&o,&p)!=EOF) { memset(a,0,sizeof(a)); add(o,p); for(int i=2;i<=13;i++) { scanf("%c%c",&o,&p); add(o,p); } scanf("%*c"); m=0; for(int i=1;i<=4;i++) for(int j=1;j<=l[i];j++) if(a[j][i]<4) { a[j][i]++; if(win()) { m++; x[m]=j; y[m]=i; } a[j][i]--; } printf("%d",m); if(m>0) { printf(" "); for(int i=1;i<=m;i++) printf("%d%c",x[i],ch[y[i]]); } printf("\n"); } return 0; } BY hzwlzrj