HDOJ4431Mahjong 模拟

第一次这么专心的这么坚持的开始写这种模拟题，从昨晚的构造思路到300行代码，今天的重写，再到构造了一个特殊情况Hack了杭电的数据，简直完美简直Nice！

题目链接：HDOJ4431

先说说题意：国粹！不按题目描述来解释了，按照麻将官方说法来解释

介绍牌型：4种类型

1万到9万：用1m到9m

1条到9条：用1s到9s

1筒到9筒：用1p到9p

花牌：东西南北中发白：用1c到7c

介绍胡牌方式：

（1）七小对：一对牌就是两个一样的牌。手上13张牌+听的牌（题目中要求的），构成7个对子就可以胡牌。注意这儿有个Hack点！（杭电没有这种数据）7对牌不一定不同哦！比如4个1万可以看作是两对

（2）十三幺：1万9万1条9条1筒9筒东西南北中发白，这13张牌每张1张，然后第14张在这13张中再选任意一张即可

（3）普通胡牌方式：1对+4句话

对于1对，与七小对的解释中对子一样

对于1句话，又可以分成两种情况

第一种，ABC形式。即花色相同的，连续的3个数字的不是花牌的牌型。如1万2万3万（注意，题目中强调了不能是花牌，即东西南1c2c3c不算做一句话）

第二种，AAA形式。即三张一模一样的牌，即：东东东，1万1万1万

对于手中的13张+听的这张，构成任意的1对+4句话的形式，就可以胡牌

昨晚的思路分析：

首先，模拟题得把思路梳理好：

构造数据结构（如何存储牌，1s，1m怎么表示，题目中强调了输出牌的格式）------枚举每一张牌（注意牌的上限张数是4张）------如何判断7小对------如何判断十三幺------找到任意对子+4句话（在这里，每张牌可能组成的一句话的方式不同，如1万1万1万2万2万3万3万有两个理解，3个1万看作一句话，就可以听2万和3万，把1万2万3万看作一句话，就是听1万，把1对1万当作对子，1万2万3万当作一句话，听1万和4万，所以这种牌听1万2万3万4万）

同样的分析方法：1万1万1万2万3万4万5万6万7万8万9万9万9万：是听所有万子的！（清一色的九子连环）

如何给定标记和排序输出

一开始的代码风格是各种瞎弄，for循环之类的写一堆，然后一直tle

错误代码（答案也不全对，但是跟着思路很清晰）：wrong

如果看到这个思路，可以更新到其他的想法，就建议不要再往下看了，自己试着写写，所有的坑点基本已经列出

睡醒之后，跟着这个思路设计了不同的数据结构和枚举策略

1.枚举每一张牌的时候，就用其int值与牌一一对应，按照题目描述的顺序依次编号，1万到9万是1到9号，符号标记为0，枚举的时候不用来回转换可以省时间

2.判断的时候，不是用14张牌是否放到对子和4句话中作为判断，而是用num数组记录每种牌出现了几次

num数组有几个好处，一个深搜的时候好标记也好撤回，用了那几张牌很清楚；另外一个就避免了第一个wrong代码的排序问题，从1到34排序已经是排好的

再一个，用num数组判断七小对和十三幺就是简单的if语句就好；最后一个就是枚举很方便，需要哪张牌就num【x】++，最后再num【x】--就恢复了原手牌；

3.4句话的特殊判断要记得，东西南北中发白是没有ABC的形式只有AAA的形式的，另外再深搜的时候记得提前剪枝ruturn回来避免超时，而且记得恢复num数组

其他的细节代码中都给出注释

从昨晚的写了三个多小时的TLE到今天一个小时就能AC

模拟真的是需要清晰的思路和高超的编辑技术的，加油！

#include<map>
#include<set>
#include<math.h>
#include<time.h>
#include<iostream>
#include<cstdio>
#include<queue>
#include<stack>
#include<stdio.h>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<cstdlib>
using namespace std;

#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define ll rt<<1
#define rr rt<<1|1
#define LL long long
#define ULL unsigned long long
#define maxn 1000000
#define eps 1e-6
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)

int t;

struct node{
	int num,ch;//ch==0:m//ch==1:s//ch==2:p//ch==3:c
	int all;
}a[20],ans[50];

char s[5];
int num[50],tot,flag;

char getch(int x){
	//根据一一对应算出花色 
	if (x>=1&&x<=9) return 'm';
	if (x>=10&&x<=18) return 's';
	if (x>=19&&x<=27) return 'p';
	return 'c';
}

int getnum(int x){
	//根据一一对应算出num值 
	if (x%9) return x%9;
	return 9;
}

void print(node x){
	//便于输出结果 
	printf("%d%c",getnum(x.all),getch(x.all));
}

int cmp1(node x,node y){
	//排序，先按照花色，再按照数值 
	if (x.ch==y.ch) return x.num<y.num;
	return x.ch<y.ch;
}

bool check_sevenpairs(){
	//判断七小对 
	int number=0;
	for(int i=1;i<=34;i++)
	//判断是1对还是两对，注意如果出现num[i]==3的情况是肯定false的所以不用特判 
		if (num[i]==2) number++; 
		else if (num[i]==4) number+=2;
	if (number==7) return true;
	return false;
}

bool check_Koku(){
	//依次判断13种牌有没有
	//再检查是不是有13种牌的某1种有两张 
	for(int i=28;i<=34;i++)
		if (!num[i]) return false;
	if (!num[1]) return false;
	if (!num[9]) return false;
	if (!num[10]) return false;
	if (!num[18]) return false;
	if (!num[19]) return false;
	if (!num[27]) return false;
	if (num[1]==2||num[9]==2||num[10]==2||num[18]==2||num[19]==2||num[27]==2
	  ||num[28]==2||num[29]==2||num[30]==2||num[31]==2||num[32]==2||num[33]==2||num[34]==2) return true;
	return false;
}

bool check_pairs(int steps){
	if (steps==4){
		//4句话枚举完毕了
		//是不是真的把14张牌用完了 
		for(int i=1;i<=34;i++)
			if (num[i]) return false;
		return true;
	}
	for(int i=1;i<=34;i++)
		if (num[i]){
			//这张牌没有被枚举到4句话里面 
			if (num[i]>=3){
				///AAA形式的，34张牌都可以 
				num[i]-=3;
				if (check_pairs(steps+1)){
					num[i]+=3;//记得恢复回来准备下一张牌的枚举 
					return true;
				}
				num[i]+=3;
			}
			if (num[i]&&i<=27){
				//注意i<=27
				//花牌没有ABC的情况 
				if (getch(i+1)==getch(i)&&getch(i+2)==getch(i)&&num[i+1]&&num[i+2]){
					//这个地方一定要判断是同一个花色的
					//因为在枚举中，9，10，11是连续的
					//但是实际麻将中9万1条2条肯定不是1句话 
					num[i]--;num[i+1]--;num[i+2]--;
					if (check_pairs(steps+1)){
						num[i]++;num[i+1]++;num[i+2]++;
						return true;
					}
					num[i]++;num[i+1]++;num[i+2]++;
				}
			}
			return false;
		}
}

int main(){
	//input;
	scanf("%d",&t);
	while(t--){
		memset(num,0,sizeof(num));
		tot=0;
		for(int i=1;i<=13;i++){
			scanf("%s",s);
			//一个数值上一一对应的计算
			a[i].num=s[0]-'0';
			if (s[1]=='m') a[i].ch=0;
			else if (s[1]=='s') a[i].ch=1;
			else if (s[1]=='p') a[i].ch=2;
			else a[i].ch=3;
			a[i].all=a[i].num+a[i].ch*9;
			num[a[i].all]++; 
		}
		
		for(int test=1;test<=34;test++){
			flag=0;
			
			if (num[test]==4) continue;
			num[test]++;
			
			if (check_sevenpairs()) flag=1;
			if (check_Koku()) flag=1;
			
			if (flag){
				//如果是七小对或者十三幺
				//就已经听牌不需要进行之后的判断了 
				tot++;
				ans[tot].all=test;
				num[test]--;
				continue;
			}
			
			for(int i=1;i<=34;i++)
				if (num[i]>=2){
					num[i]-=2;
					if (check_pairs(0)){
						flag=1;
						num[i]+=2;
						//提前恢复 
						break;
					}
					num[i]+=2;
				}
			
			if (flag){
				tot++;
				ans[tot].all=test;
			}
			
			num[test]--;
		}
		
		if (tot){
			printf("%d",tot);
			for(int i=1;i<=tot;i++)
				printf(" "),print(ans[i]);
			printf("\n");
		}
		else cout<<"Nooten"<<endl;
	}
	return 0;
}

注意：上面的程序是过不了的

亲测HDOJ的测试数据，认为4个1万不算作两个对子

所以如果num【x】==4，是不算做两个对子的，这点得注意

其他的模拟都没有问题

另附上测试数据，比较给力的测出了自己的很多错误：

11
1s 1s 1s 1m 1m 4m 4m 7m 7m 9s 9s 5p 5p
1m 2m 3m 4m 5m 6m 7m 8m 9m 1c 2c 2c 2c
1c 2c 3c 4c 5c 6c 7c 1m 2m 3m 4m 5m 6m
1m 2m 3m 4m 5m 6m 7m 1s 1s 1s 2s 2s 2s
1m 1m 1m 2m 3m 4m 5m 6m 7m 8m 9m 9m 9m
1s 1s 1s 2s 3s 4s 5s 6s 7s 8s 9s 9s 9s
1m 2s 2s 3s 3s 4s 4s 5s 5s 6s 6s 7s 7s
1s 2s 3s 2c 2c 2c 2p 3p 5m 6m 7m 1p 1p
1s 9s 1m 9m 1p 9p 1c 2c 3c 4c 5c 6c 7c
1s 1s 1m 9m 1p 9p 1c 2c 3c 4c 5c 6c 7c
1p 1p 2p 3p 4s 5s 6s 7c 7c 3s 3s 2m 2m

其中第1组是Hack数据，龙七对听1s

第二组就是检测3c能不能听，1c2c3c是花牌不能作为一句话

第三组同理

其中还有九子连环的测试数据，希望能减少大家的提交次数

模拟刷起来！