Skip to content
本博客自 2023 年 4 月 4 日起转为归档状态，可能不再发表新的博文。点此了解博主的竞赛生涯。
This blog has been archived by the owner since April 4, 2023. It may no longer have new updates.

S2OJ - 1496. 麻将

题解约 1.3 千字
# S2OJ # 模拟
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#题目背景

小 M 十分喜欢立直麻将这种棋牌游戏，而不论是什么麻将，麻将都拥有相似的胡牌规则，小 M 想要考考你，对于给定的一幅手牌，其是否符合麻将的一般型（面子手）中的胡牌型。此外，为了增加难度，小 M 还会考验你给定一幅听牌的手牌，问这幅手牌听什么牌（也就是多获得一张什么样的牌可以胡牌）。

#题目描述

关于麻将的规则，小 M 的介绍如下：

  • 一幅麻将手牌胡牌时应当恰有 1414 张牌（也就是听牌时恰有 1313 张牌），本题中的麻将也不例外；
  • 本题中，麻将共有三种花色，分别是万（用 m 表示）、饼（用 p 表示）、索（用 s 表示），每种花色共有 99 种牌（编号为 1∼91 \sim 9），每种牌最多 44 张，例如一万记为 1m、九索记为 9s。
  • 一幅麻将胡牌时应当由 44 组面子与 11 组雀头组成，其中雀头是指两张完全相同的牌（如：22s、99m），而面子在本题中一共有顺子与刻子两种；
  • 顺子是指数字大小连续的三张同花色的牌，例如：123s、789p、456m；但形如 135m、159p、891s 的三张牌则不构成顺子；
  • 刻子是指三张完全相同的牌，如：333m、777s、444p；但形如 445s 的三张牌则不构成刻子；
  • 当听牌在手牌中已经出现 44 张时，由于没有第 55 张牌可以胡，不认为这张牌是所听的牌。

#输入格式

输入第一行一个正整数 NN，表示麻将牌的张数。

第二行一个正整数 TT 表示手牌组数。

接下来 TT 行，每行 NN 个用空格分隔的长度为 22 的字符串，表示手牌。

#输出格式

输出共 TT 行，对于每组数据：

  • 若 N=14N = 14 输出一行一个非负整数，11 表示胡牌，00 表示没胡。
  • 若 N=13N = 13 输出一行若干个用空格分隔的长度为 22 的字符串，按照第一关键字为 mps，第二关键字为 1-9 的顺序将给定手牌的听牌输出（若没听则输出空行）。

#输入输出样例

样例输入 #1

14
2
1s 1s 1s 2s 3s 4s 5s 6s 7s 8s 9s 9s 9s 5s
1s 1s 1s 2s 3s 4s 5s 6s 7s 8s 9s 9s 9s 1m

样例输出 #1

1
0

样例输入 #2

13
7
1s 2s 3s 4s 5s 6s 7s 8s 9s 1m 1m 2p 3p
2s 2s 3s 3s 4s 4s 5s 6s 6s 7s 7s 8s 8s
1m 1m 1m 1m 2m 2m 2m 2m 3m 3m 3m 4m 9m
1s 1s 1s 2s 3s 4s 5s 6s 7s 8s 9s 9s 9s
1m 1m 1m 2m 3m 7p 8p 9p 9p 9p 9s 9s 9s
1m 1m 1m 1m 2m 2m 3m 3m 7s 8s 9s 9s 9s
2p 3p 4p 4p 4p 4p 5p 6p 7s 8s 9s 9s 9s

样例输出 #2

1p 4p
2s 5s 8s

1s 2s 3s 4s 5s 6s 7s 8s 9s
1m 4m 6p 9p
4m 6s 9s
1p 7p 6s 9s

#数据范围与约定

对于 100%100\% 的数据，Nin{13,14}N in \{13, 14\}，T≤10T \leq 10。

测试点编号 NN 出现的花色的最小数量 每张牌最多出现的次数 特殊性质
11 1414 33 22 有
22 无
33 33
44 44
55 22 22
66 33
77 44
88 11 22
99 33
1010 44
1111
1212 1313 33 22 有
1313 无
1414 33
1515 44
1616 22 22
1717 33
1818 44
1919 11 22
2020 33
2121
2222
2323 44
2424
2525

特殊性质：最多只会有一种牌的张数为两张。

#思路

先考虑胡牌时（N=14N = 14）的情况：当每张牌最多出现 22 次时，只需要考虑顺子和雀头，简单的枚举雀头然后贪心检索即可。其他情况可以暴力检验剩余的牌是否为刻子即可。

当 N=13N = 13 时直接暴力枚举第 1414 张牌，不会超出时间限制。

#代码

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <iostream>
#include <algorithm>
#include <string>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 15;

int n, t, a[N << 2], b[N << 2];

bool check() {
    int cnt = 0;

    for (int i = 1; i <= 27; i++) {
        if (b[i] < 0) return false;
        if (b[i] >= 3) {
            b[i] -= 3;
            cnt++;
        }

        if (i % 9 == 0 || i % 9 == 8) continue;

        while (b[i] > 0) {
            b[i]--, b[i + 1]--, b[i + 2]--;
            cnt++;
        }
    }

    return cnt == 4;
}

bool check_hu() {
    bool flag = false;

    for (int i = 1; i <= 27; i++) {
        if (a[i] >= 2) flag = true;
    }

    if (!flag) return false;

    for (int i = 1; i <= 27; i++) {
        if (a[i] < 2) continue;

        std::copy_n(a, N << 2, b);
        b[i] -= 2;

        if (check()) return true;
    }

    return false;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> t;

    while (t--) {
        std::fill_n(a, N << 2, 0);

        for (int i = 1; i <= n; i++) {
            std::string s;

            cin >> s;

            int x = s[0] - '0';
            char c = s[1];

            if (c == 'p') x += 9;
            else if (c == 's') x += 18;

            a[x]++;
        }

        if (n == 14) {
            cout << check_hu() << endl;
        } else {  // n == 13
            for (int i = 1; i <= 27; i++) {
                if (a[i] < 4) {
                    a[i]++;

                    if (check_hu()) {
                        cout << (i - 1) % 9 + 1;

                        if (1 <= i && i <= 9) {
                            cout << "m ";
                        } else if (10 <= i && i <= 18) {
                            cout << "p ";
                        } else {  // 19 <= i && i <= 27
                            cout << "s ";
                        }
                    }

                    a[i]--;
                }
            }

            cout << endl;
        }
    }

    return 0;
}