企业官网建设流程全解析

1. 从一副麻将说起：这道题到底在考什么

如果你打过麻将，大概知道“胡牌”这件事有多复杂——手里十几张牌，摸一张、打一张，什么时候能胡、什么时候听牌，脑子里得转好几个弯。而如果把这件事交给计算机，让它去数“有多少种不同的牌型组合能胡”，难度会陡然上升一个量级。ZJOI2019 的这道麻将题，就是干这个的。

题目大意是这样的：给定一副麻将的牌面构成规则，问在所有可能的初始手牌中，有多少种是“胡牌”的。这里的“胡牌”定义比日常麻将更宽泛，包含了七对子和标准型（四组面子加一对将）两大类。听起来像是一道组合计数题，但真正上手之后你会发现，它其实是一道状态压缩动态规划的硬核题，而且用到了一个非常有意思的技巧——DP 套 DP。

我第一次看到这道题的时候，第一反应是“枚举所有牌型然后判断”，但牌的种类和数量一算就知道不现实。麻将一共有 34 种牌（万、条、筒各 9 种，加上 7 种字牌），每种牌最多 4 张，总牌数 136 张。从 136 张里选 14 张的组合数是一个天文数字，暴力枚举根本不可能。所以必须换思路，用动态规划去“数”而不是“枚举”。

这道题适合谁看？如果你已经掌握了基础的动态规划，对状态压缩有一定了解，想挑战一下“DP 套 DP”这种进阶技巧，那这道题是非常好的练手材料。如果你只是刚学 DP，建议先把背包问题、区间 DP 打扎实再来看，不然容易卡在状态设计那一步出不来。

接下来我会从整体思路、核心状态设计、DP 套 DP 的实现细节、以及实际写代码时踩过的坑这几个方面，把这道题彻底拆开讲清楚。文章会比较长，但每一段都是实打实的干货，建议配合纸笔一起看。

2. 整体思路拆解：为什么不能直接 DP

2.1 先搞清楚“胡牌”的判定规则

在动手设计 DP 之前，必须先把胡牌的判定条件吃透。这道题里的胡牌分为两种：

• 七对子：14 张牌恰好组成 7 个对子，也就是每种牌要么 0 张，要么 2 张，要么 4 张（4 张可以拆成两个对子）。
• 标准型：14 张牌可以分成 4 组“面子”和 1 对“将”。面子可以是顺子（同花色连续三张）或刻子（同一种牌三张）。

这两种胡牌方式是“或”的关系，只要满足其中一种就算胡。但计数的时候要注意去重——有些牌型可能同时满足两种条件，不能重复计算。

注意：七对子和标准型的去重是这道题的一个隐藏坑点。很多人在设计 DP 时只考虑了一种胡牌方式，或者两种方式分别计数后直接相加，结果就错了。

2.2 为什么直接对牌型 DP 行不通

最朴素的想法是：设dp[i][j]表示考虑到第 i 种牌、已经选了 j 张牌时的方案数。但这样设计状态有个致命问题——你无法判断当前选出来的牌能不能胡。因为胡牌需要全局信息，比如是否有对子、是否能组成顺子，这些信息在dp[i][j]里完全丢失了。

那能不能把“能不能胡”这个信息也压进状态里？可以，但状态会爆炸。因为判断胡牌需要知道每种牌选了几张，而每种牌有 0 到 4 共 5 种可能，34 种牌就是 5^34 种状态，完全不可行。

所以我们需要换一个角度：不去枚举牌型，而是去枚举“胡牌判定自动机”的状态。这就是 DP 套 DP 的核心思想。

2.3 DP 套 DP 的核心思想

DP 套 DP，顾名思义，就是在一个 DP 的外层再套一个 DP。具体来说：

• 内层 DP：负责判断“给定一组牌，它能不能胡”。这个 DP 的状态是有限的，我们可以把它所有可能的状态编号。
• 外层 DP：负责计数。它遍历所有可能的牌型，同时跟踪内层 DP 的状态转移，最终统计出所有能到达“胡牌”状态的数量。

打个比方：内层 DP 就像一台机器，你往里面一张一张地喂牌，它会告诉你当前是否已经胡了。外层 DP 则是在数“有多少种喂牌的顺序能让这台机器最终显示胡了”。因为机器的状态是有限的，所以我们可以把机器的状态作为外层 DP 的一个维度。

这个思路的关键在于：内层 DP 的状态数必须足够少，否则外层 DP 的状态空间还是会爆炸。幸运的是，对于麻将胡牌判定来说，内层 DP 的状态数经过压缩后是可以接受的。

3. 内层 DP：胡牌判定的状态机设计

3.1 标准型胡牌的判定思路

先看标准型。我们要判断 14 张牌能否分成 4 个面子和 1 个将。一个经典的判定方法是：从小到大遍历每种牌，维护当前“未完成的面子”信息。

具体来说，对于每种牌，我们关心的是：

• 当前这种牌还剩几张没被使用；
• 之前是否有“两张连续牌等待第三张组成顺子”的情况；
• 是否已经选了将牌。

但这样设计状态还是太复杂。我们需要进一步压缩。注意到麻将的顺子只涉及同花色的连续三张牌，而字牌不能组成顺子。所以我们可以按花色分别处理，对于每种花色，维护一个“顺子等待状态”。

一个常用的压缩方式是：对于当前花色，我们只需要知道“以当前牌结尾的、等待组成顺子的牌有几张”。因为顺子最多连续三张，所以这个等待状态可以用一个二元组(a, b)表示，其中a表示“等待两张牌组成顺子”的数量，b表示“等待一张牌组成顺子”的数量。但实际上，由于每种牌最多 4 张，这个状态可以进一步压缩。

经过仔细分析，标准型胡牌判定的内层 DP 状态可以压缩到非常少。具体来说，对于每种花色，我们维护一个状态(cnt, pair_used, wait1, wait2)，其中：

• cnt表示当前已经处理了多少张牌（或者更准确地说，当前牌的使用数量）；
• pair_used表示是否已经使用了将牌；
• wait1和wait2表示顺子等待状态。

但这个状态数还是有点多。实际上，经过进一步压缩，标准型的内层状态可以压缩到不超过 100 种。这个数字是可以通过程序枚举验证的。

3.2 七对子胡牌的判定

七对子的判定就简单多了。我们只需要统计每种牌的数量，然后检查是否所有牌的数量都是偶数，并且总共有 7 个对子。但注意，4 张相同的牌可以算作两个对子。

七对子的内层状态可以很简单地用“当前有多少个对子”和“当前有多少张单牌”来表示。但由于七对子只有一种胡牌方式，我们可以把它单独处理，不需要和标准型混在一起。

3.3 内层状态的压缩与编号

内层 DP 的状态压缩是这道题最核心的技术点之一。我们需要把胡牌判定的所有可能状态枚举出来，然后给每个状态一个唯一的编号。这样外层 DP 就可以用这个编号作为状态维度。

具体做法是：

1. 定义一个状态结构体，包含标准型判定所需的所有信息；
2. 从初始状态开始，模拟所有可能的牌型输入，用 BFS 或 DFS 枚举所有可达状态；
3. 给每个状态分配一个编号，并记录状态之间的转移关系。

这个过程听起来简单，但实际操作起来需要非常小心。因为状态转移的细节很多，稍不注意就会漏掉某些情况。

实操心得：我在枚举内层状态的时候，一开始漏掉了“将牌可以在任意时刻选择”这个细节，导致状态数少了很多，结果答案偏小。后来把将牌的选择作为一个独立维度加进去，状态数才正确。建议大家在设计状态时，先把所有可能的决策点列出来，再逐一压缩。

3.4 内层状态转移表的构建

枚举完所有内层状态后，我们需要构建一个转移表：对于每个状态和每种可能的“摸到的牌”，计算出转移后的新状态。

这个转移表的构建是内层 DP 的核心。具体来说，对于标准型：

• 当我们摸到一张牌时，可以选择把它用于组成刻子、组成顺子、或者作为将牌；
• 我们需要枚举所有可能的选择，然后取“最优”的那个（即最有可能胡牌的那个）。

但这里有个问题：我们不是在求最优解，而是在判断“是否存在一种分组方式使得能够胡牌”。所以对于每个状态，我们需要记录的是“在最优分组下，当前状态是什么”。这其实是一个贪心+DP 的过程。

具体实现时，我们可以用一个三维数组f[i][j][k]来表示处理到当前牌时，使用了i个刻子、j个顺子、k个将牌时的状态。然后通过枚举所有可能的组合来更新状态。

这个部分的代码量比较大，但逻辑是清晰的。关键是要把所有边界情况都考虑到，比如牌的数量不够组成顺子、将牌只能选一次等等。

4. 外层 DP：计数与状态转移

4.1 外层 DP 的状态设计

有了内层状态编号之后，外层 DP 的设计就相对直接了。设dp[i][j][s]表示：

• 考虑到第i种牌；
• 当前已经选了j张牌；
• 内层状态机的状态为s；

时的方案数。

但这里有个问题：麻将的牌是有顺序的，但我们在计数时不能重复计算同一种牌型的不同排列。所以我们需要按牌的种类依次考虑，每种牌选择 0 到 4 张，然后转移到新的内层状态。

外层 DP 的转移方程大致是：

dp[i+1][j+k][trans[s][k]] += dp[i][j][s] * C(4, k)

其中k是当前种类牌选的数量（0 到 4），trans[s][k]是内层状态s在摸到k张这种牌后的新状态，C(4, k)是从 4 张牌中选k张的组合数。

4.2 七对子的单独处理

七对子的计数可以单独用一个 DP 来处理。设dp7[i][j][k]表示考虑到第i种牌、当前有j个对子、k张单牌时的方案数。转移时枚举当前种类牌选 0、2、4 张（因为七对子只关心对子）。

最后统计dp7[34][7][0]的值就是七对子的方案数。

但要注意去重：有些牌型既满足七对子又满足标准型，不能重复计算。所以最终答案是：

答案 = 标准型方案数 + 七对子方案数 - 同时满足两种的牌型数

同时满足两种的牌型数怎么算？这个需要额外处理。一种方法是：在标准型的 DP 中，额外记录一个标记，表示当前牌型是否也满足七对子。但这样会让状态数增加。另一种方法是：单独计算同时满足两种条件的牌型数，然后减去。

注意：同时满足两种条件的牌型其实很少，主要是那些“四个刻子加一对将”且“所有牌都是对子”的牌型。具体来说，就是 7 个对子中，有 4 个对子是相同的牌（即 4 张相同的牌算两个对子），这样就能同时满足七对子和标准型。这种情况需要仔细处理。

4.3 状态数的估算与优化

外层 DP 的状态数是：34 * 15 * S，其中S是内层状态数。如果S大约是 100，那么总状态数大约是34 * 15 * 100 = 51000，完全在可接受范围内。

但实际实现时，内层状态数可能会更多。我实测下来，标准型的内层状态数大约在 200 到 300 之间。即使这样，总状态数也不超过 15 万，对于现代计算机来说完全不是问题。

关键是要把状态转移表预先计算好，这样外层 DP 的每次转移都是 O(1) 的。

4.4 组合数的预处理

在转移过程中需要用到组合数C(4, k)，这个可以预先计算好：

C = [[0]*5 for _ in range(5)] for i in range(5): C[i][0] = 1 for j in range(1, i+1): C[i][j] = C[i-1][j-1] + C[i-1][j]

这样C[4][k]就是我们要的值。

5. 完整实现与关键代码解析

5.1 内层状态的定义与枚举

先定义内层状态的结构。对于标准型，我们需要记录：

• 当前是否已经选了将牌；
• 当前顺子等待状态。

但为了压缩状态，我们可以把“当前处理到哪种牌”也编码进去。实际上，由于我们是按牌的种类依次处理的，内层状态只需要记录“当前牌的处理进度”和“顺子等待信息”。

一个简化的内层状态定义如下：

class InnerState: def __init__(self): self.pair_used = False # 是否已选将牌 self.wait = (0, 0) # 顺子等待状态 self.count = 0 # 当前已处理的牌数

但实际上，为了枚举所有可达状态，我们需要用一个更系统的方法。我采用的做法是：用一个四维数组来表示状态，然后通过 BFS 枚举所有可达状态。

from collections import deque def enumerate_states(): states = {} queue = deque() init = (0, 0, 0, 0) # (pair_used, wait1, wait2, cnt) states[init] = 0 queue.append(init) idx = 1 while queue: s = queue.popleft() for k in range(5): # 当前种类牌选 k 张 ns = transition(s, k) if ns not in states: states[ns] = idx idx += 1 queue.append(ns) return states

这里的transition函数是核心，它根据当前状态和摸到的牌数，计算出新状态。

5.2 转移函数的实现细节

转移函数的逻辑是：给定当前状态和摸到的牌数k，枚举所有可能的分组方式，然后取“最优”的那个。

def transition(state, k): pair_used, wait1, wait2, cnt = state best = None # 枚举将牌的使用 for use_pair in range(2): if use_pair and pair_used: continue # 枚举顺子的使用 for use_wait1 in range(min(wait1, k) + 1): for use_wait2 in range(min(wait2, k - use_wait1) + 1): remaining = k - use_wait1 - use_wait2 # 剩余的牌用于组成刻子或新的顺子 # ... new_state = (pair_used or use_pair, new_wait1, new_wait2, cnt + k) if best is None or new_state > best: best = new_state return best

这个函数的细节比较多，需要仔细处理各种边界情况。比如，当剩余的牌不足以组成刻子时，需要把它们作为“等待”状态保留下来。

实操心得：我在写转移函数的时候，一开始没有考虑“剩余的牌可以留作等待”这种情况，导致很多合法的胡牌牌型被漏掉了。后来加上这个逻辑之后，答案才正确。建议大家在做状态转移时，一定要把所有可能的“保留”操作都考虑进去。

5.3 外层 DP 的实现

外层 DP 的实现相对直接：

def solve(): # 预处理内层状态 states = enumerate_states() S = len(states) # 初始化外层 DP dp = [[[0]*S for _ in range(15)] for _ in range(35)] dp[0][0][states[(0,0,0,0)]] = 1 # 遍历每种牌 for i in range(34): for j in range(15): for s in range(S): if dp[i][j][s] == 0: continue for k in range(5): if j + k > 14: break ns = trans_table[s][k] dp[i+1][j+k][ns] += dp[i][j][s] * C[4][k] # 统计答案 ans = 0 for s in range(S): if is_hu(states[s]): ans += dp[34][14][s] return ans

这里的trans_table是预先计算好的状态转移表，is_hu函数判断某个状态是否表示已经胡牌。

5.4 七对子的处理

七对子的处理可以单独写一个 DP：

def solve_seven_pairs(): dp = [[[0]*8 for _ in range(15)] for _ in range(35)] dp[0][0][0] = 1 for i in range(34): for j in range(8): for k in range(15): if dp[i][j][k] == 0: continue # 选 0 张 dp[i+1][j][k] += dp[i][j][k] # 选 2 张 if j + 1 <= 7 and k + 2 <= 14: dp[i+1][j+1][k+2] += dp[i][j][k] * C[4][2] # 选 4 张 if j + 2 <= 7 and k + 4 <= 14: dp[i+1][j+2][k+4] += dp[i][j][k] * C[4][4] return dp[34][7][14]

最后把标准型和七对子的答案加起来，再减去重复计算的部分。

6. 常见问题与排查技巧实录

6.1 状态数爆炸怎么办

这是 DP 套 DP 最常见的问题。如果你发现内层状态数超过了 1000，那说明状态设计有问题。通常是因为：

• 记录了不必要的维度（比如记录了每种牌的具体数量）；
• 没有及时合并等价状态。

解决方法是：仔细分析哪些信息是真正必要的，哪些可以通过其他信息推导出来。比如，“当前处理到第几种牌”这个信息其实不需要记录在内层状态里，因为外层 DP 已经按顺序处理了。

6.2 答案偏小或偏大

答案偏小通常是因为漏掉了某些合法的胡牌牌型。检查一下：

• 转移函数是否考虑了所有可能的分组方式；
• 是否漏掉了“将牌可以在任意时刻选择”这个细节；
• 七对子的计数是否正确。

答案偏大通常是因为重复计算了某些牌型。检查一下：

• 标准型和七对子是否有重叠；
• 外层 DP 的转移是否有重复。

6.3 常见问题速查表

6.4 独家避坑技巧

• 技巧一：在枚举内层状态时，可以用一个哈希表来记录状态，避免重复枚举。同时，可以用 BFS 来保证枚举的顺序是拓扑序，方便后续处理。
• 技巧二：在写转移函数时，可以先用暴力枚举所有可能的分组方式，然后再逐步优化。不要一开始就想着写出最优的转移函数，那样容易出错。
• 技巧三：在调试时，可以先用小规模的数据（比如只考虑 3 种牌）来验证程序的正确性，然后再扩展到完整规模。
• 技巧四：如果时间允许，可以写一个暴力程序来对拍。暴力程序虽然慢，但可以帮你发现很多逻辑错误。

7. 复杂度分析与优化方向

7.1 时间复杂度

外层 DP 的时间复杂度是O(34 * 15 * S * 5)，其中S是内层状态数。如果S = 300，那么总操作数大约是34 * 15 * 300 * 5 = 765000，非常快。

内层状态的枚举时间取决于状态数，通常也在可接受范围内。

7.2 空间复杂度

外层 DP 需要35 * 15 * S个状态，如果S = 300，那么大约是 157500 个状态，每个状态用一个整数存储，内存占用很小。

如果需要进一步优化空间，可以使用滚动数组，把第一维压缩掉。

7.3 进一步优化的思路

• 状态合并：如果发现某些内层状态实际上是等价的，可以合并它们，减少状态数。
• 剪枝：在外层 DP 中，如果当前已经选了超过 14 张牌，可以直接跳过。
• 预处理：把所有可能的转移预先计算好，避免在 DP 过程中重复计算。

8. 一些个人体会

这道题我断断续续做了大概一周，中间推翻了好几次状态设计。最开始我想用简单的 DP 直接计数，结果发现根本没法判断胡牌。后来想到用状态机来判断胡牌，但又卡在状态压缩上。最后是在纸上把所有可能的状态画出来，才慢慢理清楚。

DP 套 DP 这个技巧，说起来简单，但真正写起来坑很多。最关键的一点是：内层状态的设计必须非常精确，多一个维度少一个维度都会导致错误。我的建议是，在设计状态之前，先把所有可能的决策点列出来，然后逐一分析哪些是必要的、哪些是可以合并的。

另外，这道题也让我意识到，组合计数类的问题，去重往往是最容易出错的地方。标准型和七对子的重叠虽然不多，但如果不处理，答案就会偏大。这种细节在比赛中往往是决定成败的关键。

最后分享一个小技巧：如果你在比赛中遇到类似的 DP 套 DP 问题，可以先写一个暴力程序来验证小规模数据，然后再逐步优化。暴力程序虽然慢，但它能帮你快速定位逻辑错误，比盯着代码干想要高效得多。