考试T3麻将

工程师树辰技术 2022年11月21日

0 收藏 556 点赞 3,002 浏览 1025 个字

这题就是一个简单的暴力，但考试的时候不知道脑子在想什么，什么都没打出来，也许是我想的太多了。。。

这道题对于不会打麻将的人来说还是有点难理解规则的，~~我没说过我会打麻将，~~这里是题目链接。

20分思路，利用深搜来寻找答案，我们先枚举每一张听牌，那么很显然，时间复杂度就是O(n)，再用深搜来判断可否胡牌。首先，我们用t[x]t[x]来表示数值为x的牌出现了多少次。那么我们就从1到n枚举对子，再枚举刻子和顺子。那么深搜的时间复杂度约是O(2n2)，合起来就是O(2n^3)O(2n3)。因为9<=n<=400，所以会超时。但是不能够同时枚举多个顺子。

100分思路：

还是先枚举听牌，然后再枚举对子，接着枚举多对刻子，最后再枚举顺子。

如果我们设e数组是当前的牌的状态，那么关键代码就是：

  e[j]%=；  e[j+]-=e[j];  e[j+]-=e[j];

那么当e[j]<0时就说明这张牌不是听牌。

下面给一组数据用于对拍：

数据输入：

9 4
1 2 3 3 4 4 5 6 8 8 9 9 9

数据输出：

2 5

 #include<iostream>
 #include<cstdio>
 #include<cstring>
 #include<cstdlib>
 using namespace std;
 int n,m;
 bool flag=;
 const int maxn=1e6+;
 int t[maxn];
 int e[maxn];
 bool check()
 {
     for(int i=;i<=n;i++)
     {
         if(t[i]>=)
         {
             bool ju=;
             t[i]-=;
             for(int j=;j<=n+;j++)
             {
                 e[j]=t[j];
             }
             for(int j=;j<=n+;j++)
             {
                 if(e[j]<)
                 {
                     ju=;
                     break;
                 }
                 e[j]%=;
                 e[j+]-=e[j];
                 e[j+]-=e[j];
             }
             t[i]+=;
             if(ju==)
             {                 return ;
             }
         }
     }
     return ;
 }
 int main()
 {
     cin>>n>>m;
     for(int i=;i<=*m+;i++)
     {
         int x;
         cin>>x;
         t[x]++;
     }
     for(int i=;i<=n;i++)
     {
         t[i]++;
         memset(e,,sizeof(e));
         if(check()==)
         {
             flag=;
             cout<<i<<" ";
         }
         t[i]--;
     }
     if(flag==)
     {
         cout<<"NO";
     }
     return ;
 }