题解 | #听的是哪一张喵#

题目链接

听的是哪一张喵

题目描述

在一种特殊的麻将游戏中，我们只使用 $1$ 到 $n$ 的万子牌，每种牌有 $4$ 张。一个胡牌牌型由 $14$ 张牌组成，形式为 $4$ 个“面子”和 $1$ 个“对子”。

对子：两张相同的牌。
面子：可以是“刻子”（三张相同的牌）或“顺子”（三张连续的牌）。

我们需要计算，使用 $1$ 到 $n$ 的牌，可以组成多少种不同的胡牌牌型。两种牌型不同，当且仅当它们所含的每种牌的数量不同。

解题思路

对于 $n$ 较小的情况，我们可以采用 深度优先搜索 (DFS) + 贪心验证 的方法。

深度优先搜索 (DFS)
- 我们设计一个递归函数 dfs(t, tot)，表示当前正在决定第 t 种牌用几张，还剩下 tot 张牌需要凑齐。
- 在函数中，我们枚举第 t 种牌使用 $i$ 张（ $i$ 从 $0$ 到 $4$ ）。
- 然后递归调用 dfs(t + 1, tot - i)，继续确定下一张牌的数量。
- 递归的终止条件是 t > n。此时，如果剩余牌数 tot 恰好为 $0$ ，说明我们已经构成了一个完整的 $14$ 张牌的组合，可以进入下一步的验证环节。
贪心验证 (check 函数)
- 这个函数负责判断一个 $14$ 张牌的组合是否能胡牌。
- 胡牌的结构是 $1$ 个对子 + $4$ 个面子。我们可以枚举每一种牌 i 作为对子。
- 假设我们尝试用两张 i 作为对子，我们先从手牌中将它们“拿走”。
- 剩下的 $12$ 张牌，我们需要判断它们能否组成 $4$ 个面子（刻子或顺子）。这里可以使用一个巧妙的贪心策略：
  - 从最小的牌 k=1 开始遍历。
  - 对于牌 k，我们优先凑刻子。比如有 $4$ 张 k，我们可以凑一个刻子，剩下 $1$ 张。
  - 凑完刻子后，如果还剩下牌 k（只会剩下 $1$ 或 $2$ 张），那么这些牌必须作为顺子的开头（例如 k, k+1, k+2）。这是因为比 k 小的牌已经处理完毕，剩下的牌 k 无法再向左组成顺子，只能向右。
  - 我们从 k+1 和 k+2 中减去相应数量的牌。如果在任何一步牌不够减了，说明这个方案行不通。
- 如果遍历完所有牌后，成功凑出了 $4$ 个面子，说明这是一个合法的胡牌牌型。只要有一种对子的划分方案能成功，check 函数就返回真。

通过结合 DFS 和 check 函数，我们就能统计出所有可能的胡牌牌型数量。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

int n;
long long ans = 0;
vector<int> a;

// 贪心验证一个牌型是否能胡牌
bool check() {
    // 枚举哪张牌作为对子
    for (int i = 1; i <= n; ++i) {
        if (a[i] >= 2) {
            a[i] -= 2; // 尝试将 i 作为对子

            vector<int> t = a;
            int sets = 0;
            bool possible = true;

            for (int k = 1; k <= n; ++k) {
                // 优先凑刻子
                sets += t[k] / 3;
                t[k] %= 3;

                // 剩下的必须作为顺子开头
                if (t[k] > 0) {
                    if (k + 2 > n || t[k+1] < t[k] || t[k+2] < t[k]) {
                        possible = false;
                        break;
                    }
                    sets += t[k];
                    t[k+1] -= t[k];
                    t[k+2] -= t[k];
                }
            }

            a[i] += 2; // 回溯，恢复牌
            
            if (possible && sets == 4) {
                return true;
            }
        }
    }
    return false;
}

// DFS生成所有可能的14张牌组合
void dfs(int t, int tot) {
    if (t > n) {
        if (tot == 0 && check()) {
            ans++;
        }
        return;
    }
    
    // 剪枝：如果剩下的牌无论如何也凑不齐tot张，则返回
    if (tot > (n - t + 1) * 4) {
        return;
    }

    int upper_bound = min(4, tot);
    for (int i = 0; i <= upper_bound; ++i) {
        a[t] = i;
        dfs(t + 1, tot - i);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    a.resize(n + 3, 0);
    dfs(1, 14);
    cout << ans << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    static int n;
    static long ans;
    static int[] a;

    static boolean check() {
        // 枚举哪张牌作为对子
        for (int i = 1; i <= n; i++) {
            if (a[i] >= 2) {
                a[i] -= 2; // 尝试将 i 作为对子

                int[] t = new int[n + 3];
                System.arraycopy(a, 0, t, 0, a.length);

                int sets = 0;
                boolean possible = true;
                for (int k = 1; k <= n; k++) {
                    // 优先凑刻子
                    sets += t[k] / 3;
                    t[k] %= 3;
                    
                    // 剩下的必须作为顺子开头
                    if (t[k] > 0) {
                        if (k + 2 > n || t[k + 1] < t[k] || t[k + 2] < t[k]) {
                            possible = false;
                            break;
                        }
                        sets += t[k];
                        t[k + 1] -= t[k];
                        t[k + 2] -= t[k];
                    }
                }
                
                a[i] += 2; // 回溯
                
                if (possible && sets == 4) {
                    return true;
                }
            }
        }
        return false;
    }

    static void dfs(int t, int tot) {
        if (t > n) {
            if (tot == 0 && check()) {
                ans++;
            }
            return;
        }

        if (tot > (n - t + 1) * 4) { // 剪枝
            return;
        }

        int upperBound = Math.min(4, tot);
        for (int i = 0; i <= upperBound; i++) {
            a[t] = i;
            dfs(t + 1, tot - i);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        a = new int[n + 3];
        ans = 0;
        dfs(1, 14);
        System.out.println(ans);
    }
}

n = 0
ans = 0
a = []

# 贪心验证一个牌型是否能胡牌
def check():
    global n, a
    # 枚举哪张牌作为对子
    for i in range(1, n + 1):
        if a[i] >= 2:
            a[i] -= 2  # 尝试将 i 作为对子
            
            t = a[:]  # 创建手牌副本
            sets = 0
            possible = True
            
            for k in range(1, n + 1):
                # 优先凑刻子
                sets += t[k] // 3
                t[k] %= 3
                
                # 剩下的必须作为顺子开头
                if t[k] > 0:
                    if k + 2 > n or t[k+1] < t[k] or t[k+2] < t[k]:
                        possible = False
                        break
                    sets += t[k]
                    t[k+1] -= t[k]
                    t[k+2] -= t[k]
            
            a[i] += 2  # 回溯
            
            if possible and sets == 4:
                return True
    return False

# DFS生成所有可能的14张牌组合
def dfs(t, tot):
    global n, a, ans
    if t > n:
        if tot == 0 and check():
            ans += 1
        return

    # 剪枝
    if tot > (n - t + 1) * 4:
        return
    
    upper_bound = min(4, tot)
    for i in range(upper_bound + 1):
        a[t] = i
        dfs(t + 1, tot - i)

def main():
    global n, a, ans
    n = int(input())
    a = [0] * (n + 3)
    ans = 0
    dfs(1, 14)
    print(ans)

main()

算法及复杂度

算法：深度优先搜索 (DFS) + 贪心
时间复杂度： $O(C(n, 14) \cdot n^2)$ ，其中 $C(n, 14)$ 是生成 $14$ 张牌组合的总方案数。对于每个组合，check 函数需要 $O(n)$ 的时间来尝试每个对子，并在内部进行一次 $O(n)$ 的贪心检查。由于 $n$ 很小，总计算量在可接受范围内。
空间复杂度： $O(n)$ ，主要为递归栈的深度和存储牌型的数组。