题目描述
ggwdwsbs最近被Zeratul和Kyurem拉入了日本麻将的坑。现在，ggwdwsbs有13张牌,Kyurem又打了一张，加起来有14张牌。ggwdwsbs想拜托你帮他判断一下，这14张牌能否和。
为了方便起见，本题不考虑字牌，即只有万，筒，条三种类型的牌，牌上带有数字1~9，相同的牌最多可能出现四次。
麻将想要和，必须把14张牌凑成指定的类型——七对子(2222222的形式)或四面子一雀头（23333的形式）。
其中，七对子是指14张牌恰好是7对相同的牌（每两对牌不得相同），如果凑出这样的牌，就可以直接和了；
四面子一雀头是指有一对相同的牌，且其他12张牌凑出四个“3”，这里的“3”可以是三个一样的牌（即刻子），也可以是数字连续且种类一样的三张牌（即顺子）。
在日本麻将中，把牌凑成第二种类型（“23333”）是不足以和牌的，还需要满足另一个条件——存在役。
下面介绍本题要求考虑的四种役。
1. 断幺九：14张牌里没有带数字1和数字9的牌出现。
2. 纯全带幺九：与第一种相反，这种类型要求，那一对相同牌和四个“3”中都要出现至少一张带数字1或9的牌。
3. 平和：四个“3”全部以顺子的形式出现。
4. 对对和：四个“3”全部以刻子的形式出现
满足上述四种中的一种，且满足“23333”的格式，也可以和牌。
请帮ggwdwsbs判断一下，他这14张牌能否和。
输入
第一行一个整数t，表示测试数据组数.
第二行到第t+1，每行有14个范围在1到27之间的整数，每个整数代表一张牌编号。
其中，编号1~9表示“万”的1~9，编号10~18表示“筒”的1~9，编号19~27表示“条”的1~9。
数据保证t≤100，每行的14张牌按编号从小到大给出。
输出
输出t行，每行一个整数，如果能和请输出1，不能和请输出0。
注：日麻的规则还有有很多本题所没有提及，如果你是一个日麻高手，请假装自己不知道那些规则以AC本题。
样例输入
6 1 1 2 2 3 3 4 4 5 5 6 6 7 7 1 2 3 4 5 6 7 8 9 10 10 10 13 13 1 1 1 2 2 2 3 3 3 4 4 4 5 5 1 1 1 2 3 4 5 6 7 8 9 10 11 12 1 1 1 1 2 3 10 11 12 19 20 21 27 27 2 2 2 3 4 5 6 7 8 11 11 11 12 13
样例输出
1 0 1 1 1 1
题目来源
分析：比赛的时候用循环模拟的，结果模拟到心态爆炸，是有想过dfs，但是当时总是觉得循环差一点就出来了不想重新写dfs，于是循环模拟到了炸。。
比赛完后看完题解，和自己开始想的差不多，但是在处理23333的情况的时候，判断1，9和顺子还是刻字的时候优化了太多。。
接下来看代码把，解析写在代码里
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define debug(a) cout << #a << " " << a << endl
using namespace std;
const int maxn = 1e4 + 10;
const int mod = 1e9 + 7;
typedef long long ll;
ll cnt1, cnt2, num, vis[30];
ll dfs( ll x ) {
if( x == 6 ) { //到6时，就是遍历到了最后一个3
if( num == 0 || num == 5 ) { //满足第一种或第二种情况
return 1;
}
if( cnt1 == 4 || cnt2 == 4 ) { //满足第三种或第四种情况
return 1;
}
return 0;
} else if( x == 1 ) {
for( ll i = 1; i <= 27; i ++ ) {
if( vis[i] >= 2 ) { //第一步先取出一个对子，一定要有对子才能继续接下来的步骤
vis[i] -= 2;
if( i%9 == 0 || i%9 == 1 ) { //有幺九就记录加上
num ++;
}
if( dfs(x+1) ) {
return 1;
}
if( i%9 == 0 || i%9 == 1 ) {
num --;
}
vis[i] += 2;
}
}
return 0;
} else {
for( ll i = 1; i <= 27; i ++ ) {
if( vis[i] >= 3 ) { //判断是否有刻子
vis[i] -= 3;
if( i%9 == 0 || i%9 == 1 ) {
num ++;
}
cnt1 ++;
if( dfs(x+1) ) {
return 1;
}
if( i%9 == 0 || i%9 == 1 ) {
num --;
}
cnt1 --;
vis[i] += 3;
}
if( i%9 != 0 && i%9 != 8 && vis[i] && vis[i+1] && vis[i+2] ) { //判断是否有顺子
vis[i] --, vis[i+1] --, vis[i+2] --;
if( i%9 == 7 || i%9 == 1 ) {
num ++;
}
cnt2 ++;
if( dfs(x+1) ) {
return 1;
}
cnt2 --;
if( i%9 == 7 || i%9 == 1 ) {
num --;
}
vis[i] ++, vis[i+1] ++, vis[i+2] ++;
}
}
return 0;
}
}
int main() {
ll t;
cin >> t;
while( t -- ) {
memset( vis, 0, sizeof(vis) );
cnt1 = cnt2 = num = 0;
for( ll i = 0; i < 14; i ++ ) {
ll x;
cin >> x;
vis[x] ++;
}
ll cnt = 0;
for( ll i = 1; i <= 27; i ++ ) {
if( vis[i] == 2 ) {
cnt ++;
}
}
if( cnt == 7 ) { //是否满足七个对子
cout << 1 << endl;
continue;
}
if( dfs(1) ) {
cout << 1 << endl;
} else {
cout << 0 << endl;
}
}
return 0;
}