蓝桥杯算法训练：状态压缩DP解决子集划分问题实战

1. 项目概述从“无聊的逗”到状态压缩DP的实战看到“ALGO-1004 无聊的逗”这个标题很多刚接触蓝桥杯算法训练的同学可能会有点懵甚至觉得这题是不是在开玩笑。但做过的人都知道这恰恰是蓝桥杯ALGO算法训练系列里一道非常经典且“狡猾”的题目。它披着轻松的外衣内里却考察了算法竞赛中一个重要的思想——状态压缩动态规划或者更具体地说是子集划分和位运算的巧妙结合。这道题的核心不是去实现一个“逗”的程序而是解决一个资源分配最优化问题给你一堆长度已知的木棍两个人可以理解为“逗”和“被逗”的双方各拿一些如何分配才能让两人拿到的木棍总长度相等并且这个相等的长度尽可能大最终输出的就是这个最大可能的相等长度。如果没法相等那就输出0。理解了这个本质你就不会被标题带偏而是能直击问题核心。这道题在蓝桥杯的练习体系中属于从基础递推、搜索向中级动态规划过渡的关键节点。它不像纯粹的背包问题那样有明确的模板需要你真正理解状态表示和转移的内涵。网上很多题解要么讲得太抽象要么直接甩代码对于状态压缩DP的新手来说看完还是云里雾里。我当年也是卡了很久后来通过拆解几个关键步骤才豁然开朗。今天我就结合自己的踩坑经验把这道题的解题思路、代码实现细节以及背后的原理掰开揉碎了讲清楚目标是让你不仅能AC这道题更能掌握状态压缩DP解决子集问题的通用思路。2. 问题本质与数学模型抽象2.1 题目重述与关键信息提取我们先抛开那个有点误导性的标题把题目的核心约束用我们自己的话描述一遍输入第一行是一个整数n代表木棍的数量。第二行是n个整数代表每根木棍的长度。目标将这n根木棍分成两组每组至少一根木棍且每根木棍只能属于其中一组使得两组木棍的总长度相等。输出在所有可能的分组方案中找出的那个相等的总长度的最大值。如果没有任何方案能使两组总长度相等则输出0。这里有几个非常关键的隐含条件直接决定了我们的解题方向木棍不可分割每根木棍的长度是固定的整数不能折断。分组是子集划分从n根木棍的集合中选出两个不相交的非空子集。求最优解不是判断能否平分而是求能平分的最大长度。这意味着我们需要遍历所有可能的子集划分方案。举个例子木棍长度为[1, 2, 3, 4, 5]。一种可行的划分是{1, 4}和{2, 3}两组和都是5。另一种是{5}和{2, 3}但这样和分别是5和5不对{2,3}和是5但{5}也是5所以这也是可行的且长度是5。我们还能找到和更大的平分方案吗{3,4}和是7但剩下的{1,2,5}和是8不相等。{1,2,3,4}和是10剩下{5}和是5也不等。看起来5就是最大值。这个思考过程其实就是暴力枚举的雏形。2.2 暴力搜索的不可行性分析最直观的想法是生成所有可能的子集划分。对于n根木棍我们先选出一个非空子集A剩下的自然构成子集B。检查sum(A) sum(B)是否成立并更新最大值。 那么有多少种选法呢对于每根木棍它可以被分到A组、B组或者“都不在”不对每根木棍必须属于且仅属于一组。所以每根木棍有2种选择A或B。但A和B不能同时为空。因此总的方案数是2^n - 2减去全部分到A和全部分到B这两种导致某一组为空的情况。当n30时2^30大约是10亿量级这显然会超时蓝桥杯通常时间限制在1s左右。因此暴力枚举所有子集划分是行不通的。注意这里容易陷入一个思维误区认为是在2^n个子集中找两个子集。实际上一旦你选定了子集A子集B就唯一确定了即全集减去A。所以搜索空间确实是2^n量级但检查每个方案时我们只需要计算一次和。2.3 问题转化与状态压缩DP的引入既然暴力不行我们就需要更聪明的方法。这里的关键转化在于我们并不需要同时关心两组的具体构成只需要关注能否用一部分木棍拼出某个特定的长度。设所有木棍的总长度为total_sum。如果存在一种划分使得两组和相等设这个相等的和为S那么必然有2 * S total_sum且S是整数。同时问题等价于能否从这些木棍中选出一个子集其总和恰好为S。因为如果你能选出一个子集和为S那么剩下的木棍和自然就是total_sum - S。为了让两组和相等我们需要S total_sum - S即S total_sum / 2。但这是对于“完美平分”的情况。我们的目标是找到最大的S使得存在子集和为S并且同时存在另一个不相交的子集和也为S即剩下的木棍和也是S。这等价于total_sum - S也必须能由某个子集拼出并且这个子集与拼出S的子集不相交。这听起来有点绕。换个角度我们最终要求的是最大的S满足S total_sum / 2(因为两组和相等任何一组的和不会超过总和的一半)。存在一个子集其元素和恰好为S。剩下的木棍中也能找到一个子集当然这个子集就是剩下的所有木棍本身其和也恰好为S不对剩下的木棍总和是total_sum - S。我们需要total_sum - S也能被某个子集拼出来吗其实不需要因为剩下的木棍本身就是一个整体它的和就是total_sum - S。我们要的是total_sum - S S即S total_sum / 2。但这又回到了完美平分。这里出现了逻辑矛盾。让我们重新审视题目允许两组木棍的数量不同。假设我们找到了一个子集A其和为S。那么剩下的木棍组成集合B其和为total_sum - S。题目要求S total_sum - S吗是的因为两组长度要相等。所以确实只有S total_sum / 2时才有可能。但题目又要求输出最大的S如果total_sum是奇数那就不可能存在整数S使得2S total_sum那答案不就是0了这显然不对看之前的例子[1,2,3,4,5]总和是15是奇数但我们找到了S5的方案。误区澄清我犯了一个错误。题目并没有要求“所有木棍都必须被使用”这是最关键的一点。题目说“他拿出n根木棍并将其中一些粘成一根更长木棍”。注意是“其中一些”。在分组时我们是从n根木棍中选出两个子集没有被选中的木棍就被丢弃了或者理解为没有参与游戏。所以我们并不是把全集划分成两个子集而是从全集中选择两个不相交的子集这两个子集的并集不一定等于全集。剩下的木棍是无关的。因此设选出的两个子集分别为A和B我们需要sum(A) sum(B)并且A ∩ B ∅。A和B的并集是全集的一个子集。设我们实际使用的木棍总长度为used_sum sum(A) sum(B) 2 * S。那么问题转化为能否从n根木棍中选出两个不相交的子集使得它们的和相等求这个相等的和的最大值。这等价于寻找一个最大的整数S使得存在两个不相交的子集它们的和都是S。或者说能否从木棍中选出一些使得它们的总重量为2S并且这些木棍可以被分成和相等的两堆。这其实就是“子集划分”问题的一个变种有时被称为“子集平分”问题或“划分成两个和相等的子集”问题但这里不要求用完所有元素。2.4 状态定义与位运算表示既然要处理子集而n最大可能到30甚至更多取决于题目具体规定但ALGO-1004通常n在15左右可以用状态压缩我们很自然地想到用状态压缩动态规划。状态压缩DP的核心思想是用一个整数的二进制位来表示一个集合。如果木棍数量n较小比如n 20或n 25取决于总时间我们可以用一个int或long long的二进制位来表示哪些木棍被选中。第i位为1表示第i根木棍被选中为0表示未选中。设dp[mask]表示当选择的木棍集合为mask时这些木棍所能构成的所有可能的和的集合。但“所有可能的和”是一个集合直接存储比较麻烦。我们可以换一种定义这也是本题解法的精髓之一我们定义dp[mask]为当选择的木棍集合为mask时这些木棍能够拼出的、不超过其总长度一半的、最大的子集和。换句话说对于选中的木棍集合mask它的总长度是固定的记为sum[mask]。我们想把这些木棍再分成两堆希望两堆和相等。那么其中一堆的和最大能是多少这个最大值就是dp[mask]。如果dp[mask] * 2 sum[mask]那就说明集合mask能被完美分成和相等的两堆。但这样定义状态转移会非常复杂。更常见的、也是本题标准解法采用的是另一种思路枚举所有子集并计算其和然后寻找两个不相交的子集它们的和相等。具体算法步骤如下枚举所有可能的木棍选择方案即所有子集mask从1到(1n)-1计算每个子集的总长度sum[mask]。对于每个子集mask我们并不直接找另一个子集。而是思考如果我们最终答案的两个子集分别是A和B且sum(A) sum(B) S。那么A和B一定是某个更大集合C的子集并且C A ∪ Bsum(C) 2S。因此我们可以枚举所有子集C。对于每个C如果sum[C]是偶数那么潜在的目标S sum[C] / 2。接下来我们需要判断能否从集合C中选出一个子集A使得sum(A) S。如果能那么剩下的部分B C - A的和自然也是S。这就找到了一个合法的解。问题就转化为对于每个总和为偶数的集合C判断其是否能被划分为两个和相等的子集。这是一个经典的“子集和”问题可以用动态规划解决。但对于所有集合C都做一次DP复杂度太高。优化我们可以利用状态压缩一次预处理出所有子集的和并且用另一个DP数组f[mask]来表示集合mask能否被分成两个和相等的子集。但f[mask]的递推关系需要用到子集的信息。实际上本题最广为流传的解法采用了一种“枚举子集的子集”的技巧结合位运算可以在O(3^n)的时间内解决当n15时可行。其核心状态转移是dp[mask]表示集合mask是否能被划分成两个和相等的子集布尔值。 转移方程dp[mask] true当且仅当存在mask的一个非空真子集sub使得sum[sub] * 2 sum[mask]且dp[sub]和dp[mask ^ sub]都为真这个转移有点问题。更准确的递推关系是对于一个集合mask如果它的总和sum[mask]是奇数那么dp[mask] false。如果是偶数令目标target sum[mask] / 2。那么dp[mask] true当且仅当存在mask的一个子集sub使得sum[sub] target。因为如果存在这样的子集sub那么剩下的部分mask ^ sub的和自然也是target。所以问题又回到了判断一个集合mask中是否存在子集和为target。这可以用针对每个mask做一次子集和DP但这样整体复杂度是O(n * 2^n * 2^n)不可接受。突破口我们不必对每个mask都重新计算。我们可以用一个二维的DP或者更巧妙的是我们直接枚举所有子集并把子集和作为“状态”的一部分。最终可行的状态定义 设f[s]表示能否凑出总和s。这是一个经典的子集和问题可以用一维布尔数组dp[s]来表示通过遍历每个木棍来更新。但是这样我们只知道能否用所有木棍的某个子集凑出s却不知道具体是哪个子集也就无法判断两个和为s的子集是否不相交。因此我们需要把“子集”信息也编码进去。一种方法是使用bitset 优化的背包但这在C中更常见。在状态压缩中更直接的方法是 我们定义dp[mask]为子集mask的总和sum[mask]。 然后我们遍历所有可能的和S从大到小对于每个S我们检查是否存在两个不相交的子集mask1和mask2使得sum[mask1] S且sum[mask2] S。如果存在那么S就是一个可行解由于我们从大到小遍历第一个找到的S就是最大值。如何高效检查我们可以预处理一个映射unordered_mapint, vectorint键是和S值是和为S的所有子集对应的掩码mask。然后对于每个S遍历它的所有掩码对(mask1, mask2)检查是否满足(mask1 mask2) 0即不相交。如果满足则找到了答案。这个算法的时间复杂度主要在于枚举所有子集O(2^n)和存储映射以及对于每个S检查掩码对。当n15时子集数量为32768可以接受。检查掩码对最坏情况是O(k^2)其中k是和为S的子集数量。在木棍长度随机的情况下这个数量不会太大。3. 核心算法实现与代码精讲3.1 算法流程与步骤拆解基于上面的分析我们确定最终算法步骤如下读取输入获取木棍数量n和长度数组sticks。枚举所有子集并计算和使用一个循环mask从1遍历到(1 n) - 10代表空集跳过。对于每个mask计算其对应的木棍长度之和sum。可以通过遍历n个二进制位如果第i位为1则加上sticks[i]。更高效的方法是使用lowbit技巧或递推计算但n15时直接遍历也可行。将(sum, mask)这个配对存储起来。为了方便后续按和查找我们使用一个映射mapint, vectorint sumToMasks键为和sum值为一个列表存放所有和为sum的子集掩码。寻找最大可行解由于我们要找最大的S而S最大不会超过所有木棍总长度的一半因为两组和相等且木棍长度为正所以任何一组的和最多是总和的一半。我们可以先计算所有木棍的总和total_sum那么max_S_possible total_sum / 2。从max_S_possible开始向下遍历到1因为题目要求至少一根木棍所以S至少为最短木棍的长度但向下遍历到1更安全。对于每个候选的S在sumToMasks中找到键为S的掩码列表masks。如果masks的大小小于2说明不可能有两个和为S的子集跳过。否则遍历masks中的所有掩码对(mask_i, mask_j)i j检查是否满足(mask_i mask_j) 0。如果满足则说明找到了两个不相交的子集它们的和都是S。由于我们是从大到小遍历S所以第一个找到的满足条件的S就是答案直接输出并结束程序。输出结果如果遍历完所有S都没有找到满足条件的则输出0。3.2 C代码实现与逐行解析下面给出完整的C实现代码并附上详细注释。#include iostream #include vector #include map #include algorithm using namespace std; int main() { int n; cin n; vectorint sticks(n); for (int i 0; i n; i) { cin sticks[i]; } // 映射和 - 所有能凑出该和的子集掩码列表 mapint, vectorint sumToMasks; // 1. 枚举所有非空子集 (mask 从 1 到 2^n - 1) int totalStates 1 n; // 子集总数2^n for (int mask 1; mask totalStates; mask) { int currentSum 0; // 计算当前掩码 mask 对应的木棍长度之和 for (int i 0; i n; i) { // 检查第 i 根木棍是否在子集中 (mask 的第 i 位是否为 1) if (mask (1 i)) { currentSum sticks[i]; } } // 将当前掩码加入到对应和的列表中 sumToMasks[currentSum].push_back(mask); } // 计算所有木棍的总长度用于确定搜索上限 int totalSum 0; for (int len : sticks) { totalSum len; } // 最大可能的相等和不会超过总长度的一半 int maxPossible totalSum / 2; int answer 0; // 2. 从大到小遍历可能的和 S for (int S maxPossible; S 0; --S) { // 如果不存在和为 S 的子集或者子集数量少于2个则跳过 if (sumToMasks.find(S) sumToMasks.end()) { continue; } const vectorint masks sumToMasks[S]; int size masks.size(); if (size 2) { continue; // 至少需要两个子集才有可能不相交 } // 遍历所有掩码对寻找不相交的一对 bool found false; for (int i 0; i size !found; i) { for (int j i 1; j size !found; j) { // 关键检查两个子集没有公共元素 (按位与结果为0) if ((masks[i] masks[j]) 0) { found true; answer S; break; // 找到一对即可内层循环跳出 } } if (found) { break; // 外层循环跳出 } } if (found) { break; // 已经找到最大S跳出整个循环 } } cout answer endl; return 0; }代码关键点解析子集枚举 (for (int mask 1; mask totalStates; mask)):mask是一个整数它的二进制表示的第i位代表第i根木棍是否被选中。totalStates 1 n等于2^n所以循环遍历了所有非空子集从1开始。计算子集和: 内层循环for (int i 0; i n; i)检查mask的每一位。(mask (1 i))是一个位运算技巧1 i生成一个只有第i位是1的数与mask进行按位与操作结果非0当且仅当mask的第i位是1。数据结构mapint, vectorint: 使用map自动按键和排序但在这个算法中排序不是必须的因为我们是从大到小手动遍历S。也可以用unordered_map提高一点效率但影响不大。vectorint存储了所有能凑出该和的子集掩码。寻找不相交子集: 这是算法的核心步骤。对于给定的和S我们获取所有和为S的子集掩码列表masks。然后通过双重循环遍历所有可能的掩码对(i, j)。检查条件(masks[i] masks[j]) 0是关键。按位与运算的结果为0意味着两个掩码的二进制位没有同时为1的位置即两个子集没有包含任何相同的木棍满足题目“不相交”的要求。搜索顺序与剪枝: 我们从maxPossible总和的一半开始向下遍历S。一旦找到第一个满足条件的S它就是最大值立即跳出所有循环并输出。这保证了效率。同时在遍历掩码对时一旦找到一对满足条件的也立即跳出循环避免不必要的计算。3.3 算法复杂度与优化思考时间复杂度: 主要分为两部分。第一部分是枚举所有子集并计算和复杂度为O(n * 2^n)。因为对于每个mask共2^n个我们最多遍历n位来计算和。当n15时2^1532768n*2^n ≈ 15*32768 491520完全在可接受范围内。第二部分是查找最大S。最坏情况下需要遍历maxPossible个S约totalSum/2最大可能是所有木棍长度和的一半。对于每个S如果存在很多和为S的子集双重循环检查的复杂度是O(k^2)k是子集数量。在随机数据下k通常不会很大。最坏情况是所有木棍长度相同那么和为某个值的子集数量会非常多可能导致复杂度接近O(2^(2n))这是不可接受的。但蓝桥杯的评测数据通常会避免这种极端情况或者n较小。对于n15即使最坏情况k最大也就是C(15, 7)或C(15, 8)这个量级大约几千双重循环勉强可以接受但可能处于超时边缘。空间复杂度: 存储sumToMasks映射。最坏情况下每个子集都有一个唯一的和几乎不可能那么需要O(2^n)的空间。同样对于n15这是可以接受的。针对极端数据的优化思路 如果担心最坏情况超时可以考虑以下优化提前剪枝在枚举子集时如果currentSum已经大于maxPossible因为最终答案的S不会超过它可以跳过将该掩码加入映射或者直接不计算更大的mask不行因为子集和可能很大但两个不相交子集的和S小。不过如果单个子集的和已经超过maxPossible它绝对不可能成为最终答案S因为S要等于这个和而S maxPossible。所以我们可以只记录那些和 maxPossible的子集掩码。这能显著减少映射中的条目数尤其是当木棍长度较大时。使用哈希集存储掩码对于每个和S我们只关心是否存在两个不相交的掩码。我们可以用unordered_setint来存储掩码并在插入新掩码时检查是否与集合中已有的某个掩码不相交。但这需要遍历集合可能不比双重循环好。迭代加深搜索另一种思路是使用DFS搜索按木棍长度从大到小排序优先尝试大的木棍结合剪枝如当前和超过目标S则剪枝直接搜索两个和为S的不相交子集。从最大的可能S开始尝试。这种方法在n较大但解较早找到时可能更快。对于蓝桥杯的这道题通常的数据规模下上面给出的标准状态压缩解法已经足够通过。4. 关键难点与易错点剖析4.1 对“不相交”的理解与位运算检查这是本题最容易出错的地方。两个子集不相交意味着没有任何一根木棍同时属于两个子集。在代码中我们使用子集掩码mask一个整数来表示一个子集。两个子集不相交的充分必要条件是它们的掩码进行按位与运算的结果为0。错误检查示例假设n3,mask1 5 (二进制101)表示选了第0和第2根木棍。mask2 1 (二进制001)表示选了第0根木棍。mask1 mask2 101 001 001结果非0说明它们有公共元素第0根木棍因此不是不相交。正确的例子mask1 4 (二进制100)mask2 3 (二进制011)mask1 mask2 100 011 000结果为0说明它们没有公共元素。注意在循环中检查(masks[i] masks[j]) 0时务必注意运算符优先级。的优先级低于所以必须加上括号写成((masks[i] masks[j]) 0)。我习惯总是加上括号以避免任何歧义。4.2 空集与全集的处理题目要求每个玩家至少拿到一根木棍所以两个子集都必须是非空的。在我们的算法中我们枚举子集时从mask 1开始跳过了mask0空集。所以sumToMasks中存储的所有子集都是非空的。当我们检查一对掩码(mask_i, mask_j)时它们各自都是非空的。但是我们需要确保mask_i和mask_j的并集不会包含所有木棍吗不需要。题目没有要求木棍必须用完所以两个子集的并集可以是任意的子集甚至可以是全集。只要它们不相交且和相等即可。有一个边界情况如果存在一个子集mask其和S出现了两次但这两个“子集”实际上是同一个掩码这不可能因为我们在sumToMasks[S]的列表里存储的是掩码值同一个掩码只会被添加一次因为每个mask只枚举一次。所以列表中的掩码都是互不相同的。我们需要找的是两个不同的、不相交的掩码。4.3 搜索顺序与效率为什么从大到小遍历S因为题目要求的是最大的相等和。一旦我们找到一个满足条件的S它就是答案后续更小的S就不需要再检查了。这实现了有效的剪枝。一个常见的效率陷阱在找到答案后忘记及时跳出循环。如果继续遍历完所有的S和所有的掩码对在答案较大的情况下可能节省不了多少时间但在答案较小或者无解时会做大量无用功。务必在找到答案后使用break语句跳出多层循环。4.4 数据范围与整数溢出木棍的长度和n的范围需要根据题目具体说明。在我们的代码中currentSum和totalSum使用int类型。如果题目中木棍长度较大或n较多总和可能超出int范围约21亿。这时需要改用long long类型。在蓝桥杯OJ上通常需要观察题目描述或根据经验判断。如果题目没有明确说明但感觉可能很大使用long long是更安全的做法。5. 测试用例与调试技巧5.1 设计测试用例自己设计几个测试用例覆盖各种边界和典型情况是调试和确保代码正确性的关键。简单用例输入n3, sticks[1, 2, 3]分析总和为6。可能的分组{1,2}和{3}和分别为3和3。最大S3。预期输出3无解用例输入n3, sticks[1, 2, 4]分析总和为7。无法找到两个不相交的非空子集和相等。检查123145246单个元素1,2,4。没有任何两个不相交子集和相等。预期输出0所有元素相等输入n4, sticks[5, 5, 5, 5]分析总和20。最大S10例如任意两个木棍一组另外两个木棍一组。注意也可以一组一个木棍(5)另一组一个木棍(5)但S5不是最大。我们要找最大所以是10。预期输出10包含重复和输入n4, sticks[1, 1, 2, 2]分析总和6。可能的分组{1,2}和{1,2}注意虽然都是1和2但木棍是不同的个体所以掩码不同且不相交。S3。也可以{1,1}和{2}S2。最大是3。预期输出3最大规模测试用于估计时间输入n15生成15个随机正整数比如1~100。用程序跑一下感受时间。5.2 调试与验证输出中间变量在开发时可以打印sumToMaps的内容看看每个和对应哪些掩码。确保枚举和计算是正确的。验证位运算对于找到的答案S打印出满足条件的两个掩码mask_i和mask_j并手动解码它们分别对应哪些木棍计算其和验证是否都等于S且不相交。小规模暴力对拍对于n很小比如n10的情况可以写一个暴力枚举所有子集对的程序与你的优化算法对比结果确保正确性。6. 算法扩展与思维提升解决这道“无聊的逗”真正掌握的是状态压缩和子集枚举的技巧。这个技巧在算法竞赛中应用广泛例如旅行商问题(TSP)用dp[mask][i]表示访问过城市集合mask且当前在城市i的最短路径。精确覆盖问题可以用DLX算法但状态压缩也可以用于小规模情况。棋盘覆盖/状态表示在状压DP中用二进制位表示一行的放置状态。思维提升点从暴力到优化这道题清晰地展示了当暴力枚举 (2^n) 不可行时如何通过分析问题结构将原问题转化为枚举所有子集并利用哈希映射进行快速查询的模式。这是一种非常经典的“空间换时间”和“预处理”思想。位运算的熟练运用(1 i)、mask (1 i)、mask1 mask2这些操作是状态压缩DP的基石必须做到熟练于心。问题转化的艺术最初的问题描述可能比较模糊但通过一步步的推理我们将其转化为“寻找两个和相等且不相交的子集”进而转化为“对于每个和S检查是否存在两个不相交的子集其和均为S”。这种将复杂条件分解、逐步简化的能力至关重要。最后虽然这道题有标准的状压解法但在实际竞赛中如果n更大比如n302^30的枚举就不可行了。这时可能需要用到“折半搜索”Meet-in-the-Middle技术将木棍分成两半分别枚举所有子集的和然后通过排序和双指针在两个半区中寻找两个和相等的子集并检查它们是否不相交这需要额外记录子集掩码信息。这又是另一个层次的优化技巧了。理解这道题的基础解法是迈向这些更高级技巧的坚实一步。