【HDU 3391 && HDU 4431】 dfs+模拟

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3391（3391）

http://acm.hdu.edu.cn/showproblem.php?pid=4431（4431）

3391比较简单，这里我只讲讲4431的题目意思和解法，4431会了3391就是so easy。

题目大意：给你34张牌，1~9筒，1~9索，1~9万，东南西北风中发白。现在给你13张牌，问你再需要什么牌才能胡。

解题思路：

这题好坑爹，开始没按题目给出牌的顺序输出，WS好多次。

这题几点注意的地方： 1：题目意思是问你什么牌能胡，我就34张牌一张一张枚举过去就行了。

2：胡牌的方式右三种 :第一：七对不同的，四个相同的不算两对。第二：十三幺，1、9筒，1、9索，1、9万，东南西北风中发白，这十三张牌里面有一种牌是两张其余的都是一张，俗称“国士无双”。第三：简单的胡牌，先找出一对将军，剩下的十二张牌组成顺子或者小包子（1s2s3s，1s1s1s）。

3.枚举34张牌的时候还要判断这种牌是否超过了4张，超过了明显不符号要求。

4.找到一对（将军）后进行dfs查找顺子或者小包子的时候特别要注意剪枝，这里我超时了好多次。

  1 #include <iostream>
  2 #include <algorithm>
  3 #include <cstring>
  4 #include <cstdio>
  5 using namespace std;
  6 
  7 const char* mj[]= {"1m","2m","3m","4m","5m","6m","7m","8m","9m","1s","2s","3s","4s","5s","6s","7s","8s","9s", "1p","2p","3p","4p","5p","6p","7p","8p","9p","1c", "2c", "3c", "4c", "5c", "6c","7c"};
  8 
  9 int  a[15], c[50], f[50], ok, flag;
 10 
 11 int  conver(char s[])
 12 {
 13     for(int i=0; i<34; i++)
 14     {
 15         if(strcmp(s,mj[i])==0)
 16         {
 17             return i;
 18         }
 19     }
 20     return -1;
 21 }
 22 
 23 void dfs(int cnt)
 24 {
 25     if(cnt==14)  flag=1;
 26     if(flag) return ;
 27     for(int i=0; i<34; i++)
 28     {
 29         int mark=0;
 30         if(c[i]>=3)
 31         {
 32             mark++;
 33             c[i]-=3;
 34             dfs(cnt+3);
 35             c[i]+=3;
 36         }
 37         if(c[i]>=1&&c[i+1]>=1&&c[i+2]>=1&&((0<=i&&i<=6)||(9<=i&&i<=15)||(18<=i&&i<=24)))
 38         {
 39             mark++;
 40             c[i]--,c[i+1]--,c[i+2]--;
 41             dfs(cnt+3);
 42             c[i]++, c[i+1]++, c[i+2]++;
 43         }
 44         //下两行剪枝很关键
 45         if(mark==0&&c[i]) return ;  //这种牌有但是不符合顺子或者小包子结束这层搜索  
 46         if(c[i]) break; //这里减枝是因为上面的搜索下次遍历的时候还会继续从他这遍历，所以就不用继续下去了
 47     }
 48 }
 49 
 50 bool find()
 51 {
 52     int ans=0, cnt=0, ff=0;
 53     for(int i=0; i<34; i++)
 54     {
 55         if(c[i]==2) ans++;
 56         if(c[i]>=1&&((i+1)%9==1||(i+1)%9==0||i>=27))
 57         {
 58             if(c[i]==2) ff++;
 59             cnt++;
 60         }
 61     }
 62     if(ans==7) return true; //判断是否为七对
 63     if(cnt==13&&ff==1) return true;  //判断是否为十三幺
 64     for(int i=0; i<34; i++)
 65     {
 66         if(c[i]>=2)  //枚举将军
 67         {
 68             c[i]-=2;
 69             flag=0;
 70             dfs(2);
 71             if(flag) return true;
 72             c[i]+=2;
 73         }
 74     }
 75     return false;
 76 }
 77 
 78 void judge()
 79 {
 80     for(int i=0; i<34; i++)
 81     {
 82         int ff=0;
 83         memset(c,0,sizeof(c));
 84         c[i]++;
 85         for(int j=0; j<13; j++)
 86         {
 87             c[a[j]]++;
 88             if(c[a[j]]>4) {ff=1; break;}
 89         }
 90         if(ff) continue;
 91         if(find())
 92         {
 93             f[ok++]=i;
 94         }
 95     }
 96 }
 97 
 98 int main()
 99 {
100     char  s[10];
101     int T;
102     cin >> T;
103     while(T--)
104     {
105         for(int i=0; i<=12; i++)
106         {
107             scanf("%s",s);
108             a[i]=conver(s);
109         }
110         ok=0;
111         judge();
112         if(!ok)  printf("Nooten\n");
113         else
114         {
115             printf("%d",ok);
116             for(int i=0; i<ok; i++)
117                 printf(" %s",mj[f[i]]);
118             puts("");
119         }
120     }
121     return 0;
122 }
123 
124 /*
125 这些数据过了基本可以过了
126 10
127 1s 1s 2s 2s 4s 4s 5s 5s 6s 6s 7s 7s 8s
128 1s 9s 1m 9m 1p 9p 1c 2c 3c 4c 5c 6c 7c
129 1s 9s 1m 9m 1p 9p 1c 2c 3c 4c 5c 6c 1m
130 2s 3s 4s 5s 6s 7s 7s 1c 1c 1c 2c 2c 2c
131 2s 3s 4s 5s 6s 7s 7s 7s 1c 1c 2c 2c 2c
132 1s 1s 2s 2s 3s 4s 4s 5s 5s 6s 6s 1c 1c
133 1s 1s 1s 2s 3s 4s 5s 6s 7s 8s 9s 9s 9s
134 1s 1s 1s 1s 2s 3s 9s 9s 9s 2s 3s c1 c1
135 1s 1s 1s 1s 2s 2s 2s 3s 3s 3s 4s 4s 4s
136 */