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是花牌不能作為一句話

第三組同理

其中還有九子連環的測試資料，希望能減少大家的送出次數

模拟刷起來！