华师一附中OI组

标题: P2668 斗地主 [打印本页]
作者: admin    时间: 2018-5-11 11:16
标题: P2668 斗地主
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的规模如下：



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


作者: lyc    时间: 2018-7-4 16:58
一开始直接搜索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. }

  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. }

  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. }
复制代码
作者: admin    时间: 2018-7-4 17:25
好牛！ 此题很锻炼你们的手上的功夫
作者: lyc    时间: 2018-7-4 18:06
本帖最后由 lyc 于 2018-7-4 18:08 编辑

加强版数据太强了……疯狂特判(因为还有可以拆的牌，不过整体还是一样，改一下散牌)然而我之前漏了好多，，，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. }

  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. }
复制代码
作者: 杜文骞    时间: 2020-1-16 11:43
  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. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2