洛谷 P4050 麻将 题解【枚举】

作者: wjyyy 分类: 枚举,解题报告 发布时间: 2018-12-23 17:54

点击量:358

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

题目描述

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

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

在这里,我们考虑一种特殊的麻将。在这种特殊的麻将里,没有字牌,花色也只有一种。但是,序数不被限制在一到九的范围内,而是在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;
}

说点什么

avatar
  Subscribe  
提醒
/* */