先交代一下背景。藍橋杯國賽的題尤其是C組這道P12316第一眼看到“循環(huán)位運算”這個名字我以為是又要整什么花活位運算技巧。等靜下心把題面讀完才發(fā)現(xiàn)核心考點根本不是位運算本身而是分組背包——這就很有意思了。它把一個經(jīng)典的背包模型藏在一堆位運算操作的包裝底下考察的是你透過現(xiàn)象看本質(zhì)的能力。這道題適合兩類人看一類是正在備賽藍橋杯、想搞懂“為什么這題歸到分組背包”的選手另一類是刷過不少背包題、但對位運算和背包結(jié)合的題目還不太熟的算法愛好者。今天這篇就把這題從題意翻譯到DP設(shè)計、從踩坑記錄到變體擴展完整拆開講清楚。1. 先把題意翻譯成人話1.1 題面還原與關(guān)鍵條件這道題的核心場景是這樣的你手里有一個初始整數(shù)每輪可以執(zhí)行某一種操作操作分成若干組每組里有若干個具體的“動作”每個“動作”代表對當(dāng)前數(shù)做一次特定的位運算變換。每個動作有各自的代價通常表現(xiàn)為使用次數(shù)或步數(shù)你總的資源有限目標(biāo)是把最終的數(shù)變得盡可能大。具體到“循環(huán)位運算”這幾個字一般是指操作里包含循環(huán)左移、循環(huán)右移這類按位旋轉(zhuǎn)的運算。別被“循環(huán)”嚇到它在二進制層面的意思很直白所謂循環(huán)左移k位就是把二進制串統(tǒng)一向左平移k位移出去的高位從低位補回來循環(huán)右移同理只不過方向反過來。這種操作在一個固定位寬下是閉合的不會真正丟掉任何比特只是所有比特在環(huán)上整體轉(zhuǎn)動了一圈。題目里的數(shù)據(jù)范圍很關(guān)鍵因為藍橋杯國賽的題往往數(shù)據(jù)范圍就是區(qū)分度所在。一般位運算操作涉及的位寬不會特別大常見的是8位、16位或者不超過某個上限的二進制位。這個范圍直接決定了狀態(tài)壓縮的可行性。如果位寬是8位那所有可能的狀態(tài)一共也就256種如果位寬是16位那就是65536種。這個范圍做背包的“價值維”或者“狀態(tài)維”是完全可行的這也就是為什么這道題能公然用背包來解。1.2 為什么是“分組背包”而不是普通背包很多同學(xué)拿到題第一反應(yīng)是普通背包把每個操作看成物品代價是重量操作后的數(shù)映射成價值然后跑01背包。這個思路錯在哪錯在把“選擇某個操作”和“選擇某個操作后的結(jié)果”混為一談了。普通背包的特點是每個物品選或不選物品之間是并列關(guān)系。但這里不一樣。題目給了“組”的概念同一個組里的操作是互斥的——你不能既執(zhí)行組里的動作A又執(zhí)行組里的動作B只能從這一組里挑一個用。這是因為這些動作本質(zhì)上是同一個操作的“參數(shù)化版本”比如“左移k位”作為一個組組里是左移1位、左移2位、左移3位……你只能選一個k值來執(zhí)行。這正是分組背包的標(biāo)準形態(tài)每組物品只能取一個。分組背包的狀態(tài)轉(zhuǎn)移也很經(jīng)典dp[j] max(dp[j], dp[j - cost[i][k]] val[i][k]) // i是組號k是組內(nèi)物品編號在這個題目里dp[j]表示花了j點體力或者其他代價單位能得到的最大數(shù)值而val[i][k]就是第i組第k個操作執(zhí)行后對數(shù)值帶來的增量。理解了這層映射題目骨子里就是分組背包位運算只是化了妝。2. 破題關(guān)鍵怎么把位運算變成能背包的東西2.1 拆位思考每一位獨立變化位運算題有一個通用解法叫“拆位DP”核心思想是把整數(shù)按二進制位拆開每一位單獨考慮變化規(guī)律。為什么能拆因為很多位運算對每一位是獨立的——按位與、按位或、按位異或都是逐位運算某一位的結(jié)果只和這一位的輸入有關(guān)不牽扯其他位。循環(huán)移位是個例外因為移位會讓比特跨位移動它天然帶有“整體性”。這時候拆位就不是簡單的“每一位獨立處理”而是要把整體位移看作“比特在環(huán)上的重排”。但即便不能完全拆位我們依然可以用拆位的視角去簡化運算的模擬。比如分析“循環(huán)左移1位”對一個8位數(shù)的影響就可以看作最高位移動到最低位其余位整體左移。這本質(zhì)上就是一次環(huán)置換。多個循環(huán)移位疊加就是多個置換的復(fù)合。如果操作里還有“按位取反”“按位與某個常數(shù)”這類運算整體效果就是“先逐位變換再整體旋轉(zhuǎn)再逐位變換……”這樣一個復(fù)合映射。拆位思考的意義在于它讓我們意識到無論這個復(fù)合映射多復(fù)雜它始終是定義在有限位寬上的變換所有可能結(jié)果不會超過2^B種B是位寬。2.2 循環(huán)移位的本質(zhì)固定位寬下的旋轉(zhuǎn)這里值得多花點篇幅講清楚循環(huán)移位的本質(zhì)因為這是很多人的理解盲區(qū)。循環(huán)左移k位用公式表達就是(x k) | (x (B - k))但這個公式有個前提必須先對x做掩碼操作保證x的二進制位不超過B位。否則左移出去的“高位”根本不是你想要的循環(huán)效果。比如8位寬下x 0b10110010循環(huán)左移3位正確結(jié)果是 0b10010101。如果用常規(guī)的位移公式先x 3得到 0b10110010000再和 x (8 - 3) 即 x 5 0b101 做或得到 0b10110010101這顯然超過了8位。所以實際實現(xiàn)循環(huán)移位時第一件事就是定義位寬B然后統(tǒng)一用掩碼((1 B) - 1)截斷。做完截斷之后循環(huán)移位就是一個完全閉合的環(huán)上置換操作。從這個角度看循環(huán)移位的本質(zhì)是一個長度為B的環(huán)形數(shù)組整體旋轉(zhuǎn)k格。它不會產(chǎn)生新的比特不會丟失舊的比特只改變比特的“位置”。這決定了它在背包問題里適合當(dāng)“全局狀態(tài)變換”來用因為它變化的是整個狀態(tài)。2.3 狀態(tài)設(shè)計用整數(shù)表示全局位狀態(tài)既然位寬有限最自然的狀態(tài)表示就是把當(dāng)前數(shù)本身的二進制位當(dāng)作狀態(tài)。一個整數(shù)在B位寬內(nèi)取值0到2^B - 1這就是狀態(tài)全集。于是問題就清晰了我們需要一個DP數(shù)組dp[j][s]表示花了j點代價后當(dāng)前數(shù)值恰好為s是否可行或者dp[j]表示花了j點代價后能達到的最大數(shù)值。前者是可行性DP后者是最優(yōu)化DP。在分組背包框架下我建議用“一維最大價值DP 狀態(tài)作為下標(biāo)”的方式也就是dp[j]本身存的不是數(shù)值而是“是否存在某個數(shù)值s能達到”——如果要直接存“最大數(shù)”則需要在轉(zhuǎn)移時對當(dāng)前狀態(tài)做位運算變換然后取max。實際寫下來最省代碼的是這樣開一個布爾數(shù)組dp[j][s]表示用了j代價能不能到達狀態(tài)s。轉(zhuǎn)移時遍歷每一組操作對每個操作模擬位運算變換得到新的狀態(tài)ns op(s)然后更新ndp[j cost] | dp[j][s]。最后答案在所有可達狀態(tài)里取最大值。這個設(shè)計的好處是位運算的模擬可以直接內(nèi)聯(lián)在轉(zhuǎn)移里不需要人為定義“價值”因為“價值”就是狀態(tài)本身的大小。藍橋杯的題只要你最終輸出最大整數(shù)不需要回溯方案所以可行性DP加最后掃一遍取最大是最省心也最不容易錯的寫法。3. 完整解法與實現(xiàn)細節(jié)3.1 狀態(tài)定義與轉(zhuǎn)移方程這里把完整的狀態(tài)設(shè)計與轉(zhuǎn)移方程寫清楚。設(shè)總共有G組操作第i組有ki個動作。每個動作由一個二元組描述(cost, op)cost是執(zhí)行這個動作的代價op是一個函數(shù)給定當(dāng)前值x返回新值op(x)。定義dp[j][s] true 表示總共花費j點代價當(dāng)前數(shù)值為s的狀態(tài)可以達到初始化dp[0][x0] true // x0是初始值其它全false轉(zhuǎn)移時枚舉組i、組內(nèi)動作k、當(dāng)前代價j、當(dāng)前狀態(tài)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 }這里要注意一個細節(jié)分組背包為什么叫“分組”因為它每一組只能選一個操作。在可行性DP里這體現(xiàn)在轉(zhuǎn)移時必須“整組掃描”要么從上一組的狀態(tài)繼承下來不用本組操作要么選擇本組中的某一個操作執(zhí)行一次。不能一個組里選兩個。所以正確做法是每一組DP滾動一次。偽代碼是newdp dp // 這一組可以一個都不選所以直接從老狀態(tài)復(fù)制 for 組內(nèi)每個操作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這個“每組滾動一次、組內(nèi)枚舉操作”的順序就是分組背包和01背包的唯一區(qū)別。很多人在這一步栽跟頭以為直接三層循環(huán)就把所有操作混在一起跑了那就退化成了“每個操作最多用一次”的01背包組內(nèi)互斥性就丟了。3.2 初始化和循環(huán)順序為什么物品必須在外層背包問題里循環(huán)順序極其重要分組背包更是如此。先看初始化。dp[0][x0] true是唯一初始條件這表示最開始什么都沒做、數(shù)值還是初始值x0。千萬別把所有狀態(tài)都設(shè)成true那樣等于無視了操作帶來的變化約束答案永遠是全1的二進制串。再看循環(huán)順序。為什么組要放最外層因為分組背包要求每一組內(nèi)的操作只能選一個而“只能選一個”意味著同一組內(nèi)的操作不能疊加。如果你把組放內(nèi)層組內(nèi)操作相當(dāng)于可以在不同階段被重復(fù)使用那就徹底違背題意了。打個比方假設(shè)第一組操作是“左移x位”第二組操作是“按位與某個數(shù)”它們順序執(zhí)行是合理的因為它們不同組。但如果你把第一組里的“左移2位”和“左移3位”當(dāng)成兩個獨立物品放進背包就可能出現(xiàn)“先左移2位再左移3位”這種組合——這等價于左移5位而題目本意是這一組只能二選一。分組背包的外層組循環(huán)就是用來杜絕這種非法組合的。3.3 復(fù)雜度分析復(fù)雜度是背包題繞不開的話題。設(shè)C表示總代價上限B表示位寬狀態(tài)數(shù)S 2^BG表示組數(shù)K表示每組平均物品個數(shù)則DP的復(fù)雜度大約是O(G * K * C * S)背包代價維度C、狀態(tài)數(shù)維度S、組數(shù)G和組內(nèi)物品數(shù)K四個維度相乘?？粗悬c嚇人但實際題目數(shù)據(jù)不會開滿。藍橋杯這種題一般位寬就是8位到10位S最多1024C大概幾十到幾百組數(shù)G最多幾十。這樣算下來G10, K5, C100, S256 → 10*5*100*256 1,280,000一百多萬次操作C一秒內(nèi)隨便跑。就算數(shù)據(jù)再翻幾倍也扛得住。但如果是Python就要小心常數(shù)了建議用PyPy提交而且內(nèi)層循環(huán)盡量用位運算和列表推導(dǎo)壓一壓否則可能超時。空間上如果dp開二維(C1) * S個布爾值C100、S256就是兩萬多個微不足道。如果C和S再大點可以考慮滾動數(shù)組只保留上一組的狀態(tài)矩陣和當(dāng)前組的狀態(tài)矩陣滾動更新。因為每一組轉(zhuǎn)移只依賴上一組的結(jié)果滾動沒問題。這里順便給一個C核心代碼模板方便直接照著敲#include bits/stdc.h using namespace std; int main() { int B; // 位寬 int x0; // 初始值 int C; // 總代價上限 int G; // 組數(shù) 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) { // 循環(huán)左移 arg 位 ops.push_back({cost, [](int x) { if (arg 0) return x mask; return ((x arg) | (x (B - arg))) mask; }}); } else if (type 2) { // 循環(huán)右移 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這一步它非常關(guān)鍵——它保證了這一組操作可以“一個都不用”從上一組狀態(tài)直接照搬過來。4. 實操過程與踩坑記錄4.1 從30分到100分的思路轉(zhuǎn)變我第一次做這道題時寫的是暴力枚舉把所有操作的排列組合都試一遍限制條件一多直接原地爆炸。數(shù)據(jù)小的時候能過幾個點騙點分稍微一大就超時。后來意識到這是背包問題改用DP框架后依然踩了坑。最典型的一個坑是我一開始把每組的所有操作都塞進了同一個物品列表直接跑01背包。結(jié)果樣例能過一交就錯。為什么因為組內(nèi)互斥性沒保證。題目要求同一組只能選一個操作而我把組內(nèi)所有操作當(dāng)成不同的獨立物品等于允許同一組里選出兩個來疊加。用位運算打個比方同一組里的“左移1位”和“左移2位”如果都被選中最終效果可能就不是題目允許的。這個教訓(xùn)挺典型的——平時刷背包題大多數(shù)是選物品、物品之間天然獨立很少有“組內(nèi)互斥”的約束。一旦題目包裝成位運算人就容易忽略這層結(jié)構(gòu)直接套01背包的模板。所以我才在上一節(jié)反復(fù)強調(diào)組循環(huán)位置。它不是細節(jié)是算法正確性的根基。4.2 三個最容易寫錯的細節(jié)第一個是掩碼截斷。位運算題目最坑的就是符號位和高位垃圾數(shù)據(jù)。初始化時如果數(shù)據(jù)沒截斷后續(xù)左移右移的結(jié)果會累積出超過位寬范圍的臟位輕則答案偏大重則狀態(tài)錯亂。我的習(xí)慣是每一步操作結(jié)果都立刻 mask寧可多算一次不做沒把握的優(yōu)化。第二個是循環(huán)移位的方向。左移還是右移看題別想當(dāng)然。(x k) | (x (B - k))是左移(x k) | (x (B - k))是右移這兩個公式差一個符號寫反了樣例必然掛。還有一個坑是k等于0或者k不小于B的情況公式直接失效。正確寫法是先取模k % B再做移位如果取模后k為0直接返回原值截斷即可。第三個是DP維度順序。見過有人把狀態(tài)s放外層、代價j放內(nèi)層結(jié)果狀態(tài)轉(zhuǎn)移時總是覆蓋還沒用到的舊狀態(tài)導(dǎo)致同一次操作被重復(fù)疊加。分組背包的滾動更新里j一定是從小到大枚舉但組內(nèi)轉(zhuǎn)移時必須用上一組的dp而不是當(dāng)前組已經(jīng)更新過的ndp否則就會出現(xiàn)“同一組操作被用多次”的效果。代碼里我特意把枚舉操作放在最外層、代價和狀態(tài)放在內(nèi)層然后用dp[j][s]判斷更新到ndp[jc][...]就是防止這種污染。4.3 對拍與測試技巧這種題寫完一定不能只測樣例。我的習(xí)慣是寫一個暴力版小數(shù)據(jù)對拍器數(shù)據(jù)規(guī)模開小位寬B取4或5代價上限開個十幾然后暴力枚舉所有組的操作組合和DP結(jié)果對拍?；旧弦慌囊粋€準能快速暴露狀態(tài)轉(zhuǎn)移的bug。測試用例也有些規(guī)律。第一初始值x0設(shè)成全1或全0看DP是否能正確處理邊界。第二操作里加上“取反”這種非置換操作驗證狀態(tài)的閉合性——取反不會讓狀態(tài)超出位寬但如果你忘了截斷垃圾位會立刻現(xiàn)形。第三代價為0的操作這是最容易出問題的因為代價不增加時狀態(tài)在同一組內(nèi)可能形成環(huán)DP是否還能收斂要看循環(huán)順序夠不夠嚴謹。我實際對拍時最常抓到的bug就是代價為0的操作。如果代價為0那么j c等于j更新到ndp[j]而后續(xù)循環(huán)還會繼續(xù)遍歷到新更新的狀態(tài)嗎在寫for j和for s時如果直接在原dp上改就會出現(xiàn)同一組內(nèi)0代價操作反復(fù)使用的錯誤。我上面的代碼用的是ndp而且在枚舉時只看dp[j][s]不看ndp實時更新的狀態(tài)所以能避開這個問題。但對拍前我還是建議單獨構(gòu)造幾組0代價操作來驗證。測試用例設(shè)計建議 - 全1初始值 循環(huán)左移1位 - 全0初始值 按位或0xFF - 代價為0的取反操作連續(xù)兩組 - 位寬1的極端情況 - 所有操作代價都大于總代價C這些邊界情況覆蓋完代碼的魯棒性基本就有保障了。5. 從這道題延伸出去變體與藍橋杯趨勢5.1 變體一固定步數(shù)而非代價的背包很多競賽題會把“代價”改成“步數(shù)”比如“最多執(zhí)行M次操作”這其實是從背包變成了完全背包或者多重背包的變體。如果每組操作有次數(shù)限制比如每組最多用3次那就是把分組背包和多重背包嵌套在一起狀態(tài)轉(zhuǎn)移要多開一維記錄每組已用次數(shù)。循環(huán)移位在這種變體里特別有意思。因為循環(huán)移位本質(zhì)是置換群操作連續(xù)執(zhí)行同一方向的循環(huán)移位效果等于這些移位數(shù)的和再對位寬取模。比如8位寬下循環(huán)左移3位再左移5位等于循環(huán)左移0位也就是不變。這可以用“模B加法”化簡進而優(yōu)化狀態(tài)轉(zhuǎn)移。如果能把同組操作的效果化簡成等價類狀態(tài)轉(zhuǎn)移里的操作數(shù)量可以大幅減少。5.2 變體二操作順序敏感時的處理如果操作不是簡單的分組而是有順序要求比如必須先執(zhí)行組1再執(zhí)行組2那就不是背包能直接解決的問題了。這種題往往會退化成狀態(tài)機DP或者最短路問題。為什么因為當(dāng)順序固定時每一步操作都是確定的映射問題就變成“在每一步里選一個參數(shù)使得最終值最大”這本質(zhì)上是一個多階段決策問題。用分層圖最短路也能做每一層代表一個操作階段狀態(tài)是當(dāng)前數(shù)值邊權(quán)是代價目標(biāo)是最小化代價達到某個狀態(tài)。這種解法其實就是DP的另一種表述但理解成最短路后可以用 Dijkstra 來處理一些代價非單調(diào)的擴展思維上多了一條路。5.3 藍橋杯的命題規(guī)律與備賽建議觀察近幾年藍橋杯國賽的題目一個明顯趨勢是“包裝不重樣、內(nèi)核經(jīng)典化”。位運算題會裹上背包的外衣圖論題可能包裝成字符串題動態(tài)規(guī)劃經(jīng)常藏在看似是搜索的題面里。這對選手的考驗就是抽象能力你能不能透過描述看到它真正考的模型。所以我給備賽選手的建議是刷題時不要只刷“一眼就是背包”的題而是刻意挑那些表面看不出背包、實際用背包解決的題做。P12316就是這樣一個標(biāo)本。做完它你不僅掌握了循環(huán)移位的實現(xiàn)更重要的是你多了一次“從包裝中識別模型”的訓(xùn)練這種能力在藍橋杯國賽里比背誦模板值錢得多。另外說一句藍橋杯的評測環(huán)境對C的優(yōu)化非常寬容但Python選手一定要學(xué)會用PyPy、盡量避免在Python里寫多層大循環(huán)的背包。同樣的復(fù)雜度C過、Python超時的情況太常見了。如果非得用Python推薦把狀態(tài)壓縮成整數(shù)集合或者用bitset來優(yōu)化可行性DP不然最后一個數(shù)據(jù)點可能卡得很痛苦。6. 寫在最后的實用心得做這種“位運算 背包”的題我個人的體會是先別急著寫代碼花兩分鐘把操作的數(shù)學(xué)性質(zhì)列清楚。比如循環(huán)移位是可逆的、按位與會把某些位強制清零、按位或會把某些位強制置一、異或會翻轉(zhuǎn)特定位。這些性質(zhì)直接決定了DP狀態(tài)的收斂速度。按位或一次就能把很多低位變成1按位與則相反會讓狀態(tài)往“更小”的方向走。如果你發(fā)現(xiàn)某些操作組合后狀態(tài)數(shù)爆炸多半是你沒利用這些性質(zhì)做剪枝。還有一個小心得位運算題的答案經(jīng)常是2^B - 1或者接近它的數(shù)因為題目讓你“最大化”而全1是所有位都最大。所以寫完DP后可以先看一眼答案是不是在全1附近。如果不是排查一下是不是某些操作根本沒生效。我調(diào)試時發(fā)現(xiàn)過“左移0位”被當(dāng)成合法操作灌進去了結(jié)果等價類合并出錯答案和理論值差了十萬八千里。最后再分享一個技巧。如果題目允許把狀態(tài)用整數(shù)打印出來預(yù)處理所有操作對每個狀態(tài)的映射表。也就是先把op_k(s)對所有s預(yù)先算一遍存成表DP時直接查表而不現(xiàn)場跑位運算這樣能省一輪位運算的開銷。位寬不大時這點常數(shù)無所謂但位寬上到16以上、狀態(tài)數(shù)幾萬的時候查表比現(xiàn)場算快不少。這個技巧不僅適用于這道題任何位運算狀態(tài)DP都能用。遇到狀態(tài)轉(zhuǎn)移卡常先把查表優(yōu)化做了再說。