NOIP2015斗地主题解 7.30考试

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

新老客户大回馈,云服务器低至5折

  

问题 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 4
8 4
9 1
10 4
11 1
5 1
1 4
1 1

样例输出

3

提示

 共有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 }
View Code

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:VS2017不能打开stdio.h等文件

下一篇:P3809 【模版】后缀排序