P2668 斗地主

admin

https://www.luogu.org/problemnew/show/P2668

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

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

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




本题数据随机，不支持hack，要hack或强力数据请点击这里

输入输出格式
输入格式：
第一行包含用空格隔开的2个正整数 T,nT,n ，表示手牌的组数以及每组手牌的张数。

接下来 TT 组数据，每组数据 nn 行，每行一个非负整数对 a_i,b_ia ，表示一张牌，其中 a_ia表示牌的数码， b_ib表示牌的花色，中间用空格隔开。特别的，我们用 11 来表示数码 A， 1111 表示数码 J， 1212 表示数码 Q， 1313 表示数码 K；黑桃、红心、梅花、方片分别用 1-4 来表示；小王的表示方法为 0 1 ，大王的表示方法为 0 2 。

输出格式：
共 TT 行，每行一个整数，表示打光第 ii 组手牌的最少次数。

输入输出样例
输入样例#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次内打光。

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



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

杜文骞

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. int t,n,x,y,ans;
   
4. int sum[25];
   
5. int ans2[25];
   
6. void dfs(int v)
   
7. {
   
8.     if(v>=ans)return;
   
9.     int k=0;
   
10.     for(int i=3;i<=14;i++)
    
11.     {
    
12.         if(sum[i]==0)k=0;
    
13.         else
    
14.         {
    
15.             k++;
    
16.             if(k>=5)
    
17.             {
    
18.                 for(int j=i;j>=i-k+1;j--)
    
19.                 {
    
20.                     sum[j]--;
    
21.                 }
    
22.                 dfs(v+1);
    
23.                 for(int j=i;j>=i-k+1;j--)
    
24.                 {
    
25.                     sum[j]++;
    
26.                 }
    
27.             }
    
28.         }
    
29.     }
    
30.     k=0;
    
31.     for(int i=3;i<=14;i++)
    
32.     {
    
33.         if(sum[i]<=1)k=0;
    
34.         else
    
35.         {
    
36.             k++;
    
37.             if(k>=3)
    
38.             {
    
39.                 for(int j=i;j>=i-k+1;j--)
    
40.                 {
    
41.                     sum[j]-=2;
    
42.                 }
    
43.                 dfs(v+1);
    
44.                 for(int j=i;j>=i-k+1;j--)
    
45.                 {
    
46.                     sum[j]+=2;
    
47.                 }
    
48.             }
    
49.         }
    
50.     }
    
51.     k=0;
    
52.     for(int i=3;i<=14;i++)
    
53.     {
    
54.         if(sum[i]<=2)k=0;
    
55.         else
    
56.         {
    
57.             k++;
    
58.             if(k>=2)
    
59.             {
    
60.                 for(int j=i;j>=i-k+1;j--)
    
61.                 {
    
62.                     sum[j]-=3;
    
63.                 }
    
64.                 dfs(v+1);
    
65.                 for(int j=i;j>=i-k+1;j--)
    
66.                 {
    
67.                     sum[j]+=3;
    
68.                 }
    
69.             }
    
70.         }
    
71.     }
    
72.     for(int i=2;i<=14;i++)
    
73.     {
    
74.         if(sum[i]<=3)
    
75.         {
    
76.             if(sum[i]<=2)continue;
    
77.             sum[i]-=3;
    
78.             for(int j=2;j<=15;j++)
    
79.             {
    
80.                 if(!(sum[j]<=0 || i==j))
    
81.                 {
    
82.                     sum[j]--;
    
83.                     dfs(v+1);
    
84.                     sum[j]++;
    
85.                 }
    
86.             }
    
87.             for(int j=2;j<=14;j++)
    
88.             {
    
89.                 if(!(sum[j]<=0 || i==j))
    
90.                 {
    
91.                     sum[j]-=2;
    
92.                     dfs(v+1);
    
93.                     sum[j]+=2;
    
94.                 }
    
95.             }
    
96.             sum[i]+=3;
    
97.         }
    
98.         else
    
99.         {
    
100.             sum[i]-=3;
     
101.             for(int j=2;j<=15;j++)
     
102.             {
     
103.                 if(!(sum[j]<=0 || i==j))
     
104.                 {
     
105.                     sum[j]--;
     
106.                     dfs(v+1);
     
107.                     sum[j]++;
     
108.                 }
     
109.             }
     
110.             for(int j=2;j<=14;j++)
     
111.             {
     
112.                 if(!(sum[j]<=1 || i==j))
     
113.                 {
     
114.                     sum[j]-=2;
     
115.                     dfs(v+1);
     
116.                     sum[j]+=2;
     
117.                 }
     
118.             }
     
119.             sum[i]+=3;
     
120.             sum[i]-=4;
     
121.             for(int j=2;j<=15;j++)
     
122.             {
     
123.                 if(!(sum[j]<=0 || i==j))
     
124.                 {
     
125.                     sum[j]--;
     
126.                     for(int k=1;k<=14;k++)
     
127.                     {
     
128.                         if(!(sum[k]<=0 || j==k))
     
129.                         {
     
130.                             sum[k]--;
     
131.                             dfs(v+1);
     
132.                             sum[k]++;
     
133.                         }
     
134.                     }
     
135.                     sum[j]++;
     
136.                 }
     
137.             }
     
138.             for(int j=2;j<=14;j++)
     
139.             {
     
140.                 if(!(sum[j]<=1 || i==j))
     
141.                 {
     
142.                     sum[j]-=2;
     
143.                     for(int k=1;k<=13;k++)
     
144.                     {
     
145.                         if(!(sum[k]<=1 || j==k))
     
146.                         {
     
147.                             sum[k]-=2;
     
148.                             dfs(v+1);
     
149.                             sum[k]+=2;
     
150.                         }
     
151.                     }
     
152.                     sum[j]+=2;
     
153.                 }
     
154.             }
     
155.             sum[i]+=4;
     
156.         }
     
157.     }
     
158.     for(int i=2;i<=15;i++)
     
159.     {
     
160.         if(sum[i])
     
161.         {
     
162.             v++;
     
163.         }
     
164.     }
     
165.     ans=min(ans,v);
     
166. }
     
167. int main()
     
168. {
     
169.     cin>>t>>n;
     
170.     for(int i=1;i<=t;i++)
     
171.     {
     
172.         ans=0x7fffffff;
     
173.         memset(sum,0,sizeof(sum));
     
174.         for(int i=1;i<=n;i++)
     
175.         {
     
176.             scanf("%d%d",&x,&y);
     
177.             if(x==0)
     
178.             {
     
179.                 sum[15]++;
     
180.             }
     
181.             else if(x==1)
     
182.             {
     
183.                 sum[14]++;
     
184.             }
     
185.             else
     
186.             {
     
187.                 sum[x]++;
     
188.             }
     
189.         }
     
190.         dfs(0);
     
191.         ans2[i]=ans;
     
192.     }
     
193.     for(int i=1;i<=t;i++)
     
194.     {
     
195.         cout<<ans2[i]<<endl;
     
196.     }
     
197.     return 0;
     
198. }
     

复制代码

lyc

加强版数据太强了……疯狂特判(因为还有可以拆的牌，不过整体还是一样，改一下散牌)然而我之前漏了好多，，，debug好久，部分特判参考题解

1. #include<cstdio>
   
2. #include<cstring>
   
3. #include<iostream>
   
4. #include<algorithm>
   
5. const int N = 20;
   
6. using namespace std;
   
7. int p[N],c[N];
   
8. int n,t,ans;
   
9. int other(){//打散牌
   
10.     int t = 0;
    
11.     int c[10]; bool boom = 0;//炸弹
    
12.     memset(c, 0, sizeof(c));
    
13.     if(p[0] == 2) boom = 1;
    
14.     c[1] += p[0];//王分开算
    
15.     for(int i=1; i<=13; i++) c[p[i]] ++;
    
16.     while(!c[3] && c[4] >= 2 && c[1] == 1 && c[2] == 1) c[4]-=2, c[1] --, c[2] --, t += 2;
    
17.     while(!c[3] && c[4] >= 2 && c[1] == 2 && c[2] == 2) c[4]-=2, c[1] -=2, c[2] -=2, t += 2;
    
18.     while(!c[2] && c[3] >= 2 && c[4] == 1 && c[1] == 1) c[3]-=2, c[1] --, c[4] --, t += 2;
    
19.     if(c[3] + c[4] > c[1] + c[2])
    
20.         while(c[4] && c[2] && c[3]) c[2]--, c[3]--, c[1]++, c[4]--,t++;
    
21.     if(c[3] + c[4] > c[1] + c[2])
    
22.         while(c[4] && c[1] && c[3]) c[1]--, c[3]--, c[2]++, c[4]--,t++;//以上拆牌打更优
    
23.     if(c[3] % 3 == 0 && c[1] + c[2] <= 1)//拆三张
    
24.         while(c[3] > 2) c[3] -= 3, t += 2;
    
25.     while(c[4] && c[2] >= 2) c[4] --, c[2] -= 2, t++;//四带二对
    
26.     while(c[4] && c[1] >= 2) c[4] --, c[1] -= 2, t++;//四带二
    
27.     while(c[4] && c[2] >= 1) c[4] --, c[2] --  , t++;//四带一对
    
28.     while(c[3] && c[2]) c[3] --, c[2] --, t++;
    
29.     while(c[3] && c[1]) c[3] --, c[1] --, t++;
    
30.     while(c[4] >= 2 && c[3]) c[4] -= 2, c[3] --, t+=2;
    
31.     while(c[3] >= 2 && c[4]) c[3] -= 2, c[4] --, t+=2;//拆三和炸弹
    
32.     while(c[3] >= 3) c[3] -= 3, t+=2;//三张三也能拆orz
    
33.     while(c[4] >= 2) c[4]-=2, t++;
    
34.     if(boom && c[1] >= 2) return t + c[1] + c[2] + c[3] + c[4] - 1;
    
35.     return t + c[1] + c[2] + c[3] + c[4];
    
36. }
    
37. void dfs(int now)
    
38. {
    
39.     if(now >= ans)
    
40.         return ;
    
41.     int add = other();
    
42.     if(now + add < ans)
    
43.         ans = now + add;
    
44.     for(int i=2; i<=13; i++)
    
45.     {
    
46.         int j=i;
    
47.         while(p[j] >= 3)
    
48.             j++;
    
49.         if(j-i >= 2)
    
50.         {
    
51.             for(int m=i+1; m<=j-1; m++)
    
52.             {
    
53.                 for(int k=i; k<=m; k++)
    
54.                     p[k]-=3;
    
55.                 dfs(now+1);
    
56.                 for(int k=i; k<=m; k++)
    
57.                     p[k]+=3;
    
58.             }
    
59.         }
    
60.     }
    
61.     for(int i=2; i<=13; i++)
    
62.     {
    
63.         int j=i;
    
64.         while(p[j]>=2)
    
65.             j++;
    
66.         if(j-i>=3)
    
67.         {
    
68.             for(int m=i+2; m<=j-1; m++)
    
69.             {
    
70.                 for(int k=i; k<=m; k++)
    
71.                     p[k]-=2;
    
72.                 dfs(now+1);
    
73.                 for(int k=i; k<=m; k++)
    
74.                     p[k]+=2;
    
75.             }
    
76.         }
    
77.     }
    
78.     for(int i=2; i<=13; i++)
    
79.     {
    
80.         int j=i;
    
81.         while(p[j]>=1)
    
82.             j++;
    
83.         if(j-i>=3)
    
84.         {
    
85.             for(int m=i+4; m<=j-1; m++)
    
86.             {
    
87.                 for(int k=i; k<=m; k++)
    
88.                     p[k]--;
    
89.                 dfs(now+1);
    
90.                 for(int k=i; k<=m; k++)
    
91.                     p[k]++;
    
92.             }
    
93.         }
    
94.     }
    
95. }
    
96. 
    
97. int main()
    
98. {
    
99.     cin>>t>>n;
    
100.     while(t--)
     
101.     {
     
102.         memset(p,0,sizeof(p));
     
103.         for(int i=1; i<=n; i++)
     
104.         {
     
105.             int a, b;
     
106.             cin>>a>>b;
     
107.             if(a==1)
     
108.                 a=13;
     
109.             else if(a)
     
110.                 a--;
     
111.             p[a]++;
     
112.         }
     
113.         ans=n;
     
114.         dfs(0);
     
115.         cout<<ans<<endl;
     
116.     }
     
117.     return 0;
     
118. }
     

复制代码

admin

好牛！ 此题很锻炼你们的手上的功夫

lyc

一开始直接搜索tle,后来看题解说搜索顺子，散牌贪心打出来，没考虑拆牌打，不过随机数据弱……
这种题打得真的累……

1. #include<cstdio>
   
2. #include<cstring>
   
3. #include<iostream>
   
4. #include<algorithm>
   
5. const int N = 20;
   
6. using namespace std;
   
7. int p[N],c[N];
   
8. int n,t,ans;
   
9. int other()
   
10. {
    
11.     memset(c,0,sizeof(c));
    
12.     for(int i=0; i<=13; i++)
    
13.         c[p[i]]++;
    
14.     int t=0;
    
15.     while(c[4] && c[2]>1)
    
16.         c[4]--, c[2]-=2, t++;
    
17.     while(c[4] && c[1]>1)
    
18.         c[4]--, c[1]-=2, t++;
    
19.     while(c[4] && c[2])
    
20.         c[4]--, c[2]--, t++;
    
21.     while(c[3] && c[2])
    
22.         c[3]--, c[2]--, t++;
    
23.     while(c[3] && c[1])
    
24.         c[3]--, c[1]--, t++;
    
25.     return t + c[1] + c[2] + c[3] + c[4];
    
26. }
    
27. 
    
28. void dfs(int now)
    
29. {
    
30.     if(now >= ans)
    
31.         return ;
    
32.     int add = other();
    
33.     if(now + add < ans)
    
34.         ans = now + add;
    
35.     for(int i=2; i<=13; i++)
    
36.     {
    
37.         int j=i;
    
38.         while(p[j] >= 3)
    
39.             j++;
    
40.         if(j-i >= 2)
    
41.         {
    
42.             for(int m=i+1; m<=j-1; m++)
    
43.             {
    
44.                 for(int k=i; k<=m; k++)
    
45.                     p[k]-=3;
    
46.                 dfs(now+1);
    
47.                 for(int k=i; k<=m; k++)
    
48.                     p[k]+=3;
    
49.             }
    
50.         }
    
51.     }
    
52.     for(int i=2; i<=13; i++)
    
53.     {
    
54.         int j=i;
    
55.         while(p[j]>=2)
    
56.             j++;
    
57.         if(j-i>=3)
    
58.         {
    
59.             for(int m=i+2; m<=j-1; m++)
    
60.             {
    
61.                 for(int k=i; k<=m; k++)
    
62.                     p[k]-=2;
    
63.                 dfs(now+1);
    
64.                 for(int k=i; k<=m; k++)
    
65.                     p[k]+=2;
    
66.             }
    
67.         }
    
68.     }
    
69.     for(int i=2; i<=13; i++)
    
70.     {
    
71.         int j=i;
    
72.         while(p[j]>=1)
    
73.             j++;
    
74.         if(j-i>=3)
    
75.         {
    
76.             for(int m=i+4; m<=j-1; m++)
    
77.             {
    
78.                 for(int k=i; k<=m; k++)
    
79.                     p[k]--;
    
80.                 dfs(now+1);
    
81.                 for(int k=i; k<=m; k++)
    
82.                     p[k]++;
    
83.             }
    
84.         }
    
85.     }
    
86. }
    
87. 
    
88. int main()
    
89. {
    
90.     cin>>t>>n;
    
91.     while(t--)
    
92.     {
    
93.         memset(p,0,sizeof(p));
    
94.         for(int i=1; i<=n; i++)
    
95.         {
    
96.             int a, b;
    
97.             cin>>a>>b;
    
98.             if(a==1)
    
99.                 a=13;
    
100.             else if(a)
     
101.                 a--;
     
102.             p[a]++;
     
103.         }
     
104.         ans=n;
     
105.         dfs(0);
     
106.         cout<<ans<<endl;
     
107.     }
     
108.     return 0;
     
109. }

复制代码