先交代一下背景。藍橋杯國賽的題尤其是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都能用。遇到狀態轉移卡常先把查表優化做了再說。