首页 > > 程序设计 > C/C++ >

NOIP2015斗地主题解 7.30考试

2018-06-17 22:09:19来源：未知阅读 ()

问题 B: NOIP2015 斗地主

时间限制: 3 Sec 内存限制: 1024 MB

题目描述

牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、方片的A到K加上大小王的共54张牌来进行的扑克牌游戏。在斗地主中，牌的大小关系根据牌的数码表示如下：3<4<5<6<7<8<9<10<J<Q<K<A<2<小王<大王，而花色并不对牌的大小产生影响。每一局游戏中，一副手牌由n张牌组成。游戏者每次可以根据规定的牌型进行出牌，首先打光自己的手牌一方取得游戏的胜利。现在，牛牛只想知道，对于自己的若干组手牌，分别最少需要多少次出牌可以将它们打光。请你帮他解决这个问题。需要注意的是，本题中游戏者每次可以出手的牌型与一般的斗地主相似而略有不同。具体规则如下：

输入

第一行包含用空格隔开的2个正整数T,N，表示手牌的组数以及每组手牌的张数。

接下来T组数据，每组数据N行，每行一个非负整数对Ai,Bi，表示一张牌，其中Ai表示牌的数码,Bi表示牌的花色，中间用空格隔开。特别的，我们用1来表示数码A，11表示数码J，12表示数码Q，13表示数码K；黑桃、红心、梅花、方片分别用1-4来表示；小王的表示方法为01，大王的表示方法为02。

输出

共T行，每行一个整数，表示打光第T组手牌的最少次数。

样例输入

样例输出

提示

共有1组手牌，包含8张牌：方片7，方片8，黑桃9，方片10，黑桃J，黑桃5，方片A以及黑桃A。可以通过打单顺子（方片7，方片8，黑桃9，方片10，黑桃J），单张

　　这道题为NOIP2015第一天第三题。属于爆搜类，没有任何算法，就是模拟加爆搜。由于有不同种打法，dfs分为好几层，本着先大后小便于剪枝的原则，先出顺子，再带牌，最后散着出。

　　首先，花色对结果无影响，其次大小王对结果是否有贡献只看是否出现其中之一，出现结果+1即可，未出现就不必管了（吐槽一下题目描述，没说四带二不算俩王，但测试点中确实不带）。还有一点值得注意的是大小顺序，首先是2不算顺子，其次1比3~13都大，因此可以把大小统一减2,1、2改为12、13便于使用。

　　先预处理出各个数字（以下都为预处理后的数字）的个数，开始分层爆搜。先提前说明各个数组，la[]为各个数字还剩几个没打，num[i]为数量为i的同数字牌还有几个

　　第一至三层为顺子，它们可以搜索到自己，因为一套牌可以出现多个顺子，至于顺子的长度，从大到小进行枚举，原理见上然后将搜索完的目标再次指向自己，在函数最后向下一层搜索。

　　第四，五层为带，四层为四带二，要注意是四带二不是四带一，因为这个卡了55%，带对带单都可以，又因为可以同时出四带两个单和四带两个双，因此需要引入一个bool型变量确认该次搜索由哪里传下来，若为上层则四带双和四带单都单独搜索，四带双继续指向本层，bool改变，只搜四带单，三同理。

　　第五层就是处理散牌了，不解释。

　　最后膜拜？大犇，有一个剪枝，若到盖层走的步数以比当前最优解大，则直接返回，貌似省了不少时间。

　　本来就是搜索题，只能说这些了，其实主要还是代码能力和脑洞。

  1 #include<iostream>
  2 #include<cstdlib>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<queue>
  6 #include<algorithm>
  7 #include<cmath>
  8 using namespace std;
  9 int t,n,ans=0x7fffffff;
 10 int sum[14],la[14],num[5];
 11 void dfs6(int js){
 12     if(js>=ans)return;
 13     int jj=0;
 14     for(int i=4;i>=1;i--)
 15         jj+=num[i];
 16     ans=min(ans,jj+js);
 17     return;
 18 }
 19 void dfs5(int js,bool pd){ //3 _
 20     if(js>=ans)return;
 21     int nn[5];
 22     memcpy(nn,num,sizeof(num));
 23     if(!pd)
 24     {
 25         for(int i=num[3];i>=1;i--)
 26         {
 27             if(num[2]>=i)
 28             {
 29                 memcpy(num,nn,sizeof(num));
 30                 num[3]-=i;
 31                 num[2]-=i;
 32                 dfs5(js+i,1);
 33                 memcpy(num,nn,sizeof(num));//记得还原，否则判断num[]将会失误。下同。 
 34             }
 35         }
 36     }
 37     for(int i=num[3];i>=1;i--)
 38     {
 39         if(num[1]>=i)
 40         {
 41             memcpy(num,nn,sizeof(num));
 42             num[3]-=i;
 43             num[1]-=i;
 44             dfs6(js+i);
 45             memcpy(num,nn,sizeof(num));
 46         }
 47     }
 48     memcpy(num,nn,sizeof(nn));
 49     dfs6(js);
 50 }
 51 void dfs4(int js,bool pd){      //4 2    
 52     if(js>=ans)    return;
 53     int nn[5];
 54     if(!pd)
 55     {
 56         memset(num,0,sizeof(num));
 57         for(int i=1;i<=13;i++) num[la[i]]++;
 58         memcpy(nn,num,sizeof(num));
 59         for(int i=num[4];i>=1;i--)
 60         {
 61             if(num[2]>=i*2)
 62             {
 63                 memcpy(num,nn,sizeof(nn));
 64                 num[4]-=i;
 65                 num[2]-=i*2;
 66                 dfs4(js+i,1);
 67                 memcpy(num,nn,sizeof(nn)); 
 68             }        
 69         }
 70     }
 71     if(pd) memcpy(nn,num,sizeof(num));
 72     for(int i=num[4];i>=1;i--)
 73     {
 74         if(num[1]>=i*2)
 75         {
 76             memcpy(num,nn,sizeof(nn));
 77             num[4]-=i;
 78             num[1]-=i*2;
 79             dfs5(js+i,0);
 80             memcpy(num,nn,sizeof(nn));
 81         }
 82     }
 83     memcpy(num,nn,sizeof(nn));
 84     dfs5(js,0);
 85 }
 86 void dfs3(int js){    //1s
 87     if(js>=ans) return;
 88     int ll[14];
 89     memcpy(ll,la,sizeof(la));
 90     for(int l=12;l>=5;l--)
 91     {    
 92         for(int i=1;i<=12-l+1;i++)
 93         {
 94             bool yx=1;
 95             for(int j=i;j<=i+l-1;j++)
 96             {
 97                 if(la[j]<1)
 98                 {
 99                     yx=0;
100                     break;
101                 }
102             }
103             if(yx)
104             {
105                 memcpy(la,ll,sizeof(ll));
106                 for(int j=i;j<=i+l-1;j++)
107                 {
108                     la[j]-=1;
109                 }
110                 dfs3(js+1);
111                 memcpy(la,ll,sizeof(ll));
112             }
113         }
114     }
115     memcpy(la,ll,sizeof(ll));
116     dfs4(js,0);
117 }
118 void dfs2(int js){   //2s
119     if(js>=ans)    return;
120     int ll[14];
121     memcpy(ll,la,sizeof(la));
122     for(int l=11;l>=3;l--)
123     {    
124         for(int i=1;i<=12-l+1;i++)
125         {
126             bool yx=1;
127             for(int j=i;j<=i+l-1;j++)
128             {
129                 if(la[j]<2)
130                 {
131                     yx=0;
132                     break;
133                 }
134             }
135             if(yx)
136             {
137                 memcpy(la,ll,sizeof(ll));
138                 for(int j=i;j<=i+l-1;j++)
139                 {
140                     la[j]-=2;
141                 }
142                 dfs2(js+1);
143                 memcpy(la,ll,sizeof(ll));
144             }
145         }
146     }
147     memcpy(la,ll,sizeof(ll));
148     dfs3(js);
149 }
150 void dfs1(int js){  //3s
151     if(js>=ans) return;
152     int ll[14];
153     memcpy(ll,la,sizeof(la));
154     for(int l=7;l>=2;l--)
155     {    
156         for(int i=1;i<=12-l+1;i++)
157         {
158             bool yx=1;
159             for(int j=i;j<=i+l-1;j++)
160             {
161                 if(la[j]<3)
162                 {
163                     yx=0;
164                     break;
165                 }
166             }
167             
168             if(yx)
169             {
170                 memcpy(la,ll,sizeof(ll));
171                 for(int j=i;j<=i+l-1;j++)
172                 {
173                     la[j]-=3;
174                 }
175                 dfs1(js+1);
176                 memcpy(la,ll,sizeof(ll));
177             }
178         }
179     }
180     memcpy(la,ll,sizeof(ll));
181     dfs2(js);
182 }
183 int main(){
184     scanf("%d%d",&t,&n);
185 while(t--)
186 {
187     memset(sum,0,sizeof(sum));
188     memset(la,0,sizeof(la));
189     memset(num,0,sizeof(num));
190     ans=0x7fffffff;
191     int a,b,c,d;
192     for(int i=1;i<=n;i++)
193     {
194         int xx,yy;
195         scanf("%d%d",&xx,&yy);
196         if(xx==1)
197             xx=12;
198         else if(xx==2)
199             xx=13;
200         else xx-=2;
201         if(xx==-2) xx=0;
202         sum[xx]++;
203     }
204     memcpy(la,sum,sizeof(sum));
205     dfs1(0);
206     if(sum[0]) ans++;
207     printf("%d\n",ans);
208 }
209     //while(1);
210     return 0;
211 }