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

算法竞赛选手必看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个21.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²)对于n1e5的数据显然不可行。我们需要利用双指针技术将复杂度降为O(n)。2.1 滑动窗口的条件维护核心观察当固定右指针i时左指针l需要满足对于所有数字jtong[i][j] - tong[l-1][j] ≡ g[j] (mod 3)其中tong[i][j]是前i个元素中数字j的出现次数g[j]是当前枚举的吃组合对数字j的需求量实现时使用哈希表h记录前缀状态出现次数vectorint 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)在n1e5时约7e7次操作实际运行时间约300ms3. 关键实现细节与优化技巧3.1 前缀和数组的高效处理预处理tong数组加速区间数字计数查询vectorvectorint tong(n 1, vectorint(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 状态压缩的位运算技巧虽然使用三进制但实际编码时通过乘法和取模运算实现vectorint 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分解每位表示该吃组合出现的次数模3vectorint 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[i1] x; // 数字i1的需求 g[i2] x; // 数字i2的需求 }4. 同类问题的扩展应用这种三进制状压双指针的技术可以推广到许多需要满足模数条件的子区间统计问题字符频率统计如寻找子串使得各字母出现次数满足特定模关系资源分配问题多类资源的分配需要满足某些周期性条件游戏状态判断卡牌游戏中特定组合的检测实际应用时需要注意当状态空间过大如模数较大或维度较高时可能需要结合哈希或其他优化技术减少内存使用。在训练这类题目时建议从简单版本入手先解决二进制状态压缩问题如LeetCode 1371再尝试固定窗口大小的模数问题最后挑战这种动态窗口多模数条件的复杂变种ICPC这类高水平竞赛中出题人常将多个经典算法组合创新。这道H题的精彩之处在于将麻将规则转化为模数学问题通过三进制压缩将指数级状态变为可处理规模用双指针维护动态变化的模条件最终实现看似O(n³)问题的高效O(n)解法