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

2106. [NOIP2015] 斗地主

2018-06-17 22:30:45来源：未知阅读 ()

2106. [NOIP2015] 斗地主

★★★☆ 输入文件：landlords.in 输出文件：landlords.out 简单对比
时间限制：2 s 内存限制：1025 MB

【题目描述】

牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、方片的A到K加上大小王的共54张牌来进行的扑克牌游戏。在斗地主中，牌的大小关系根据牌的数码表示如下：3<4<5<6<7<8<9<10<J<Q<K<A<2<小王<大王，而花色并不对牌的大小产生影响。每一局游戏中，一副手牌由n张牌组成。游戏者每次可以根据规定的牌型进行出牌，首先打光自己的手牌一方取得游戏的胜利。

现在，牛牛只想知道，对于自己的若干组手牌，分别最少需要多少次出牌可以将它们打光。请你帮他解决这个问题。

需要注意的是，本题中游戏者每次可以出手的牌型与一般的斗地主相似而略有不同。

具体规则如下：

【输入格式】

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

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

【输出格式】

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

【样例输入1】

【样例输出1】

【样例输入2】

【样例输出2】

【提示】

样例1说明

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

对于不同的测试点，我们约定手牌组数T与张数n的规模如下：

数据保证：所有的手牌都是随机生成的。

【来源】

在此键入。

这个题，，我不想多吐槽什么。。。。。。

323行，四个小时，记录...

虽然一开始就看出是暴力搜索了，，但是我写的是BFS，，从来没人AC的BFS。。

好吧我也没AC不过拿了85分。。实在是没什么好优化的了。（传说可以加贪心）

这道题的深搜，我想留到noip2017前夕写。

留个纪念

思路：

暴力枚举所有可能出现的情况

That all

代码略长，留给以后的自己，请勿吐槽

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<queue>
  6 #include<map>
  7 using namespace std;
  8 const int MAXN=101;
  9 int T,n,pai_num,meiyong;
 10 int pai[MAXN];
 11 map<string,bool>mp;
 12 int js=0;
 13 struct node
 14 {
 15     int a[20];
 16     int step;
 17 }now,nxt;
 18 queue<node>q;
 19 int ans=0x7ffff;
 20 inline int pdvis(node p)
 21 {
 22     string gg;
 23     for(int i=1;i<=17;i++)
 24         gg=gg+(char)(p.a[i]-48);
 25     if(mp[gg]==1)return 0;
 26     else
 27     {
 28         mp[gg]=1;
 29         return 1;
 30     }
 31 }
 32 int read(int & n)
 33 {
 34     char c=getchar();
 35     int x=0,flag=0;
 36     while(c<'0'||c>'9')
 37     {if(c=='-')flag=1;
 38     c=getchar();}
 39     while(c>='0'&&c<='9')
 40         x=x*10+(c-48),c=getchar();
 41     if(flag==1)n= -x;
 42     else n= x;    
 43 }
 44 inline void init()
 45 {
 46     mp.clear();
 47     memset(pai,0,sizeof(pai));
 48     memset(now.a,0,sizeof(now));
 49     memset(nxt.a,0,sizeof(nxt));// 多组数据 
 50     for(int i=1;i<=n;i++)
 51     {
 52         read(pai_num);read(meiyong);
 53         if(pai_num==1)pai_num=14;// A
 54         if(pai_num==2)pai_num=15;// 2
 55         if(pai_num==0)
 56         {
 57             if(meiyong==1)pai_num=16;// 小王 
 58             else if(meiyong==2)pai_num=17;
 59         }
 60         pai[pai_num]++;
 61     }
 62 }
 63 inline void pd_danshun(node p)
 64 {
 65     int num=0;
 66     for(int i=3;i<=10;i++)
 67     {
 68         if(p.a[i]>=1)
 69         {
 70             num=1;
 71             for(int j=i+1;j<=14;j++)
 72             {
 73                 if(p.a[j]>=1)
 74                     num++;
 75                 else 
 76                     break;
 77             }
 78             if(num>=5)
 79             {
 80                 for(int j=i;j<=i+num-1;j++)
 81                 p.a[j]--;
 82                 for(int j=3;j<=17;j++)
 83                 nxt.a[j]=p.a[j];
 84                 nxt.step=p.step+1;
 85                 if(pdvis(nxt))
 86                 q.push(nxt);
 87                 for(int j=i;j<=i+num-1;j++)
 88                 p.a[j]++;
 89             }
 90         }
 91         
 92     }
 93 }
 94 inline void pd_shuangshun(node p)
 95 {
 96     int num=0;
 97     for(int i=3;i<=12;i++)
 98     {
 99         if(p.a[i]>=2)
100         {
101             num=1;
102             for(int j=i+1;j<=14;j++)
103             {
104                 if(p.a[j]>=2)
105                     num++;
106                 else 
107                     break;
108             }
109             if(num>=3)
110             {
111                 for(int j=i;j<=i+num-1;j++)
112                 p.a[j]=p.a[j]-2;
113                 for(int j=3;j<=17;j++)
114                 nxt.a[j]=p.a[j];
115                 nxt.step=p.step+1;
116                 if(pdvis(nxt))
117                 q.push(nxt);
118                 for(int j=i;j<=i+num-1;j++)
119                 p.a[j]=p.a[j]+2;
120             }
121         }
122     }
123 }
124 inline void pd_sanshun(node p)
125 {
126     int num=0;
127     for(int i=3;i<=13;i++)
128     {
129         if(p.a[i]>=3)
130         {
131             num=1;
132             for(int j=i+1;j<=14;j++)
133             {
134                 if(p.a[j]==3)
135                     num++;
136                 else 
137                     break;
138             }
139             if(num>=2)
140             {
141                 for(int j=i;j<=i+num-1;j++)
142                 p.a[j]=p.a[j]-3;
143                 for(int j=3;j<=17;j++)
144                 nxt.a[j]=p.a[j];
145                 nxt.step=p.step+1;
146                 if(pdvis(nxt))
147                 q.push(nxt);
148                 for(int j=i;j<=i+num-1;j++)
149                 p.a[j]=p.a[j]+3;
150             }
151         }
152     }
153 }
154 inline void pd_three(node p)
155 {
156     for(int i=3;i<=15;i++)
157     {
158         if(p.a[i]==3)
159         {
160             for(int j=3;j<=15;j++)
161             {
162                 if(i!=j&&(p.a[j]==1||p.a[j]==2))
163                 {
164                     int tmp=p.a[j];
165                     p.a[i]=0;
166                     p.a[j]=0;
167                     for(int k=3;k<=17;k++)
168                         nxt.a[k]=p.a[k];    
169                     nxt.step=p.step+1;
170                     if(pdvis(nxt))
171                     q.push(nxt);
172                     p.a[i]=3;
173                     p.a[j]=tmp;
174                 }
175             }
176             p.a[i]=0;
177             for(int l=3;l<=17;l++)
178                 nxt.a[l]=p.a[l];
179             nxt.step=p.step+1;
180             if(pdvis(nxt))
181             q.push(nxt);
182             p.a[i]=3;
183         }
184     }
185 }
186 inline void pd_boom(node p)
187 {
188     for(int i=3;i<=17;i++)
189     {
190         if(p.a[i]==4)
191         {
192             for(int ll=3;ll<=17;ll++)
193             {
194                 for(int rr=3;rr<=17;rr++)
195                 {
196                     if((p.a[ll]==1&&p.a[rr]==1&&ll!=rr)||(p.a[ll]==2&&p.a[rr]==2&&ll!=rr))
197                     {
198                         int tmp=p.a[ll];
199                         p.a[i]=0;
200                         p.a[ll]=0;
201                         p.a[rr]=0;
202                         for(int kkk=3;kkk<=17;kkk++)
203                         nxt.a[kkk]=p.a[kkk];
204                         nxt.step=p.step+1;
205                         if(pdvis(nxt))
206                         q.push(nxt);
207                         p.a[i]=4;
208                         p.a[ll]=tmp;
209                         p.a[rr]=tmp;
210                     }
211                 }
212             }
213             p.a[i]=0;
214             for(int l=3;l<=17;l++)
215             nxt.a[l]=p.a[l];
216             nxt.step=p.step+1;
217             if(pdvis(nxt))
218             q.push(nxt);
219             p.a[i]=4;
220         }
221     }
222 }
223 inline void pd_other(node p)
224 {
225     for(int i=3;i<=17;i++)
226     {
227         if(i==16)
228         {
229             if(p.a[i]==p.a[i+1]&&p.a[i]!=0)
230             {
231                 p.a[i]=0;
232                 p.a[i+1]=0;
233                 for(int l=3;l<=17;l++)
234                 nxt.a[l]=p.a[l];
235                 nxt.step=p.step+1;
236                 if(pdvis(nxt))
237                 q.push(nxt);
238                 p.a[i]=1;
239                 p.a[i+1]=1;
240                 continue;
241             }
242         }
243         if(p.a[i]==1||p.a[i]==2)
244         {
245             int tmp=p.a[i];
246             p.a[i]=0;
247             for(int l=3;l<=17;l++)
248                 nxt.a[l]=p.a[l];
249             nxt.step=p.step+1;
250             
251             if(pdvis(nxt))
252             q.push(nxt);
253             p.a[i]=tmp;
254         }
255     }
256     
257 }
258 inline void chushihua()
259 {
260     for(int i=3;i<=17;i++)
261     nxt.a[i]=7;
262 }
263 inline int findans(node p)
264 {
265     for(int i=3;i<=17;i++)
266         if(p.a[i]!=0)
267             return 0;
268     return 1;
269 }
270 inline void gaoall(node p)
271 {
272     pd_boom(p);// 炸弹 
273     chushihua();// 初始化 
274     pd_danshun(p);// 单顺子 
275     pd_shuangshun(p);// 双顺子 
276     pd_sanshun(p);// 三顺子 
277     pd_three(p);// 三 
278     pd_other(p);// 单，对，大小王 
279 }
280 void bfs()
281 {
282     js=0;
283     for(int i=3;i<=17;i++)
284         now.a[i]=pai[i];
285     now.step=0;
286     while(q.size()!=0)
287     q.pop();
288     ans=0x7ffff;
289     q.push(now);
290     while(q.size()!=0)
291     {
292         node p=q.front();
293         q.pop();
294         gaoall(p);
295         if(findans(p)==1)
296         {
297             ans=min(ans,p.step);
298             js++;
299             if(js>=5)
300             break;
301         }
302     }
303 }
304 int main()
305 {
306     freopen("landlords.in","r",stdin);
307     freopen("landlords.out","w",stdout);
308     read(T);read(n);
309     while(T--)
310     {
311         init();
312     /*    for(int i=1;i<=17;i++)cout<<i<<"  ";
313         cout<<endl;
314         for(int i=1;i<=17;i++)cout<<pai[i]<<"  ";
315         cout<<endl;*/
316         bfs(); 
317     //    if(ans==2)
318     //        printf("\n%d*%d\n",T,n);
319         printf("%d\n",ans);
320     }
321     
322     return 0;
323 }