MyException - 我的异常网
当前位置:我的异常网» C++ » NOIP2015斗地主例题 7.30考试(第一发博文)

NOIP2015斗地主例题 7.30考试(第一发博文)

www.MyException.Cn  网友分享于:2013-08-22  浏览:0次
NOIP2015斗地主题解 7.30考试(第一发博文)

  

问题 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斗地主。

  这道题为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

 

文章评论

我的丈夫是个程序员
我的丈夫是个程序员
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
旅行,写作,编程
旅行,写作,编程
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
总结2014中国互联网十大段子
总结2014中国互联网十大段子
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
老程序员的下场
老程序员的下场
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
我是如何打败拖延症的
我是如何打败拖延症的
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
Java程序员必看电影
Java程序员必看电影
代码女神横空出世
代码女神横空出世
如何成为一名黑客
如何成为一名黑客
每天工作4小时的程序员
每天工作4小时的程序员
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
为什么程序员都是夜猫子
为什么程序员都是夜猫子
一个程序员的时间管理
一个程序员的时间管理
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
 程序员的样子
程序员的样子
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
10个调试和排错的小建议
10个调试和排错的小建议
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
鲜为人知的编程真相
鲜为人知的编程真相
漫画:程序员的工作
漫画:程序员的工作
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
那些争议最大的编程观点
那些争议最大的编程观点
程序员和编码员之间的区别
程序员和编码员之间的区别
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
程序员的鄙视链
程序员的鄙视链
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有