洛谷 P4050 麻将 题解【枚举】

点击量：540

突然看到任务计划里有这个题，就点开看了一下……不是很难

目录

题目描述

麻将是中国传统的娱乐工具之一。麻将牌的牌可以分为字牌（共有东、南、西、北、中、发、白七种）和序数牌（分为条子、饼子、万子三种花色，每种花色各有一到九的九种牌），每种牌各四张。

在麻将中，通常情况下一组和了的牌（即完成的牌）由十四张牌组成。十四张牌中的两张组成对子（即完全相同的两张牌），剩余的十二张组成三张一组的四组，每一组须为顺子（即同花色且序数相连的序数牌，例如条子的三、四、五）或者是刻子（即完全相同的三张牌）。一组听牌的牌是指一组十三张牌，且再加上某一张牌就可以组成和牌。那一张加上的牌可以称为等待牌。

在这里，我们考虑一种特殊的麻将。在这种特殊的麻将里，没有字牌，花色也只有一种。但是，序数不被限制在一到九的范围内，而是在1到n的范围内。同时，也没有每一种牌四张的限制。一组和了的牌由3m + 2张牌组成，其中两张组成对子，其余3m张组成三张一组的m组，每组须为顺子或刻子。现给出一组3m + 1张的牌，要求判断该组牌是否为听牌（即还差一张就可以和牌）。如果是的话，输出所有可能的等待牌。

输入输出格式

输入格式：

包含两行。第一行包含两个由空格隔开整数n, m (9<=n<=400, 4<=m<=1000)。第二行包含3m + 1个由空格隔开整数，每个数均在范围1到n之内。这些数代表要求判断听牌的牌的序数。

输出格式：

输出为一行。如果该组牌为听牌，则输出所有的可能的等待牌的序数，数字之间用一个空格隔开。所有的序数必须按从小到大的顺序输出。如果该组牌不是听牌，则输出”NO”。

输入输出样例

输入样例#1：

9 4
1 1 2 2 3 3 5 5 5 7 8 8 8

输出样例#1：

6 7 9

题解：

\(n\)的范围比较小。因此可以大胆想象枚举，这个题的枚举思路也很清晰。

• 枚举听的牌（等待牌） \(O(n)\) 之后把这张牌数量\(+1\)
• 枚举将（对子） \(O(n)\) 之后把这张牌数量\(-2\)
• 看能否胡牌 \(O(n)\)

此时已经去掉了将，因此剩下的只能是刻子或顺子。那么剩下的牌如果某一张不是\(3\)的倍数，那么这一张一定会被组成顺子。

如果一种牌的个数是大于\(0\)的\(3\)的倍数，那么它有两种可能，一是当刻子，另一种是当顺子，这样一来貌似就要多\(O(2^m)\)的复杂度了？其实不是，因为如果剩下\(x\)张的全部作为顺子，那么后面两个就都至少要剩下\(x\)张才可以；又因为\(x\equiv 0\pmod 3\)，所以后面两张的前\(x\)部分一定可以拿去作为刻子的。因此对于每个数目模\(3\)不为\(0\)的牌，只需要检查以它为首的顺子存不存在即可。

Code：

#include<cstdio>
#include<cstring>
int num[405];
int now[405];
int n;
bool check()
{
    for(int i=1;i<=n;++i)
        while(now[i]%3!=0)
        {
            if(!now[i+1]||!now[i+2])
                return false;
            --now[i];
            --now[i+1];
            --now[i+2];
        }
    return true;
}
int main()
{
    int m,u;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=3*m+1;++i)
    {
        scanf("%d",&u);
        ++num[u];
    }
    int flag=0;
    for(int i=1;i<=n;++i)//枚举听哪一张
    {
        ++num[i];
        for(int j=1;j<=n;++j)//枚举将
            if(num[j]>=2)
            {
                for(int k=1;k<=n;++k)
                    now[k]=num[k];
                now[j]-=2;
                if(check())
                {
                    flag=1;
                    printf("%d ",i);
                    break;
                }
            }
        --num[i];
    }
    if(!flag)
        puts("NO");//无解输出NO
    return 0;
}