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