“優(yōu)秀的拆分”算法)
1. 項目概述從一道真題看信息學競賽的思維訓練如果你接觸過信息學奧賽的普及組CSP-J那么“優(yōu)秀的拆分”這道題絕對是一個繞不開的經(jīng)典。作為2020年CSP-J的第一題T1它看似簡單卻精準地考察了選手對計算機基礎——二進制表示——的理解以及將數(shù)學思維轉(zhuǎn)化為代碼邏輯的能力。很多新手第一次看到題目可能會懵拆分怎么拆優(yōu)秀的標準是什么其實這道題的本質(zhì)是要求你將一個給定的正整數(shù)表示為若干個互不相同的2的正整數(shù)次冪之和。如果能夠做到就輸出這些冪次如果不能就輸出-1。這聽起來有點像把一個數(shù)字“翻譯”成2的冪次方的“單詞”組合并且每個“單詞”只能用一次。為什么是2的冪次方因為這是計算機世界的“母語”。計算機內(nèi)部存儲和處理數(shù)據(jù)最底層就是二進制的0和1。每一個2的冪次方在二進制里就對應著某一位上的一個“1”。所以“優(yōu)秀的拆分”問題實質(zhì)上就是將一個十進制整數(shù)轉(zhuǎn)換為其二進制表示中所有值為1的位所對應的2的冪次方并且要從大到小輸出。這道題的價值遠不止于讓你通過一次考試。它像一把鑰匙幫你打開理解數(shù)據(jù)在計算機中如何存儲、如何高效運算的大門。無論是準備競賽的學生還是希望夯實編程基礎的開發(fā)者深入理解這個問題背后的原理和實現(xiàn)技巧都大有裨益。2. 核心思路解析二進制是唯一的鑰匙要解決“優(yōu)秀的拆分”最核心、最高效的思路就是利用二進制。我們不需要去暴力枚舉所有2的冪次方的組合那樣效率太低。我們需要理解十進制數(shù)和二進制數(shù)之間深刻的聯(lián)系。2.1 二進制表示與拆分的等價關(guān)系讓我們從一個具體的例子開始。假設題目給出的數(shù)字n 11。我們首先將11轉(zhuǎn)換為二進制11十進制 1011二進制。這個二進制數(shù)1011從右向左從低位到高位每一位的權(quán)重分別是 2^01, 2^12, 2^38。因此11 1*8 0*4 1*2 1*1 8 2 1?？次覀冏匀欢坏氐玫搅艘粋€由2的冪次方8, 2, 1組成的和。這正是題目要求的“拆分”。并且由于二進制表示中每個位上的值只能是0或1這意味著每個2的冪次方在求和時最多出現(xiàn)一次完美滿足了“互不相同”的條件。所以算法思路就非常清晰了如果輸入的整數(shù)n是奇數(shù)那么它的二進制最低位2^0位一定是1。這意味著拆分結(jié)果中必然包含2^0也就是1。但根據(jù)題目定義2的正整數(shù)次冪是從2^12開始的不包括1。因此任何奇數(shù)都不可能有“優(yōu)秀的拆分”直接輸出-1。如果n是偶數(shù)我們將其轉(zhuǎn)換為二進制然后找出所有值為1的位記錄這些位對應的2的冪次方從高位到低位即為答案。2.2 方案選型位運算 vs. 數(shù)學運算在代碼實現(xiàn)時我們有兩種主流方式來處理這個二進制分解過程。方案一數(shù)學除余法這是最直觀的方法模擬手算二進制的過程不斷地將數(shù)字除以2記錄余數(shù)。余數(shù)為1的位就對應一個2的冪次方。int n 10; // 舉例 vectorint powers; int bit_position 0; // 當前位的位置0代表2^0 while (n 0) { if (n % 2 1) { // 當前二進制位是1 // 注意題目要求輸出的是2^k而不是k。所以需要計算 2^bit_position // 但更常用的是通過左移運算1 bit_position powers.push_back(1 bit_position); } n / 2; // 相當于二進制數(shù)右移一位 bit_position; } // 得到的powers是從低位到高位的需要反轉(zhuǎn)后從大到小輸出 reverse(powers.begin(), powers.end());這種方法邏輯清晰易于理解但需要進行除法和取模運算在極端大量數(shù)據(jù)時效率略低于位運算。方案二位運算法這是更貼近計算機底層、效率更高的方法。我們直接檢查整數(shù)n的每一個二進制位。int n 10; vectorint powers; // 我們從高位向低位檢查以滿足從大到小輸出的要求 // 先找到最高位。例如10的二進制是1010最高位是2^38 for (int i 30; i 1; i--) { // 2^30 10^9普及組數(shù)據(jù)范圍足夠 if (n (1 i)) { // 檢查第i位是否為1 powers.push_back(1 i); } } // 循環(huán)從i1開始跳過了i0即2^01因為題目要求正整數(shù)次冪這里的關(guān)鍵是n (1 i)這個操作。1 i生成了一個只有第i位是1其他位都是0的數(shù)。按位與操作會檢查n的第i位是否也為1。如果結(jié)果為真非零則說明該位是1。為什么首選位運算位運算如是CPU最基本的指令通常在一個時鐘周期內(nèi)就能完成速度遠快于除法/取模運算。在競賽編程中養(yǎng)成使用位運算的習慣能在處理大量數(shù)據(jù)或復雜算法時帶來可觀的性能提升。對于這道題兩種方法都能輕松AC通過但位運算方案更優(yōu)雅、更“程序員”。3. 關(guān)鍵實現(xiàn)細節(jié)與避坑指南思路清晰了但要把代碼寫得健壯、準確還需要注意以下幾個關(guān)鍵細節(jié)這些都是從無數(shù)次提交錯誤中總結(jié)出來的經(jīng)驗。3.1 奇數(shù)情況的快速判斷與處理這是題目最大的一個“坑”也是區(qū)分是否理解題意的重要一點。題目明確要求拆分是“2的正整數(shù)次冪”即2, 4, 8, 16... 不包括12^0。而任何奇數(shù)的二進制表示最低位一定是1這意味著其拆分必然包含1。if (n % 2 1) { cout -1 endl; return 0; // 直接結(jié)束程序 }避坑點千萬不要試圖去拆分奇數(shù)。有些初學者可能會想那我把奇數(shù)減1變成偶數(shù)再拆分行不行不行因為題目要求就是拆分這個數(shù)本身。奇數(shù)就是無解沒有例外。3.2 從大到小輸出的實現(xiàn)技巧題目要求輸出從大到小排列。我們的算法邏輯自然保證了這一點。如果采用“從高位向低位”遍歷的位運算法那么我們每次找到的冪次方本身就是從大到小的直接存入數(shù)組或輸出即可。如果采用“從低位向高位”的除余法那么收集到的冪次方順序是從小到大的需要在最后進行反轉(zhuǎn)reverse操作。個人心得我強烈推薦使用從高位向低位遍歷的位運算法。理由有三第一無需額外的反轉(zhuǎn)操作邏輯更簡潔第二遍歷的上限可以預估比如對于CSP-J的數(shù)據(jù)范圍n ≤ 10^72^23約800萬2^24約1600萬所以從i24開始向下檢查就足夠了效率更高第三更能體現(xiàn)對二進制位操作的掌握。3.3 邊界條件與數(shù)據(jù)范圍考量雖然題目樣例可能很簡單但我們必須考慮通用情況。輸入為2二進制是10拆分結(jié)果就是2。正確。輸入為0或負數(shù)根據(jù)題目描述n是正整數(shù)所以無需處理。但在自己測試時要確保程序?qū)?奇數(shù)能正確輸出-1。大數(shù)情況當n很大時比如接近10^7計算2的冪次方1 i要確保不超出整數(shù)范圍。在C中對于int類型32位1 31會導致溢出因為最高位是符號位。因此我們的循環(huán)條件i的上限應設為30130約10億或者使用更大的數(shù)據(jù)類型如long long。一個實用的技巧在循環(huán)內(nèi)部可以先判斷(1 i) n。如果當前2的冪次已經(jīng)比n本身還大那么n的二進制表示中不可能在這一位為1可以直接break跳出循環(huán)減少不必要的迭代。for (int i 30; i 1; i--) { int power 1 i; // 計算2^i if (power n) continue; // 這一位肯定為0跳過 if (n power) { // 等價于 (n (1 i)) ! 0 cout power ; n - power; // 可選減去已找到的冪次有時能簡化邏輯 } }4. 完整代碼實現(xiàn)與逐行解讀下面我將給出一個C的完整AC代碼并附上詳細的注釋。這份代碼采用了效率最高的位運算方法并包含了上述的所有注意事項。#include iostream using namespace std; int main() { int n; cin n; // 關(guān)鍵點1奇數(shù)直接輸出-1 if (n % 2 1) { cout -1 endl; return 0; } // 關(guān)鍵點2從可能的最大冪次開始向下遍歷 // 2^30 1e9對于普及組數(shù)據(jù)完全足夠。使用1i計算2的冪次。 bool hasOutput false; // 標記是否輸出了至少一個數(shù)用于控制空格 for (int i 30; i 1; i--) { // i從1開始排除了2^01 int current_power 1 i; // 計算2^i // 如果當前的2^i比n還大則n的這一位肯定是0跳過 if (current_power n) { continue; } // 按位與運算檢查n的第i位是否為1 if (n current_power) { if (hasOutput) { cout ; // 不是第一個數(shù)先輸出空格 } cout current_power; hasOutput true; // n - current_power; // 可以減去但不必須因為我們是按位判斷不影響后續(xù)位判斷 } } // 關(guān)鍵點3如果n是偶數(shù)但循環(huán)后什么都沒輸出理論上只有n0時會發(fā)生但n是正整數(shù) // 為了代碼健壯性可以加上但本題保證n1所以可以省略。 if (!hasOutput) { // 這種情況對于正整數(shù)n不會發(fā)生除非n0。 // cout -1 endl; } cout endl; // 最后換行 return 0; }代碼解讀與技巧奇數(shù)判斷if (n % 2 1)是最高效的判斷方式。也可以用位運算if (n 1)含義完全相同。循環(huán)起點i 30是一個安全且足夠大的起點。你也可以根據(jù)數(shù)據(jù)范圍估算一個更小的值比如i 24。current_power n判斷這是一個重要的優(yōu)化。當2^i已經(jīng)大于當前的n時n的二進制表示中第i位及更高位絕對為0后續(xù)的i都可以跳過。雖然對于單次計算提升不大但在某些需要頻繁調(diào)用的場景或追求極致效率時是個好習慣。輸出格式控制使用hasOutput標志來控制空格避免了末尾多一個空格的常見格式錯誤。這是競賽編程中處理輸出格式的經(jīng)典技巧。n - current_power這行代碼被注釋掉了。它的作用是在找到一個冪次方后從n中減去它。這樣后續(xù)循環(huán)中n的值會變小current_power n的判斷會更快生效。兩種寫法都是正確的不減去也不影響按位與的判斷邏輯因為每一位是獨立的。5. 常見錯誤與問題排查實錄即便思路正確在實現(xiàn)時也容易掉進一些陷阱。下面是我在輔導學生和自己刷題中遇到的幾個典型錯誤案例。5.1 錯誤類型一遺漏奇數(shù)判斷或判斷錯誤這是最常見的錯誤。沒有理解“正整數(shù)次冪”不包括1。錯誤代碼示例// 錯誤沒有處理奇數(shù) cin n; for (int i 30; i 0; i--) { // i從0開始包含了1 ... }輸入3錯誤輸出2 1正確輸出-1排查方法首先單獨測試輸入1, 3, 5等奇數(shù)看輸出是否為-1。5.2 錯誤類型二輸出順序錯誤或格式錯誤題目要求從大到小輸出用空格隔開。錯誤代碼示例順序錯誤// 錯誤從低位向高位遍歷且未反轉(zhuǎn) while (n 0) { if (n % 2 1) cout (1 bit) ; bit; n / 2; }輸入10(二進制1010)錯誤輸出2 8先輸出2后輸出8正確輸出8 2錯誤代碼示例格式錯誤末尾多空格// 錯誤每次輸出都帶空格 for (...) { if (n (1i)) { cout (1i) ; // 最后一個數(shù)后面也會跟空格 } }雖然很多評測系統(tǒng)如OI系列會自動忽略行末空格但這是一個不好的習慣在某些嚴格系統(tǒng)上會導致格式錯誤。排查方法使用hasOutput標志或先收集到數(shù)組再統(tǒng)一輸出可以有效避免格式問題。5.3 錯誤類型三整數(shù)溢出在計算1 i時如果i過大如i31對于32位int會導致溢出結(jié)果是未定義的通常是負數(shù)。錯誤代碼示例for (int i 31; i 0; i--) { // i可能為31 if (n (1 i)) { // 當i31時131是負數(shù)-2147483648 ... } }解決方案確保循環(huán)上限合理。對于int類型的ni最大取30。更穩(wěn)妥的做法是使用long long類型來存儲current_power。for (int i 30; i 1; i--) { long long power 1LL i; // 使用LL后綴確保是long long類型 if (power n) continue; ... }5.4 問題排查速查表問題現(xiàn)象可能原因解決方案輸入奇數(shù)輸出了一串數(shù)未進行奇數(shù)判斷或判斷條件錯誤在程序開始處添加if (n%21) { cout-1; return 0; }輸出結(jié)果順序是反的遍歷二進制的方向是從低到高改為從高位向低位遍歷for(i30; i1; i--)輸出結(jié)果包含數(shù)字1循環(huán)變量i從0開始了確保循環(huán)從i1開始排除2^0對大一點的數(shù)據(jù)輸出錯誤或異常整數(shù)溢出檢查1i是否可能溢出降低i的上限或使用long long感覺代碼效率低使用了除余法且未做優(yōu)化改用位運算法并添加if(power n) continue提前跳出6. 從“優(yōu)秀的拆分”延伸的編程思維訓練這道題的價值不僅僅在于解決一個問題更在于它訓練了幾種非常重要的編程和算法思維。思維一數(shù)學建模與轉(zhuǎn)化將“拆分”問題轉(zhuǎn)化為“二進制表示”問題這是一種重要的建模能力。在競賽和實際開發(fā)中很多問題表面復雜但換一個數(shù)學視角就會變得清晰簡單。遇到問題時先思考其數(shù)學本質(zhì)往往能事半功倍。思維二位運算的熟練應用這道題是指引你深入學習位運算的絕佳入口。除了按位與、左移還有按位或|、異或^、右移、取反~等。掌握它們你就能寫出更高效、更簡潔的代碼。例如判斷奇偶用n 1除以2的冪用n k設置某位為1用n | (1 k)。思維三邊界條件與魯棒性思考必須考慮奇數(shù)、偶數(shù)、1、大數(shù)等邊界情況。編寫代碼時養(yǎng)成首先考慮輸入數(shù)據(jù)的合法范圍和各種極端情況的習慣這能極大提高代碼的魯棒性Robustness減少BUG。思維四空間與時間的權(quán)衡雖然這道題不需要復雜的數(shù)據(jù)結(jié)構(gòu)但它暗示了一種思想我們通過一個循環(huán)在“時間”上遍歷了所有可能的2的冪次而沒有預先在“空間”里存儲一個2的冪次表。在算法設計中時間和空間常常需要權(quán)衡Time-Space Tradeoff。對于這個問題用時間換空間即時計算2^i是更優(yōu)解。如果你想進一步挑戰(zhàn)自己可以嘗試這些變種問題如果允許重復使用2的冪次方呢這就變成了經(jīng)典的“換硬幣”問題可以用動態(tài)規(guī)劃求解。如果不是2的冪而是3的冪、5的冪呢思路類似但進制轉(zhuǎn)換變成了三進制、五進制。如何找出“最少數(shù)量的2的冪次方”來表示一個數(shù)這其實就是求該數(shù)二進制表示中“1”的個數(shù)popcount有非常巧妙的位運算技巧如n (n-1)。這道“優(yōu)秀的拆分”就像一顆種子它包含的二進制、位運算、循環(huán)控制、條件判斷等概念是構(gòu)建更龐大算法知識體系的基石。吃透它你收獲的將不僅僅是一道題的分數(shù)。 CSP-J真題解析：二進制位運算實現(xiàn)“優(yōu)秀的拆分”算法
1. 項目概述從一道真題看信息學競賽的思維訓練如果你接觸過信息學奧賽的普及組CSP-J那么“優(yōu)秀的拆分”這道題絕對是一個繞不開的經(jīng)典。作為2020年CSP-J的第一題T1它看似簡單卻精準地考察了選手對計算機基礎——二進制表示——的理解以及將數(shù)學思維轉(zhuǎn)化為代碼邏輯的能力。很多新手第一次看到題目可能會懵拆分怎么拆優(yōu)秀的標準是什么其實這道題的本質(zhì)是要求你將一個給定的正整數(shù)表示為若干個互不相同的2的正整數(shù)次冪之和。如果能夠做到就輸出這些冪次如果不能就輸出-1。這聽起來有點像把一個數(shù)字“翻譯”成2的冪次方的“單詞”組合并且每個“單詞”只能用一次。為什么是2的冪次方因為這是計算機世界的“母語”。計算機內(nèi)部存儲和處理數(shù)據(jù)最底層就是二進制的0和1。每一個2的冪次方在二進制里就對應著某一位上的一個“1”。所以“優(yōu)秀的拆分”問題實質(zhì)上就是將一個十進制整數(shù)轉(zhuǎn)換為其二進制表示中所有值為1的位所對應的2的冪次方并且要從大到小輸出。這道題的價值遠不止于讓你通過一次考試。它像一把鑰匙幫你打開理解數(shù)據(jù)在計算機中如何存儲、如何高效運算的大門。無論是準備競賽的學生還是希望夯實編程基礎的開發(fā)者深入理解這個問題背后的原理和實現(xiàn)技巧都大有裨益。2. 核心思路解析二進制是唯一的鑰匙要解決“優(yōu)秀的拆分”最核心、最高效的思路就是利用二進制。我們不需要去暴力枚舉所有2的冪次方的組合那樣效率太低。我們需要理解十進制數(shù)和二進制數(shù)之間深刻的聯(lián)系。2.1 二進制表示與拆分的等價關(guān)系讓我們從一個具體的例子開始。假設題目給出的數(shù)字n 11。我們首先將11轉(zhuǎn)換為二進制11十進制 1011二進制。這個二進制數(shù)1011從右向左從低位到高位每一位的權(quán)重分別是 2^01, 2^12, 2^38。因此11 1*8 0*4 1*2 1*1 8 2 1?？次覀冏匀欢坏氐玫搅艘粋€由2的冪次方8, 2, 1組成的和。這正是題目要求的“拆分”。并且由于二進制表示中每個位上的值只能是0或1這意味著每個2的冪次方在求和時最多出現(xiàn)一次完美滿足了“互不相同”的條件。所以算法思路就非常清晰了如果輸入的整數(shù)n是奇數(shù)那么它的二進制最低位2^0位一定是1。這意味著拆分結(jié)果中必然包含2^0也就是1。但根據(jù)題目定義2的正整數(shù)次冪是從2^12開始的不包括1。因此任何奇數(shù)都不可能有“優(yōu)秀的拆分”直接輸出-1。如果n是偶數(shù)我們將其轉(zhuǎn)換為二進制然后找出所有值為1的位記錄這些位對應的2的冪次方從高位到低位即為答案。2.2 方案選型位運算 vs. 數(shù)學運算在代碼實現(xiàn)時我們有兩種主流方式來處理這個二進制分解過程。方案一數(shù)學除余法這是最直觀的方法模擬手算二進制的過程不斷地將數(shù)字除以2記錄余數(shù)。余數(shù)為1的位就對應一個2的冪次方。int n 10; // 舉例 vectorint powers; int bit_position 0; // 當前位的位置0代表2^0 while (n 0) { if (n % 2 1) { // 當前二進制位是1 // 注意題目要求輸出的是2^k而不是k。所以需要計算 2^bit_position // 但更常用的是通過左移運算1 bit_position powers.push_back(1 bit_position); } n / 2; // 相當于二進制數(shù)右移一位 bit_position; } // 得到的powers是從低位到高位的需要反轉(zhuǎn)后從大到小輸出 reverse(powers.begin(), powers.end());這種方法邏輯清晰易于理解但需要進行除法和取模運算在極端大量數(shù)據(jù)時效率略低于位運算。方案二位運算法這是更貼近計算機底層、效率更高的方法。我們直接檢查整數(shù)n的每一個二進制位。int n 10; vectorint powers; // 我們從高位向低位檢查以滿足從大到小輸出的要求 // 先找到最高位。例如10的二進制是1010最高位是2^38 for (int i 30; i 1; i--) { // 2^30 10^9普及組數(shù)據(jù)范圍足夠 if (n (1 i)) { // 檢查第i位是否為1 powers.push_back(1 i); } } // 循環(huán)從i1開始跳過了i0即2^01因為題目要求正整數(shù)次冪這里的關(guān)鍵是n (1 i)這個操作。1 i生成了一個只有第i位是1其他位都是0的數(shù)。按位與操作會檢查n的第i位是否也為1。如果結(jié)果為真非零則說明該位是1。為什么首選位運算位運算如是CPU最基本的指令通常在一個時鐘周期內(nèi)就能完成速度遠快于除法/取模運算。在競賽編程中養(yǎng)成使用位運算的習慣能在處理大量數(shù)據(jù)或復雜算法時帶來可觀的性能提升。對于這道題兩種方法都能輕松AC通過但位運算方案更優(yōu)雅、更“程序員”。3. 關(guān)鍵實現(xiàn)細節(jié)與避坑指南思路清晰了但要把代碼寫得健壯、準確還需要注意以下幾個關(guān)鍵細節(jié)這些都是從無數(shù)次提交錯誤中總結(jié)出來的經(jīng)驗。3.1 奇數(shù)情況的快速判斷與處理這是題目最大的一個“坑”也是區(qū)分是否理解題意的重要一點。題目明確要求拆分是“2的正整數(shù)次冪”即2, 4, 8, 16... 不包括12^0。而任何奇數(shù)的二進制表示最低位一定是1這意味著其拆分必然包含1。if (n % 2 1) { cout -1 endl; return 0; // 直接結(jié)束程序 }避坑點千萬不要試圖去拆分奇數(shù)。有些初學者可能會想那我把奇數(shù)減1變成偶數(shù)再拆分行不行不行因為題目要求就是拆分這個數(shù)本身。奇數(shù)就是無解沒有例外。3.2 從大到小輸出的實現(xiàn)技巧題目要求輸出從大到小排列。我們的算法邏輯自然保證了這一點。如果采用“從高位向低位”遍歷的位運算法那么我們每次找到的冪次方本身就是從大到小的直接存入數(shù)組或輸出即可。如果采用“從低位向高位”的除余法那么收集到的冪次方順序是從小到大的需要在最后進行反轉(zhuǎn)reverse操作。個人心得我強烈推薦使用從高位向低位遍歷的位運算法。理由有三第一無需額外的反轉(zhuǎn)操作邏輯更簡潔第二遍歷的上限可以預估比如對于CSP-J的數(shù)據(jù)范圍n ≤ 10^72^23約800萬2^24約1600萬所以從i24開始向下檢查就足夠了效率更高第三更能體現(xiàn)對二進制位操作的掌握。3.3 邊界條件與數(shù)據(jù)范圍考量雖然題目樣例可能很簡單但我們必須考慮通用情況。輸入為2二進制是10拆分結(jié)果就是2。正確。輸入為0或負數(shù)根據(jù)題目描述n是正整數(shù)所以無需處理。但在自己測試時要確保程序?qū)?奇數(shù)能正確輸出-1。大數(shù)情況當n很大時比如接近10^7計算2的冪次方1 i要確保不超出整數(shù)范圍。在C中對于int類型32位1 31會導致溢出因為最高位是符號位。因此我們的循環(huán)條件i的上限應設為30130約10億或者使用更大的數(shù)據(jù)類型如long long。一個實用的技巧在循環(huán)內(nèi)部可以先判斷(1 i) n。如果當前2的冪次已經(jīng)比n本身還大那么n的二進制表示中不可能在這一位為1可以直接break跳出循環(huán)減少不必要的迭代。for (int i 30; i 1; i--) { int power 1 i; // 計算2^i if (power n) continue; // 這一位肯定為0跳過 if (n power) { // 等價于 (n (1 i)) ! 0 cout power ; n - power; // 可選減去已找到的冪次有時能簡化邏輯 } }4. 完整代碼實現(xiàn)與逐行解讀下面我將給出一個C的完整AC代碼并附上詳細的注釋。這份代碼采用了效率最高的位運算方法并包含了上述的所有注意事項。#include iostream using namespace std; int main() { int n; cin n; // 關(guān)鍵點1奇數(shù)直接輸出-1 if (n % 2 1) { cout -1 endl; return 0; } // 關(guān)鍵點2從可能的最大冪次開始向下遍歷 // 2^30 1e9對于普及組數(shù)據(jù)完全足夠。使用1i計算2的冪次。 bool hasOutput false; // 標記是否輸出了至少一個數(shù)用于控制空格 for (int i 30; i 1; i--) { // i從1開始排除了2^01 int current_power 1 i; // 計算2^i // 如果當前的2^i比n還大則n的這一位肯定是0跳過 if (current_power n) { continue; } // 按位與運算檢查n的第i位是否為1 if (n current_power) { if (hasOutput) { cout ; // 不是第一個數(shù)先輸出空格 } cout current_power; hasOutput true; // n - current_power; // 可以減去但不必須因為我們是按位判斷不影響后續(xù)位判斷 } } // 關(guān)鍵點3如果n是偶數(shù)但循環(huán)后什么都沒輸出理論上只有n0時會發(fā)生但n是正整數(shù) // 為了代碼健壯性可以加上但本題保證n1所以可以省略。 if (!hasOutput) { // 這種情況對于正整數(shù)n不會發(fā)生除非n0。 // cout -1 endl; } cout endl; // 最后換行 return 0; }代碼解讀與技巧奇數(shù)判斷if (n % 2 1)是最高效的判斷方式。也可以用位運算if (n 1)含義完全相同。循環(huán)起點i 30是一個安全且足夠大的起點。你也可以根據(jù)數(shù)據(jù)范圍估算一個更小的值比如i 24。current_power n判斷這是一個重要的優(yōu)化。當2^i已經(jīng)大于當前的n時n的二進制表示中第i位及更高位絕對為0后續(xù)的i都可以跳過。雖然對于單次計算提升不大但在某些需要頻繁調(diào)用的場景或追求極致效率時是個好習慣。輸出格式控制使用hasOutput標志來控制空格避免了末尾多一個空格的常見格式錯誤。這是競賽編程中處理輸出格式的經(jīng)典技巧。n - current_power這行代碼被注釋掉了。它的作用是在找到一個冪次方后從n中減去它。這樣后續(xù)循環(huán)中n的值會變小current_power n的判斷會更快生效。兩種寫法都是正確的不減去也不影響按位與的判斷邏輯因為每一位是獨立的。5. 常見錯誤與問題排查實錄即便思路正確在實現(xiàn)時也容易掉進一些陷阱。下面是我在輔導學生和自己刷題中遇到的幾個典型錯誤案例。5.1 錯誤類型一遺漏奇數(shù)判斷或判斷錯誤這是最常見的錯誤。沒有理解“正整數(shù)次冪”不包括1。錯誤代碼示例// 錯誤沒有處理奇數(shù) cin n; for (int i 30; i 0; i--) { // i從0開始包含了1 ... }輸入3錯誤輸出2 1正確輸出-1排查方法首先單獨測試輸入1, 3, 5等奇數(shù)看輸出是否為-1。5.2 錯誤類型二輸出順序錯誤或格式錯誤題目要求從大到小輸出用空格隔開。錯誤代碼示例順序錯誤// 錯誤從低位向高位遍歷且未反轉(zhuǎn) while (n 0) { if (n % 2 1) cout (1 bit) ; bit; n / 2; }輸入10(二進制1010)錯誤輸出2 8先輸出2后輸出8正確輸出8 2錯誤代碼示例格式錯誤末尾多空格// 錯誤每次輸出都帶空格 for (...) { if (n (1i)) { cout (1i) ; // 最后一個數(shù)后面也會跟空格 } }雖然很多評測系統(tǒng)如OI系列會自動忽略行末空格但這是一個不好的習慣在某些嚴格系統(tǒng)上會導致格式錯誤。排查方法使用hasOutput標志或先收集到數(shù)組再統(tǒng)一輸出可以有效避免格式問題。5.3 錯誤類型三整數(shù)溢出在計算1 i時如果i過大如i31對于32位int會導致溢出結(jié)果是未定義的通常是負數(shù)。錯誤代碼示例for (int i 31; i 0; i--) { // i可能為31 if (n (1 i)) { // 當i31時131是負數(shù)-2147483648 ... } }解決方案確保循環(huán)上限合理。對于int類型的ni最大取30。更穩(wěn)妥的做法是使用long long類型來存儲current_power。for (int i 30; i 1; i--) { long long power 1LL i; // 使用LL后綴確保是long long類型 if (power n) continue; ... }5.4 問題排查速查表問題現(xiàn)象可能原因解決方案輸入奇數(shù)輸出了一串數(shù)未進行奇數(shù)判斷或判斷條件錯誤在程序開始處添加if (n%21) { cout-1; return 0; }輸出結(jié)果順序是反的遍歷二進制的方向是從低到高改為從高位向低位遍歷for(i30; i1; i--)輸出結(jié)果包含數(shù)字1循環(huán)變量i從0開始了確保循環(huán)從i1開始排除2^0對大一點的數(shù)據(jù)輸出錯誤或異常整數(shù)溢出檢查1i是否可能溢出降低i的上限或使用long long感覺代碼效率低使用了除余法且未做優(yōu)化改用位運算法并添加if(power n) continue提前跳出6. 從“優(yōu)秀的拆分”延伸的編程思維訓練這道題的價值不僅僅在于解決一個問題更在于它訓練了幾種非常重要的編程和算法思維。思維一數(shù)學建模與轉(zhuǎn)化將“拆分”問題轉(zhuǎn)化為“二進制表示”問題這是一種重要的建模能力。在競賽和實際開發(fā)中很多問題表面復雜但換一個數(shù)學視角就會變得清晰簡單。遇到問題時先思考其數(shù)學本質(zhì)往往能事半功倍。思維二位運算的熟練應用這道題是指引你深入學習位運算的絕佳入口。除了按位與、左移還有按位或|、異或^、右移、取反~等。掌握它們你就能寫出更高效、更簡潔的代碼。例如判斷奇偶用n 1除以2的冪用n k設置某位為1用n | (1 k)。思維三邊界條件與魯棒性思考必須考慮奇數(shù)、偶數(shù)、1、大數(shù)等邊界情況。編寫代碼時養(yǎng)成首先考慮輸入數(shù)據(jù)的合法范圍和各種極端情況的習慣這能極大提高代碼的魯棒性Robustness減少BUG。思維四空間與時間的權(quán)衡雖然這道題不需要復雜的數(shù)據(jù)結(jié)構(gòu)但它暗示了一種思想我們通過一個循環(huán)在“時間”上遍歷了所有可能的2的冪次而沒有預先在“空間”里存儲一個2的冪次表。在算法設計中時間和空間常常需要權(quán)衡Time-Space Tradeoff。對于這個問題用時間換空間即時計算2^i是更優(yōu)解。如果你想進一步挑戰(zhàn)自己可以嘗試這些變種問題如果允許重復使用2的冪次方呢這就變成了經(jīng)典的“換硬幣”問題可以用動態(tài)規(guī)劃求解。如果不是2的冪而是3的冪、5的冪呢思路類似但進制轉(zhuǎn)換變成了三進制、五進制。如何找出“最少數(shù)量的2的冪次方”來表示一個數(shù)這其實就是求該數(shù)二進制表示中“1”的個數(shù)popcount有非常巧妙的位運算技巧如n (n-1)。這道“優(yōu)秀的拆分”就像一顆種子它包含的二進制、位運算、循環(huán)控制、條件判斷等概念是構(gòu)建更龐大算法知識體系的基石。吃透它你收獲的將不僅僅是一道題的分數(shù)。