2106. [NOIP2015] 斗地主
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 8
7 4
8 4
9 1
10 4
11 1
5 1
1 4
1 1【样例输出1】
3【样例输入2】
1 17
12 3
4 3
2 3
5 4
10 2
3 3
12 2
0 1
1 3
10 1
6 2
12 1
11 3
5 2
12 4
2 2
7 2【样例输出2】
6【提示】
样例1说明
共有1组手牌，包含8张牌：方片7，方片8，黑桃9，方片10，黑桃J，黑桃5，方片A以及黑桃A。可以通过打单顺子（方片7，方片8，黑桃9，方片10，黑桃J），单张牌（黑桃5）以及对子牌（黑桃A以及方片A）在3次内打光。
数据保证：所有的手牌都是随机生成的。
【来源】
在此键入。
这个题，，我不想多吐槽什么。。。。。。
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 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-05-22 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录