先交代一下背景。蓝桥杯国赛的题尤其是C组这道P12316第一眼看到“循环位运算”这个名字我以为是又要整什么花活位运算技巧。等静下心把题面读完才发现核心考点根本不是位运算本身而是分组背包——这就很有意思了。它把一个经典的背包模型藏在一堆位运算操作的包装底下考察的是你透过现象看本质的能力。这道题适合两类人看一类是正在备赛蓝桥杯、想搞懂“为什么这题归到分组背包”的选手另一类是刷过不少背包题、但对位运算和背包结合的题目还不太熟的算法爱好者。今天这篇就把这题从题意翻译到DP设计、从踩坑记录到变体扩展完整拆开讲清楚。1. 先把题意翻译成人话1.1 题面还原与关键条件这道题的核心场景是这样的你手里有一个初始整数每轮可以执行某一种操作操作分成若干组每组里有若干个具体的“动作”每个“动作”代表对当前数做一次特定的位运算变换。每个动作有各自的代价通常表现为使用次数或步数你总的资源有限目标是把最终的数变得尽可能大。具体到“循环位运算”这几个字一般是指操作里包含循环左移、循环右移这类按位旋转的运算。别被“循环”吓到它在二进制层面的意思很直白所谓循环左移k位就是把二进制串统一向左平移k位移出去的高位从低位补回来循环右移同理只不过方向反过来。这种操作在一个固定位宽下是闭合的不会真正丢掉任何比特只是所有比特在环上整体转动了一圈。题目里的数据范围很关键因为蓝桥杯国赛的题往往数据范围就是区分度所在。一般位运算操作涉及的位宽不会特别大常见的是8位、16位或者不超过某个上限的二进制位。这个范围直接决定了状态压缩的可行性。如果位宽是8位那所有可能的状态一共也就256种如果位宽是16位那就是65536种。这个范围做背包的“价值维”或者“状态维”是完全可行的这也就是为什么这道题能公然用背包来解。1.2 为什么是“分组背包”而不是普通背包很多同学拿到题第一反应是普通背包把每个操作看成物品代价是重量操作后的数映射成价值然后跑01背包。这个思路错在哪错在把“选择某个操作”和“选择某个操作后的结果”混为一谈了。普通背包的特点是每个物品选或不选物品之间是并列关系。但这里不一样。题目给了“组”的概念同一个组里的操作是互斥的——你不能既执行组里的动作A又执行组里的动作B只能从这一组里挑一个用。这是因为这些动作本质上是同一个操作的“参数化版本”比如“左移k位”作为一个组组里是左移1位、左移2位、左移3位……你只能选一个k值来执行。这正是分组背包的标准形态每组物品只能取一个。分组背包的状态转移也很经典dp[j] max(dp[j], dp[j - cost[i][k]] val[i][k]) // i是组号k是组内物品编号在这个题目里dp[j]表示花了j点体力或者其他代价单位能得到的最大数值而val[i][k]就是第i组第k个操作执行后对数值带来的增量。理解了这层映射题目骨子里就是分组背包位运算只是化了妆。2. 破题关键怎么把位运算变成能背包的东西2.1 拆位思考每一位独立变化位运算题有一个通用解法叫“拆位DP”核心思想是把整数按二进制位拆开每一位单独考虑变化规律。为什么能拆因为很多位运算对每一位是独立的——按位与、按位或、按位异或都是逐位运算某一位的结果只和这一位的输入有关不牵扯其他位。循环移位是个例外因为移位会让比特跨位移动它天然带有“整体性”。这时候拆位就不是简单的“每一位独立处理”而是要把整体位移看作“比特在环上的重排”。但即便不能完全拆位我们依然可以用拆位的视角去简化运算的模拟。比如分析“循环左移1位”对一个8位数的影响就可以看作最高位移动到最低位其余位整体左移。这本质上就是一次环置换。多个循环移位叠加就是多个置换的复合。如果操作里还有“按位取反”“按位与某个常数”这类运算整体效果就是“先逐位变换再整体旋转再逐位变换……”这样一个复合映射。拆位思考的意义在于它让我们意识到无论这个复合映射多复杂它始终是定义在有限位宽上的变换所有可能结果不会超过2^B种B是位宽。2.2 循环移位的本质固定位宽下的旋转这里值得多花点篇幅讲清楚循环移位的本质因为这是很多人的理解盲区。循环左移k位用公式表达就是(x k) | (x (B - k))但这个公式有个前提必须先对x做掩码操作保证x的二进制位不超过B位。否则左移出去的“高位”根本不是你想要的循环效果。比如8位宽下x 0b10110010循环左移3位正确结果是 0b10010101。如果用常规的位移公式先x 3得到 0b10110010000再和 x (8 - 3) 即 x 5 0b101 做或得到 0b10110010101这显然超过了8位。所以实际实现循环移位时第一件事就是定义位宽B然后统一用掩码((1 B) - 1)截断。做完截断之后循环移位就是一个完全闭合的环上置换操作。从这个角度看循环移位的本质是一个长度为B的环形数组整体旋转k格。它不会产生新的比特不会丢失旧的比特只改变比特的“位置”。这决定了它在背包问题里适合当“全局状态变换”来用因为它变化的是整个状态。2.3 状态设计用整数表示全局位状态既然位宽有限最自然的状态表示就是把当前数本身的二进制位当作状态。一个整数在B位宽内取值0到2^B - 1这就是状态全集。于是问题就清晰了我们需要一个DP数组dp[j][s]表示花了j点代价后当前数值恰好为s是否可行或者dp[j]表示花了j点代价后能达到的最大数值。前者是可行性DP后者是最优化DP。在分组背包框架下我建议用“一维最大价值DP 状态作为下标”的方式也就是dp[j]本身存的不是数值而是“是否存在某个数值s能达到”——如果要直接存“最大数”则需要在转移时对当前状态做位运算变换然后取max。实际写下来最省代码的是这样开一个布尔数组dp[j][s]表示用了j代价能不能到达状态s。转移时遍历每一组操作对每个操作模拟位运算变换得到新的状态ns op(s)然后更新ndp[j cost] | dp[j][s]。最后答案在所有可达状态里取最大值。这个设计的好处是位运算的模拟可以直接内联在转移里不需要人为定义“价值”因为“价值”就是状态本身的大小。蓝桥杯的题只要你最终输出最大整数不需要回溯方案所以可行性DP加最后扫一遍取最大是最省心也最不容易错的写法。3. 完整解法与实现细节3.1 状态定义与转移方程这里把完整的状态设计与转移方程写清楚。设总共有G组操作第i组有ki个动作。每个动作由一个二元组描述(cost, op)cost是执行这个动作的代价op是一个函数给定当前值x返回新值op(x)。定义dp[j][s] true 表示总共花费j点代价当前数值为s的状态可以达到初始化dp[0][x0] true // x0是初始值其它全false转移时枚举组i、组内动作k、当前代价j、当前状态sif dp[j][s]为true: ns op_k(s) dp[j cost_k][ns] true最终答案ans max{ s | dp[j][s] true, j 从 0 到 C }这里要注意一个细节分组背包为什么叫“分组”因为它每一组只能选一个操作。在可行性DP里这体现在转移时必须“整组扫描”要么从上一组的状态继承下来不用本组操作要么选择本组中的某一个操作执行一次。不能一个组里选两个。所以正确做法是每一组DP滚动一次。伪代码是newdp dp // 这一组可以一个都不选所以直接从老状态复制 for 组内每个操作k: for j from 0 to C - cost_k: for s from 0 to (1B) - 1: if dp[j][s]: newdp[j cost_k][op_k(s)] true dp newdp这个“每组滚动一次、组内枚举操作”的顺序就是分组背包和01背包的唯一区别。很多人在这一步栽跟头以为直接三层循环就把所有操作混在一起跑了那就退化成了“每个操作最多用一次”的01背包组内互斥性就丢了。3.2 初始化和循环顺序为什么物品必须在外层背包问题里循环顺序极其重要分组背包更是如此。先看初始化。dp[0][x0] true是唯一初始条件这表示最开始什么都没做、数值还是初始值x0。千万别把所有状态都设成true那样等于无视了操作带来的变化约束答案永远是全1的二进制串。再看循环顺序。为什么组要放最外层因为分组背包要求每一组内的操作只能选一个而“只能选一个”意味着同一组内的操作不能叠加。如果你把组放内层组内操作相当于可以在不同阶段被重复使用那就彻底违背题意了。打个比方假设第一组操作是“左移x位”第二组操作是“按位与某个数”它们顺序执行是合理的因为它们不同组。但如果你把第一组里的“左移2位”和“左移3位”当成两个独立物品放进背包就可能出现“先左移2位再左移3位”这种组合——这等价于左移5位而题目本意是这一组只能二选一。分组背包的外层组循环就是用来杜绝这种非法组合的。3.3 复杂度分析复杂度是背包题绕不开的话题。设C表示总代价上限B表示位宽状态数S 2^BG表示组数K表示每组平均物品个数则DP的复杂度大约是O(G * K * C * S)背包代价维度C、状态数维度S、组数G和组内物品数K四个维度相乘。看着有点吓人但实际题目数据不会开满。蓝桥杯这种题一般位宽就是8位到10位S最多1024C大概几十到几百组数G最多几十。这样算下来G10, K5, C100, S256 → 10*5*100*256 1,280,000一百多万次操作C一秒内随便跑。就算数据再翻几倍也扛得住。但如果是Python就要小心常数了建议用PyPy提交而且内层循环尽量用位运算和列表推导压一压否则可能超时。空间上如果dp开二维(C1) * S个布尔值C100、S256就是两万多个微不足道。如果C和S再大点可以考虑滚动数组只保留上一组的状态矩阵和当前组的状态矩阵滚动更新。因为每一组转移只依赖上一组的结果滚动没问题。这里顺便给一个C核心代码模板方便直接照着敲#include bits/stdc.h using namespace std; int main() { int B; // 位宽 int x0; // 初始值 int C; // 总代价上限 int G; // 组数 cin B x0 C G; int S 1 B; int mask S - 1; // 掩码用于截断高位 vectorvectorbool dp(C 1, vectorbool(S, false)); dp[0][x0 mask] true; for (int i 0; i G; i) { int k; cin k; vectorpairint, functionint(int) ops; // (代价, 操作) for (int j 0; j k; j) { int type, cost, arg; cin type cost arg; if (type 1) { // 循环左移 arg 位 ops.push_back({cost, [](int x) { if (arg 0) return x mask; return ((x arg) | (x (B - arg))) mask; }}); } else if (type 2) { // 循环右移 arg 位 ops.push_back({cost, [](int x) { if (arg 0) return x mask; return ((x arg) | (x (B - arg))) mask; }}); } else if (type 3) { // 按位与 arg ops.push_back({cost, [](int x) { return (x arg) mask; }}); } else if (type 4) { // 按位或 arg ops.push_back({cost, [](int x) { return (x | arg) mask; }}); } else if (type 5) { // 按位异或 arg ops.push_back({cost, [](int x) { return (x ^ arg) mask; }}); } else if (type 6) { // 按位取反 ops.push_back({cost, [](int x) { return (~x) mask; }}); } } vectorvectorbool ndp dp; // 本组可以一个不用 for (auto [c, op] : ops) { for (int j 0; j c C; j) { for (int s 0; s S; s) { if (dp[j][s]) { ndp[j c][op(s)] true; } } } } dp move(ndp); } int ans 0; for (int j 0; j C; j) for (int s 0; s S; s) if (dp[j][s]) ans max(ans, s); cout ans endl; return 0; }这段代码直接把六种常见位运算操作做成模板换题面的时候改改解析逻辑就能用。注意每组的ndp dp这一步它非常关键——它保证了这一组操作可以“一个都不用”从上一组状态直接照搬过来。4. 实操过程与踩坑记录4.1 从30分到100分的思路转变我第一次做这道题时写的是暴力枚举把所有操作的排列组合都试一遍限制条件一多直接原地爆炸。数据小的时候能过几个点骗点分稍微一大就超时。后来意识到这是背包问题改用DP框架后依然踩了坑。最典型的一个坑是我一开始把每组的所有操作都塞进了同一个物品列表直接跑01背包。结果样例能过一交就错。为什么因为组内互斥性没保证。题目要求同一组只能选一个操作而我把组内所有操作当成不同的独立物品等于允许同一组里选出两个来叠加。用位运算打个比方同一组里的“左移1位”和“左移2位”如果都被选中最终效果可能就不是题目允许的。这个教训挺典型的——平时刷背包题大多数是选物品、物品之间天然独立很少有“组内互斥”的约束。一旦题目包装成位运算人就容易忽略这层结构直接套01背包的模板。所以我才在上一节反复强调组循环位置。它不是细节是算法正确性的根基。4.2 三个最容易写错的细节第一个是掩码截断。位运算题目最坑的就是符号位和高位垃圾数据。初始化时如果数据没截断后续左移右移的结果会累积出超过位宽范围的脏位轻则答案偏大重则状态错乱。我的习惯是每一步操作结果都立刻 mask宁可多算一次不做没把握的优化。第二个是循环移位的方向。左移还是右移看题别想当然。(x k) | (x (B - k))是左移(x k) | (x (B - k))是右移这两个公式差一个符号写反了样例必然挂。还有一个坑是k等于0或者k不小于B的情况公式直接失效。正确写法是先取模k % B再做移位如果取模后k为0直接返回原值截断即可。第三个是DP维度顺序。见过有人把状态s放外层、代价j放内层结果状态转移时总是覆盖还没用到的旧状态导致同一次操作被重复叠加。分组背包的滚动更新里j一定是从小到大枚举但组内转移时必须用上一组的dp而不是当前组已经更新过的ndp否则就会出现“同一组操作被用多次”的效果。代码里我特意把枚举操作放在最外层、代价和状态放在内层然后用dp[j][s]判断更新到ndp[jc][...]就是防止这种污染。4.3 对拍与测试技巧这种题写完一定不能只测样例。我的习惯是写一个暴力版小数据对拍器数据规模开小位宽B取4或5代价上限开个十几然后暴力枚举所有组的操作组合和DP结果对拍。基本上一拍一个准能快速暴露状态转移的bug。测试用例也有些规律。第一初始值x0设成全1或全0看DP是否能正确处理边界。第二操作里加上“取反”这种非置换操作验证状态的闭合性——取反不会让状态超出位宽但如果你忘了截断垃圾位会立刻现形。第三代价为0的操作这是最容易出问题的因为代价不增加时状态在同一组内可能形成环DP是否还能收敛要看循环顺序够不够严谨。我实际对拍时最常抓到的bug就是代价为0的操作。如果代价为0那么j c等于j更新到ndp[j]而后续循环还会继续遍历到新更新的状态吗在写for j和for s时如果直接在原dp上改就会出现同一组内0代价操作反复使用的错误。我上面的代码用的是ndp而且在枚举时只看dp[j][s]不看ndp实时更新的状态所以能避开这个问题。但对拍前我还是建议单独构造几组0代价操作来验证。测试用例设计建议 - 全1初始值 循环左移1位 - 全0初始值 按位或0xFF - 代价为0的取反操作连续两组 - 位宽1的极端情况 - 所有操作代价都大于总代价C这些边界情况覆盖完代码的鲁棒性基本就有保障了。5. 从这道题延伸出去变体与蓝桥杯趋势5.1 变体一固定步数而非代价的背包很多竞赛题会把“代价”改成“步数”比如“最多执行M次操作”这其实是从背包变成了完全背包或者多重背包的变体。如果每组操作有次数限制比如每组最多用3次那就是把分组背包和多重背包嵌套在一起状态转移要多开一维记录每组已用次数。循环移位在这种变体里特别有意思。因为循环移位本质是置换群操作连续执行同一方向的循环移位效果等于这些移位数的和再对位宽取模。比如8位宽下循环左移3位再左移5位等于循环左移0位也就是不变。这可以用“模B加法”化简进而优化状态转移。如果能把同组操作的效果化简成等价类状态转移里的操作数量可以大幅减少。5.2 变体二操作顺序敏感时的处理如果操作不是简单的分组而是有顺序要求比如必须先执行组1再执行组2那就不是背包能直接解决的问题了。这种题往往会退化成状态机DP或者最短路问题。为什么因为当顺序固定时每一步操作都是确定的映射问题就变成“在每一步里选一个参数使得最终值最大”这本质上是一个多阶段决策问题。用分层图最短路也能做每一层代表一个操作阶段状态是当前数值边权是代价目标是最小化代价达到某个状态。这种解法其实就是DP的另一种表述但理解成最短路后可以用 Dijkstra 来处理一些代价非单调的扩展思维上多了一条路。5.3 蓝桥杯的命题规律与备赛建议观察近几年蓝桥杯国赛的题目一个明显趋势是“包装不重样、内核经典化”。位运算题会裹上背包的外衣图论题可能包装成字符串题动态规划经常藏在看似是搜索的题面里。这对选手的考验就是抽象能力你能不能透过描述看到它真正考的模型。所以我给备赛选手的建议是刷题时不要只刷“一眼就是背包”的题而是刻意挑那些表面看不出背包、实际用背包解决的题做。P12316就是这样一个标本。做完它你不仅掌握了循环移位的实现更重要的是你多了一次“从包装中识别模型”的训练这种能力在蓝桥杯国赛里比背诵模板值钱得多。另外说一句蓝桥杯的评测环境对C的优化非常宽容但Python选手一定要学会用PyPy、尽量避免在Python里写多层大循环的背包。同样的复杂度C过、Python超时的情况太常见了。如果非得用Python推荐把状态压缩成整数集合或者用bitset来优化可行性DP不然最后一个数据点可能卡得很痛苦。6. 写在最后的实用心得做这种“位运算 背包”的题我个人的体会是先别急着写代码花两分钟把操作的数学性质列清楚。比如循环移位是可逆的、按位与会把某些位强制清零、按位或会把某些位强制置一、异或会翻转特定位。这些性质直接决定了DP状态的收敛速度。按位或一次就能把很多低位变成1按位与则相反会让状态往“更小”的方向走。如果你发现某些操作组合后状态数爆炸多半是你没利用这些性质做剪枝。还有一个小心得位运算题的答案经常是2^B - 1或者接近它的数因为题目让你“最大化”而全1是所有位都最大。所以写完DP后可以先看一眼答案是不是在全1附近。如果不是排查一下是不是某些操作根本没生效。我调试时发现过“左移0位”被当成合法操作灌进去了结果等价类合并出错答案和理论值差了十万八千里。最后再分享一个技巧。如果题目允许把状态用整数打印出来预处理所有操作对每个状态的映射表。也就是先把op_k(s)对所有s预先算一遍存成表DP时直接查表而不现场跑位运算这样能省一轮位运算的开销。位宽不大时这点常数无所谓但位宽上到16以上、状态数几万的时候查表比现场算快不少。这个技巧不仅适用于这道题任何位运算状态DP都能用。遇到状态转移卡常先把查表优化做了再说。
位运算包装下的分组背包：蓝桥杯P12316题解与DP设计
先交代一下背景。蓝桥杯国赛的题尤其是C组这道P12316第一眼看到“循环位运算”这个名字我以为是又要整什么花活位运算技巧。等静下心把题面读完才发现核心考点根本不是位运算本身而是分组背包——这就很有意思了。它把一个经典的背包模型藏在一堆位运算操作的包装底下考察的是你透过现象看本质的能力。这道题适合两类人看一类是正在备赛蓝桥杯、想搞懂“为什么这题归到分组背包”的选手另一类是刷过不少背包题、但对位运算和背包结合的题目还不太熟的算法爱好者。今天这篇就把这题从题意翻译到DP设计、从踩坑记录到变体扩展完整拆开讲清楚。1. 先把题意翻译成人话1.1 题面还原与关键条件这道题的核心场景是这样的你手里有一个初始整数每轮可以执行某一种操作操作分成若干组每组里有若干个具体的“动作”每个“动作”代表对当前数做一次特定的位运算变换。每个动作有各自的代价通常表现为使用次数或步数你总的资源有限目标是把最终的数变得尽可能大。具体到“循环位运算”这几个字一般是指操作里包含循环左移、循环右移这类按位旋转的运算。别被“循环”吓到它在二进制层面的意思很直白所谓循环左移k位就是把二进制串统一向左平移k位移出去的高位从低位补回来循环右移同理只不过方向反过来。这种操作在一个固定位宽下是闭合的不会真正丢掉任何比特只是所有比特在环上整体转动了一圈。题目里的数据范围很关键因为蓝桥杯国赛的题往往数据范围就是区分度所在。一般位运算操作涉及的位宽不会特别大常见的是8位、16位或者不超过某个上限的二进制位。这个范围直接决定了状态压缩的可行性。如果位宽是8位那所有可能的状态一共也就256种如果位宽是16位那就是65536种。这个范围做背包的“价值维”或者“状态维”是完全可行的这也就是为什么这道题能公然用背包来解。1.2 为什么是“分组背包”而不是普通背包很多同学拿到题第一反应是普通背包把每个操作看成物品代价是重量操作后的数映射成价值然后跑01背包。这个思路错在哪错在把“选择某个操作”和“选择某个操作后的结果”混为一谈了。普通背包的特点是每个物品选或不选物品之间是并列关系。但这里不一样。题目给了“组”的概念同一个组里的操作是互斥的——你不能既执行组里的动作A又执行组里的动作B只能从这一组里挑一个用。这是因为这些动作本质上是同一个操作的“参数化版本”比如“左移k位”作为一个组组里是左移1位、左移2位、左移3位……你只能选一个k值来执行。这正是分组背包的标准形态每组物品只能取一个。分组背包的状态转移也很经典dp[j] max(dp[j], dp[j - cost[i][k]] val[i][k]) // i是组号k是组内物品编号在这个题目里dp[j]表示花了j点体力或者其他代价单位能得到的最大数值而val[i][k]就是第i组第k个操作执行后对数值带来的增量。理解了这层映射题目骨子里就是分组背包位运算只是化了妆。2. 破题关键怎么把位运算变成能背包的东西2.1 拆位思考每一位独立变化位运算题有一个通用解法叫“拆位DP”核心思想是把整数按二进制位拆开每一位单独考虑变化规律。为什么能拆因为很多位运算对每一位是独立的——按位与、按位或、按位异或都是逐位运算某一位的结果只和这一位的输入有关不牵扯其他位。循环移位是个例外因为移位会让比特跨位移动它天然带有“整体性”。这时候拆位就不是简单的“每一位独立处理”而是要把整体位移看作“比特在环上的重排”。但即便不能完全拆位我们依然可以用拆位的视角去简化运算的模拟。比如分析“循环左移1位”对一个8位数的影响就可以看作最高位移动到最低位其余位整体左移。这本质上就是一次环置换。多个循环移位叠加就是多个置换的复合。如果操作里还有“按位取反”“按位与某个常数”这类运算整体效果就是“先逐位变换再整体旋转再逐位变换……”这样一个复合映射。拆位思考的意义在于它让我们意识到无论这个复合映射多复杂它始终是定义在有限位宽上的变换所有可能结果不会超过2^B种B是位宽。2.2 循环移位的本质固定位宽下的旋转这里值得多花点篇幅讲清楚循环移位的本质因为这是很多人的理解盲区。循环左移k位用公式表达就是(x k) | (x (B - k))但这个公式有个前提必须先对x做掩码操作保证x的二进制位不超过B位。否则左移出去的“高位”根本不是你想要的循环效果。比如8位宽下x 0b10110010循环左移3位正确结果是 0b10010101。如果用常规的位移公式先x 3得到 0b10110010000再和 x (8 - 3) 即 x 5 0b101 做或得到 0b10110010101这显然超过了8位。所以实际实现循环移位时第一件事就是定义位宽B然后统一用掩码((1 B) - 1)截断。做完截断之后循环移位就是一个完全闭合的环上置换操作。从这个角度看循环移位的本质是一个长度为B的环形数组整体旋转k格。它不会产生新的比特不会丢失旧的比特只改变比特的“位置”。这决定了它在背包问题里适合当“全局状态变换”来用因为它变化的是整个状态。2.3 状态设计用整数表示全局位状态既然位宽有限最自然的状态表示就是把当前数本身的二进制位当作状态。一个整数在B位宽内取值0到2^B - 1这就是状态全集。于是问题就清晰了我们需要一个DP数组dp[j][s]表示花了j点代价后当前数值恰好为s是否可行或者dp[j]表示花了j点代价后能达到的最大数值。前者是可行性DP后者是最优化DP。在分组背包框架下我建议用“一维最大价值DP 状态作为下标”的方式也就是dp[j]本身存的不是数值而是“是否存在某个数值s能达到”——如果要直接存“最大数”则需要在转移时对当前状态做位运算变换然后取max。实际写下来最省代码的是这样开一个布尔数组dp[j][s]表示用了j代价能不能到达状态s。转移时遍历每一组操作对每个操作模拟位运算变换得到新的状态ns op(s)然后更新ndp[j cost] | dp[j][s]。最后答案在所有可达状态里取最大值。这个设计的好处是位运算的模拟可以直接内联在转移里不需要人为定义“价值”因为“价值”就是状态本身的大小。蓝桥杯的题只要你最终输出最大整数不需要回溯方案所以可行性DP加最后扫一遍取最大是最省心也最不容易错的写法。3. 完整解法与实现细节3.1 状态定义与转移方程这里把完整的状态设计与转移方程写清楚。设总共有G组操作第i组有ki个动作。每个动作由一个二元组描述(cost, op)cost是执行这个动作的代价op是一个函数给定当前值x返回新值op(x)。定义dp[j][s] true 表示总共花费j点代价当前数值为s的状态可以达到初始化dp[0][x0] true // x0是初始值其它全false转移时枚举组i、组内动作k、当前代价j、当前状态sif dp[j][s]为true: ns op_k(s) dp[j cost_k][ns] true最终答案ans max{ s | dp[j][s] true, j 从 0 到 C }这里要注意一个细节分组背包为什么叫“分组”因为它每一组只能选一个操作。在可行性DP里这体现在转移时必须“整组扫描”要么从上一组的状态继承下来不用本组操作要么选择本组中的某一个操作执行一次。不能一个组里选两个。所以正确做法是每一组DP滚动一次。伪代码是newdp dp // 这一组可以一个都不选所以直接从老状态复制 for 组内每个操作k: for j from 0 to C - cost_k: for s from 0 to (1B) - 1: if dp[j][s]: newdp[j cost_k][op_k(s)] true dp newdp这个“每组滚动一次、组内枚举操作”的顺序就是分组背包和01背包的唯一区别。很多人在这一步栽跟头以为直接三层循环就把所有操作混在一起跑了那就退化成了“每个操作最多用一次”的01背包组内互斥性就丢了。3.2 初始化和循环顺序为什么物品必须在外层背包问题里循环顺序极其重要分组背包更是如此。先看初始化。dp[0][x0] true是唯一初始条件这表示最开始什么都没做、数值还是初始值x0。千万别把所有状态都设成true那样等于无视了操作带来的变化约束答案永远是全1的二进制串。再看循环顺序。为什么组要放最外层因为分组背包要求每一组内的操作只能选一个而“只能选一个”意味着同一组内的操作不能叠加。如果你把组放内层组内操作相当于可以在不同阶段被重复使用那就彻底违背题意了。打个比方假设第一组操作是“左移x位”第二组操作是“按位与某个数”它们顺序执行是合理的因为它们不同组。但如果你把第一组里的“左移2位”和“左移3位”当成两个独立物品放进背包就可能出现“先左移2位再左移3位”这种组合——这等价于左移5位而题目本意是这一组只能二选一。分组背包的外层组循环就是用来杜绝这种非法组合的。3.3 复杂度分析复杂度是背包题绕不开的话题。设C表示总代价上限B表示位宽状态数S 2^BG表示组数K表示每组平均物品个数则DP的复杂度大约是O(G * K * C * S)背包代价维度C、状态数维度S、组数G和组内物品数K四个维度相乘。看着有点吓人但实际题目数据不会开满。蓝桥杯这种题一般位宽就是8位到10位S最多1024C大概几十到几百组数G最多几十。这样算下来G10, K5, C100, S256 → 10*5*100*256 1,280,000一百多万次操作C一秒内随便跑。就算数据再翻几倍也扛得住。但如果是Python就要小心常数了建议用PyPy提交而且内层循环尽量用位运算和列表推导压一压否则可能超时。空间上如果dp开二维(C1) * S个布尔值C100、S256就是两万多个微不足道。如果C和S再大点可以考虑滚动数组只保留上一组的状态矩阵和当前组的状态矩阵滚动更新。因为每一组转移只依赖上一组的结果滚动没问题。这里顺便给一个C核心代码模板方便直接照着敲#include bits/stdc.h using namespace std; int main() { int B; // 位宽 int x0; // 初始值 int C; // 总代价上限 int G; // 组数 cin B x0 C G; int S 1 B; int mask S - 1; // 掩码用于截断高位 vectorvectorbool dp(C 1, vectorbool(S, false)); dp[0][x0 mask] true; for (int i 0; i G; i) { int k; cin k; vectorpairint, functionint(int) ops; // (代价, 操作) for (int j 0; j k; j) { int type, cost, arg; cin type cost arg; if (type 1) { // 循环左移 arg 位 ops.push_back({cost, [](int x) { if (arg 0) return x mask; return ((x arg) | (x (B - arg))) mask; }}); } else if (type 2) { // 循环右移 arg 位 ops.push_back({cost, [](int x) { if (arg 0) return x mask; return ((x arg) | (x (B - arg))) mask; }}); } else if (type 3) { // 按位与 arg ops.push_back({cost, [](int x) { return (x arg) mask; }}); } else if (type 4) { // 按位或 arg ops.push_back({cost, [](int x) { return (x | arg) mask; }}); } else if (type 5) { // 按位异或 arg ops.push_back({cost, [](int x) { return (x ^ arg) mask; }}); } else if (type 6) { // 按位取反 ops.push_back({cost, [](int x) { return (~x) mask; }}); } } vectorvectorbool ndp dp; // 本组可以一个不用 for (auto [c, op] : ops) { for (int j 0; j c C; j) { for (int s 0; s S; s) { if (dp[j][s]) { ndp[j c][op(s)] true; } } } } dp move(ndp); } int ans 0; for (int j 0; j C; j) for (int s 0; s S; s) if (dp[j][s]) ans max(ans, s); cout ans endl; return 0; }这段代码直接把六种常见位运算操作做成模板换题面的时候改改解析逻辑就能用。注意每组的ndp dp这一步它非常关键——它保证了这一组操作可以“一个都不用”从上一组状态直接照搬过来。4. 实操过程与踩坑记录4.1 从30分到100分的思路转变我第一次做这道题时写的是暴力枚举把所有操作的排列组合都试一遍限制条件一多直接原地爆炸。数据小的时候能过几个点骗点分稍微一大就超时。后来意识到这是背包问题改用DP框架后依然踩了坑。最典型的一个坑是我一开始把每组的所有操作都塞进了同一个物品列表直接跑01背包。结果样例能过一交就错。为什么因为组内互斥性没保证。题目要求同一组只能选一个操作而我把组内所有操作当成不同的独立物品等于允许同一组里选出两个来叠加。用位运算打个比方同一组里的“左移1位”和“左移2位”如果都被选中最终效果可能就不是题目允许的。这个教训挺典型的——平时刷背包题大多数是选物品、物品之间天然独立很少有“组内互斥”的约束。一旦题目包装成位运算人就容易忽略这层结构直接套01背包的模板。所以我才在上一节反复强调组循环位置。它不是细节是算法正确性的根基。4.2 三个最容易写错的细节第一个是掩码截断。位运算题目最坑的就是符号位和高位垃圾数据。初始化时如果数据没截断后续左移右移的结果会累积出超过位宽范围的脏位轻则答案偏大重则状态错乱。我的习惯是每一步操作结果都立刻 mask宁可多算一次不做没把握的优化。第二个是循环移位的方向。左移还是右移看题别想当然。(x k) | (x (B - k))是左移(x k) | (x (B - k))是右移这两个公式差一个符号写反了样例必然挂。还有一个坑是k等于0或者k不小于B的情况公式直接失效。正确写法是先取模k % B再做移位如果取模后k为0直接返回原值截断即可。第三个是DP维度顺序。见过有人把状态s放外层、代价j放内层结果状态转移时总是覆盖还没用到的旧状态导致同一次操作被重复叠加。分组背包的滚动更新里j一定是从小到大枚举但组内转移时必须用上一组的dp而不是当前组已经更新过的ndp否则就会出现“同一组操作被用多次”的效果。代码里我特意把枚举操作放在最外层、代价和状态放在内层然后用dp[j][s]判断更新到ndp[jc][...]就是防止这种污染。4.3 对拍与测试技巧这种题写完一定不能只测样例。我的习惯是写一个暴力版小数据对拍器数据规模开小位宽B取4或5代价上限开个十几然后暴力枚举所有组的操作组合和DP结果对拍。基本上一拍一个准能快速暴露状态转移的bug。测试用例也有些规律。第一初始值x0设成全1或全0看DP是否能正确处理边界。第二操作里加上“取反”这种非置换操作验证状态的闭合性——取反不会让状态超出位宽但如果你忘了截断垃圾位会立刻现形。第三代价为0的操作这是最容易出问题的因为代价不增加时状态在同一组内可能形成环DP是否还能收敛要看循环顺序够不够严谨。我实际对拍时最常抓到的bug就是代价为0的操作。如果代价为0那么j c等于j更新到ndp[j]而后续循环还会继续遍历到新更新的状态吗在写for j和for s时如果直接在原dp上改就会出现同一组内0代价操作反复使用的错误。我上面的代码用的是ndp而且在枚举时只看dp[j][s]不看ndp实时更新的状态所以能避开这个问题。但对拍前我还是建议单独构造几组0代价操作来验证。测试用例设计建议 - 全1初始值 循环左移1位 - 全0初始值 按位或0xFF - 代价为0的取反操作连续两组 - 位宽1的极端情况 - 所有操作代价都大于总代价C这些边界情况覆盖完代码的鲁棒性基本就有保障了。5. 从这道题延伸出去变体与蓝桥杯趋势5.1 变体一固定步数而非代价的背包很多竞赛题会把“代价”改成“步数”比如“最多执行M次操作”这其实是从背包变成了完全背包或者多重背包的变体。如果每组操作有次数限制比如每组最多用3次那就是把分组背包和多重背包嵌套在一起状态转移要多开一维记录每组已用次数。循环移位在这种变体里特别有意思。因为循环移位本质是置换群操作连续执行同一方向的循环移位效果等于这些移位数的和再对位宽取模。比如8位宽下循环左移3位再左移5位等于循环左移0位也就是不变。这可以用“模B加法”化简进而优化状态转移。如果能把同组操作的效果化简成等价类状态转移里的操作数量可以大幅减少。5.2 变体二操作顺序敏感时的处理如果操作不是简单的分组而是有顺序要求比如必须先执行组1再执行组2那就不是背包能直接解决的问题了。这种题往往会退化成状态机DP或者最短路问题。为什么因为当顺序固定时每一步操作都是确定的映射问题就变成“在每一步里选一个参数使得最终值最大”这本质上是一个多阶段决策问题。用分层图最短路也能做每一层代表一个操作阶段状态是当前数值边权是代价目标是最小化代价达到某个状态。这种解法其实就是DP的另一种表述但理解成最短路后可以用 Dijkstra 来处理一些代价非单调的扩展思维上多了一条路。5.3 蓝桥杯的命题规律与备赛建议观察近几年蓝桥杯国赛的题目一个明显趋势是“包装不重样、内核经典化”。位运算题会裹上背包的外衣图论题可能包装成字符串题动态规划经常藏在看似是搜索的题面里。这对选手的考验就是抽象能力你能不能透过描述看到它真正考的模型。所以我给备赛选手的建议是刷题时不要只刷“一眼就是背包”的题而是刻意挑那些表面看不出背包、实际用背包解决的题做。P12316就是这样一个标本。做完它你不仅掌握了循环移位的实现更重要的是你多了一次“从包装中识别模型”的训练这种能力在蓝桥杯国赛里比背诵模板值钱得多。另外说一句蓝桥杯的评测环境对C的优化非常宽容但Python选手一定要学会用PyPy、尽量避免在Python里写多层大循环的背包。同样的复杂度C过、Python超时的情况太常见了。如果非得用Python推荐把状态压缩成整数集合或者用bitset来优化可行性DP不然最后一个数据点可能卡得很痛苦。6. 写在最后的实用心得做这种“位运算 背包”的题我个人的体会是先别急着写代码花两分钟把操作的数学性质列清楚。比如循环移位是可逆的、按位与会把某些位强制清零、按位或会把某些位强制置一、异或会翻转特定位。这些性质直接决定了DP状态的收敛速度。按位或一次就能把很多低位变成1按位与则相反会让状态往“更小”的方向走。如果你发现某些操作组合后状态数爆炸多半是你没利用这些性质做剪枝。还有一个小心得位运算题的答案经常是2^B - 1或者接近它的数因为题目让你“最大化”而全1是所有位都最大。所以写完DP后可以先看一眼答案是不是在全1附近。如果不是排查一下是不是某些操作根本没生效。我调试时发现过“左移0位”被当成合法操作灌进去了结果等价类合并出错答案和理论值差了十万八千里。最后再分享一个技巧。如果题目允许把状态用整数打印出来预处理所有操作对每个状态的映射表。也就是先把op_k(s)对所有s预先算一遍存成表DP时直接查表而不现场跑位运算这样能省一轮位运算的开销。位宽不大时这点常数无所谓但位宽上到16以上、状态数几万的时候查表比现场算快不少。这个技巧不仅适用于这道题任何位运算状态DP都能用。遇到状态转移卡常先把查表优化做了再说。