当前位置：首页 > news >正文

算法竞赛选手必看：ICPC香港站H题Mah-jong的三进制状压与双指针解法详解

news 2026/8/3 6:14:04

算法竞赛选手必看：ICPC香港站H题Mah-jong的三进制状压与双指针解法详解

麻将牌型判断一直是算法竞赛中极具挑战性的问题类型，它不仅考察选手对动态规划、状态压缩等经典算法的掌握程度，更考验将实际问题抽象为数学模型的能力。在2024年ICPC香港区域赛的H题Mah-jong中，命题人巧妙地将麻将的"碰"和"吃"规则转化为三进制状态压缩问题，结合双指针技术实现高效求解。这道题的正解率不足15%，成为区分金牌队伍的关键题目。

1. 麻将规则与问题抽象

麻将的牌型判断核心在于处理两种基本操作：碰（三张相同数字牌）和吃（三张连续数字牌）。在算法设计中，我们需要将这两种操作转化为可计算的数学模型。

碰操作：三个相同的数字牌（如三个"1万"）
吃操作：三个连续的数字牌（如"1万、2万、3万"）

题目要求计算所有满足条件的子区间，其中每个数字牌的使用次数必须是3的倍数（可以同时用于碰和吃）。例如数字"2"可能被用于：

一次碰（消耗3个"2"）
或参与三个不同的吃组合（如"1-2-3"、"2-3-4"、"2-3-4"各消耗1个"2"）

1.1 三进制状态设计

传统状态压缩常用二进制（每位0/1表示存在与否），但本题需要记录每个数字出现次数模3的余数（0/1/2），因此采用三进制：

# 三进制状态示例：数字1-8的出现次数模3 state = 0 for num in range(1, 9): state = state * 3 + (count[num] % 3)

这种表示法将8个数字的状态压缩为一个0~3⁸-1的整数，极大减少了状态空间。实际解题中发现，连续数字的吃操作只涉及相邻6个数字（如"1-2-3"到"6-7-8"），因此状态数可进一步优化为3⁶=729种。

2. 双指针滑动窗口优化

直接枚举所有子区间时间复杂度为O(n²)，对于n=1e5的数据显然不可行。我们需要利用双指针技术将复杂度降为O(n)。

2.1 滑动窗口的条件维护

核心观察：当固定右指针i时，左指针l需要满足对于所有数字j：

tong[i][j] - tong[l-1][j] ≡ g[j] (mod 3)

其中：

tong[i][j]是前i个元素中数字j的出现次数
g[j]是当前枚举的吃组合对数字j的需求量

实现时使用哈希表h记录前缀状态出现次数：

vector<int> h(100000, 0); for (int i = 0; i <= n; i++) h[f[i]]++; // 记录初始前缀状态 int l = 0; for (int i = 1; i <= n; i++) { while (l <= i) h[f[l++]]--; // 移动左指针，剔除无效状态 int s = 0; for (int j = 1; j <= 8; j++) { while (l <= n && tong[l][j] < tong[i-1][j] + g[j]) h[f[l++]]--; // 确保窗口内数字j足够满足g[j]需求 s = s * 3 + (tong[i-1][j] + g[j]) % 3; } if (l > n) break; ans += h[s]; // 统计匹配状态数 }

2.2 复杂度分析

外层循环：729种吃组合
内层双指针扫描：O(n)
总复杂度：O(729*n)，在n=1e5时约7e7次操作，实际运行时间约300ms

3. 关键实现细节与优化技巧

3.1 前缀和数组的高效处理

预处理tong数组加速区间数字计数查询：

vector<vector<int>> tong(n + 1, vector<int>(10, 0)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= 8; j++) tong[i][j] = tong[i-1][j]; tong[i][a[i]]++; }

3.2 状态压缩的位运算技巧

虽然使用三进制，但实际编码时通过乘法和取模运算实现：

vector<int> f(n + 1, 0); for (int i = 1; i <= n; i++) { int state = 0; for (int j = 1; j <= 8; j++) state = state * 3 + (tong[i][j] % 3); f[i] = state; }

3.3 吃组合的枚举与需求计算

6个连续数字的吃组合（如1-2-3到6-7-8）对应三进制数0-728，分解每位表示该吃组合出现的次数模3：

vector<int> g(10, 0); int t = bit; // 当前枚举的吃组合状态(0-728) for (int i = 1; i <= 6; i++) { int x = t % 3; // 第i个吃组合的次数 t /= 3; g[i] += x; // 数字i的需求 g[i+1] += x; // 数字i+1的需求 g[i+2] += x; // 数字i+2的需求 }