1. 從一道“過河”題看NOIP-J1的思維起點(diǎn)最近在整理舊資料時翻到了2014年NOIP普及組J組第一輪的真題。雖然距離現(xiàn)在有些年頭了但里面的題目尤其是那道經(jīng)典的“過河”問題至今看來依然充滿了啟發(fā)性。它不像現(xiàn)在一些競賽題那樣追求復(fù)雜的算法模板或刁鉆的數(shù)據(jù)結(jié)構(gòu)而是直指計算機(jī)思維和問題建模的核心——如何把一個現(xiàn)實(shí)生活中的場景抽象成計算機(jī)能理解和處理的過程。對于剛開始接觸信息學(xué)競賽的初中生或者任何想鍛煉邏輯思維和編程解決問題能力的朋友來說這類題目都是極好的“磨刀石”。今天我們就以2014年NOIP-J1的真題為引子不單單是講答案更重要的是拆解題目背后的思考路徑看看當(dāng)年出題人希望考察哪些能力以及我們今天能從中汲取什么營養(yǎng)。NOIP-J1的試卷結(jié)構(gòu)通常包括選擇題、問題求解和閱讀程序?qū)懡Y(jié)果等部分考察范圍覆蓋計算機(jī)基礎(chǔ)、簡單算法、邏輯推理和基本的代碼閱讀理解。2014年的這套題整體難度適中但有幾道題設(shè)計得非常巧妙需要跳出慣性思維。我們重點(diǎn)聊聊其中最具代表性的幾道特別是那道需要你“指揮”青蛙過河的題目它完美地詮釋了什么叫“模擬”算法以及為什么清晰的步驟分解能力在編程中如此重要。2. “過河”模擬題把現(xiàn)實(shí)步驟翻譯成代碼邏輯我們先來看這道經(jīng)典的“青蛙過河”題題目大意還原。河中間有N塊石頭排成一排左邊岸上有若干只青蛙要跳到右邊岸上。青蛙只能向右跳并且一次最多跳過K只青蛙即最多跨越K個空位。題目會給出初始狀態(tài)問最少需要多少步所有青蛙都能到達(dá)對岸或者判斷是否無解。這聽起來像個游戲但本質(zhì)上是一個狀態(tài)模擬與搜索問題。很多同學(xué)第一次見可能會有點(diǎn)懵不知道從哪里下手。關(guān)鍵在于不要一上來就想代碼而是先用人腦模擬一遍小規(guī)模的情況找出規(guī)律。2.1 問題拆解與狀態(tài)定義首先我們得把問題“數(shù)字化”。河中的石頭和青蛙的位置可以用一個數(shù)組來表示。例如用數(shù)組a[]表示每個位置的狀態(tài)0代表空位石頭或岸邊的空位1代表有一只青蛙。假設(shè)有5個位置包括左右岸初始狀態(tài)為1 1 0 1 01代表青蛙。青蛙的跳躍規(guī)則是只能向右并且中間最多只能有K個連續(xù)的1青蛙被跳過。這其實(shí)是對“跳躍距離”的一種限制。更直觀的理解是一只青蛙要看它右邊離它最近的那個空位0在哪里如果中間隔著的青蛙數(shù)量小于等于K它就能跳過去。那么我們的目標(biāo)狀態(tài)就是所有青蛙都移動到最右邊。對于上面的例子目標(biāo)狀態(tài)是0 0 1 1 1。解題的核心思路是模擬從左邊開始依次嘗試移動每一只青蛙每次都移動當(dāng)前能移動的最左邊的青蛙這是一個貪心策略通常能保證步數(shù)最少。為什么是最左邊因?yàn)橐苿幼筮叺那嗤芸梢詾楦筮叺那嗤茯v出空間這是一個“連鎖反應(yīng)”的起點(diǎn)。2.2 貪心策略的證明與手動演算我們來手動算一個例子。設(shè)K1初始狀態(tài)1 1 0 1 0。從左往右找第一只青蛙位置1它右邊是1不是空位。它最多跳過K1只青蛙所以它看位置30中間隔著位置2的1只青蛙可以跳。跳完后狀態(tài)0 1 1 1 0。繼續(xù)從最左邊找。位置1是0位置2是青蛙。它右邊位置3是1看位置41也不是空位看位置50中間隔著位置3和4兩只青蛙1 1數(shù)量為2 K1所以它不能跳到位置5。那么它能否跳到更近的空位位置3已經(jīng)是青蛙了。所以位置2的青蛙此時無法移動。既然位置2的青蛙動不了我們就看下一個能動的。位置3的青蛙右邊位置4是1看位置5是0中間隔著位置4的1只青蛙等于K可以跳。跳完后狀態(tài)0 1 1 0 1。此時狀態(tài)0 1 1 0 1。最左邊的青蛙在位置2。它右邊位置3是1看位置4是0中間隔著位置3的1只青蛙可以跳。跳完后狀態(tài)0 0 1 1 1。檢查狀態(tài)所有青蛙已在最右端共用了3步。這個過程就是貪心模擬。我們需要在代碼里實(shí)現(xiàn)一個循環(huán)只要未達(dá)到目標(biāo)狀態(tài)就不斷地尋找并移動最左邊可移動的青蛙。如果某一次循環(huán)中沒有找到任何可以移動的青蛙但狀態(tài)又不是目標(biāo)狀態(tài)那就說明無解。注意這里的“可移動”判斷是核心也是容易出錯的地方。必須嚴(yán)格按照規(guī)則從青蛙當(dāng)前位置的下一個位置開始掃描統(tǒng)計連續(xù)青蛙的數(shù)量直到遇到一個空位。如果連續(xù)青蛙的數(shù)量 K則可以跳到那個空位否則這只青蛙本次就不能移動。需要掃描到數(shù)組末尾因?yàn)榭赡芴^所有石頭直接到對岸。2.3 從模擬到代碼的轉(zhuǎn)換將上述思路轉(zhuǎn)化為代碼框架如下讀入N, K和初始狀態(tài)數(shù)組a[N]。定義目標(biāo)狀態(tài)數(shù)組target[N]所有青蛙集中在右邊。初始化步數(shù)steps 0。While (當(dāng)前狀態(tài) ! 目標(biāo)狀態(tài)) a. 設(shè)置一個標(biāo)志moved false。 b. 從左到右遍歷數(shù)組對于每個是青蛙的位置i i. 從j i1開始向右掃描初始化frog_count 0。 ii. 當(dāng)j N且a[j] 1時frog_count,j。 iii. 如果j N且a[j] 0且frog_count K則這是一次合法跳躍。 - 交換a[i]和a[j]的值青蛙從i跳到j(luò)。 -moved true,steps。 - 跳出對當(dāng)前青蛙的檢查因?yàn)橐淮沃灰苿右恢弧?c. 如果一輪遍歷后moved false說明無法再移動輸出無解并結(jié)束。輸出步數(shù)steps。這個模擬過程很好地考察了選手對循環(huán)、條件判斷和數(shù)組操作的基本功更重要的是考察了將文字規(guī)則嚴(yán)謹(jǐn)?shù)剞D(zhuǎn)化為邏輯條件的能力。在競賽中這類題目往往通過設(shè)計不同的K值和初始狀態(tài)來測試程序是否考慮了所有邊界情況比如K0青蛙只能跳到相鄰空位或者所有青蛙一開始就在最右邊等特殊情況。3. 邏輯推理與排列組合隱藏在選擇題里的思維體操除了編程題NOIP-J1的選擇題和問題求解部分同樣充滿智慧。2014年試卷中有幾道涉及邏輯推理和簡單排列組合的題目它們不要求寫代碼但要求清晰的思維和嚴(yán)謹(jǐn)?shù)耐茖?dǎo)。這部分能力對于后期理解復(fù)雜的算法邏輯至關(guān)重要。例如可能有一道題是這樣的“有5個不同的禮物分給3個小朋友每人至少一個有多少種分法” 這本質(zhì)上是一個第二類斯特林?jǐn)?shù)的應(yīng)用或者用隔板法的變種。對于初學(xué)者不需要知道這些名詞但需要會分類討論。首先5個不同禮物分給3個不同的人每人至少一個。我們可以先考慮禮物的分配方式。一種直觀的方法是“先分堆再分配”。將5個不同的禮物分成3堆非空。分堆的方式只有兩種類型一堆3個另外兩堆各1個記為3,1,1或者一堆1個另外兩堆各2個記為1,2,2。對于(3,1,1)的分法先從5個禮物中選3個作為那大堆有C(5,3)10種選法。剩下的兩個禮物自然成為兩個1份。但是這里兩個“1份”是一樣的都是單個禮物所以這種分堆方式就是10種。對于(1,2,2)的分法先從5個禮物中選1個作為單獨(dú)的那份有C(5,1)5種選法。然后從剩下4個禮物中選2個作為第一堆2個有C(4,2)6種選法。剩下的2個自然成為第二堆。但是這里兩個“2個一堆”的堆是沒有區(qū)別的比如{A,B}和{C,D}交換算同一種分堆所以我們需要除以2的階乘2!。因此這種分堆方式有 (5 * 6) / 2 15種。所以總的分堆方法有 10 15 25種。最后把3堆禮物分給3個不同的小朋友是一個全排列有 3! 6種方法。因此總的分配方法為 25 * 6 150種。這道題考察的就是有序分配中的去重思想。很多同學(xué)會在(1,2,2)這種分堆時忘記除以2!導(dǎo)致結(jié)果錯誤。在編程解題中這種“去重”思想無處不在比如在生成組合、枚舉狀態(tài)時如何避免重復(fù)計算是一個永恒的話題。另一類常見的題目是邏輯判斷題比如“甲、乙、丙三人中只有一人說了真話根據(jù)他們的陳述判斷事實(shí)”。這類題最有效的方法是假設(shè)法。假設(shè)甲說真話那么推導(dǎo)乙和丙的話是否符合“只有一人說真話”的條件如果矛盾則假設(shè)不成立再假設(shè)乙說真話…… 這種方法本質(zhì)上是一種窮舉搜索只不過規(guī)模很小用人腦就可以完成。但在編程中當(dāng)變量增多時我們就需要編寫程序來枚舉所有可能的“真話/假話”組合狀態(tài)這其實(shí)是一個簡單的布爾狀態(tài)搜索然后驗(yàn)證哪種組合滿足所有邏輯條件。這為后面學(xué)習(xí)“搜索”算法中的狀態(tài)空間概念打下了基礎(chǔ)。4. 閱讀程序?qū)懡Y(jié)果理解代碼執(zhí)行過程的“慢鏡頭”閱讀程序題是NOIP/J組試卷的特色也是難點(diǎn)。它給你一段完整的、通常帶有一些“陷阱”的代碼要求你人工模擬計算機(jī)的執(zhí)行過程寫出最終的輸出。這相當(dāng)于給代碼執(zhí)行過程拍了一個“慢鏡頭”強(qiáng)迫你去理解每一行代碼的作用每一個變量的變化。2014年的這類題目通常涉及循環(huán)、數(shù)組、遞歸或簡單的字符串處理。我們構(gòu)造一個類似風(fēng)格的例子#include iostream using namespace std; int main() { int a[10] {0}; int i, j, sum 0; for (i 0; i 10; i) { a[i] i % 3; } for (i 1; i 9; i) { for (j i 1; j 10; j) { if (a[i] a[j]) { sum; } } } cout sum endl; return 0; }要解這道題不能憑感覺必須一步步來第一個循環(huán)初始化數(shù)組a。i%3的結(jié)果是循環(huán)的0%30, 1%31, 2%32, 3%30, 4%31... 所以數(shù)組a最終為[0, 1, 2, 0, 1, 2, 0, 1, 2, 0]。第二個部分是雙重循環(huán)。外層i從1到8內(nèi)層j從i1到9。這是一個典型的比較所有無序?qū)Φ难h(huán)結(jié)構(gòu)。if (a[i] a[j])則sum。也就是說sum統(tǒng)計的是對于所有滿足1 i j 9的(i, j)對有多少對滿足a[i]的值大于a[j]的值。我們不需要比較所有36對可以找規(guī)律。數(shù)組a從下標(biāo)1開始是[1, 2, 0, 1, 2, 0, 1, 2, 0]對應(yīng)a[1]到a[9]。我們關(guān)心的是值的大小關(guān)系。值只有012三種。對于值為2的元素它比后面所有的0和1都大。對于值為1的元素它比后面所有的0都大但比后面的2小。對于值為0的元素它比后面任何數(shù)都小因?yàn)?是最小的。我們來數(shù)一數(shù)a[1]1后面是2,0,1,2,0,1,2,0。比它小的只有0。后面0的位置有a[3], a[6], a[9]。所以貢獻(xiàn)3。a[2]2后面是0,1,2,0,1,2,0。所有數(shù)0,1,0,1,0都比2小。所以貢獻(xiàn)5。a[3]0后面都比它大1,2,0,1,2,0沒有比0小的。貢獻(xiàn)0。a[4]1后面是2,0,1,2,0。比1小的只有0a[6], a[9]。貢獻(xiàn)2。a[5]2后面是0,1,2,0。所有數(shù)0,1,0都比2小。貢獻(xiàn)3。a[6]0后面是1,2,0。沒有比0小的。貢獻(xiàn)0。a[7]1后面是2,0。比1小的只有0a[9]。貢獻(xiàn)1。a[8]2后面是0。0比2小。貢獻(xiàn)1。a[9]0后面沒有元素了。貢獻(xiàn)0。把所有貢獻(xiàn)加起來350230110 15。所以最終輸出是15。這道題考察了取模運(yùn)算、數(shù)組遍歷、雙重循環(huán)的邏輯以及耐心和細(xì)心。在實(shí)際做題時可以在草稿紙上畫出數(shù)組并標(biāo)記出比較過程這是最可靠的方法。很多錯誤都源于對循環(huán)邊界i9和j10理解不清或者沒有耐心完成整個計數(shù)過程。5. 真題訓(xùn)練的現(xiàn)代意義與方法建議今天回過頭來刷2014年甚至更早的NOIP-J真題意義何在我認(rèn)為主要有三點(diǎn)第一鞏固基礎(chǔ)思維模型。現(xiàn)在的競賽題目越來越綜合往往一個題融合了多個知識點(diǎn)。而早期的NOIP-J題知識點(diǎn)相對單純就像一個個獨(dú)立的“思維零件”。熟練掌握這些“零件”的運(yùn)作原理比如如何模擬一個過程、如何進(jìn)行窮舉和去重、如何跟蹤程序狀態(tài)是組裝復(fù)雜“機(jī)器”解決綜合題的前提。像“過河”這道題它的模擬思想在游戲AI、自動化調(diào)度等場景中都有體現(xiàn)。第二規(guī)避“想當(dāng)然”的陷阱。老題中很多陷阱設(shè)計得非常經(jīng)典。例如在涉及浮點(diǎn)數(shù)計算的選擇題中考察對精度誤差的理解在閱讀程序題中考察對變量作用域、自增運(yùn)算符前置/后置區(qū)別的掌握。這些細(xì)節(jié)在緊張的比賽環(huán)境中很容易被忽略。通過練習(xí)老題可以養(yǎng)成嚴(yán)謹(jǐn)審題、細(xì)致模擬的習(xí)慣。第三建立信心與節(jié)奏。對于初學(xué)者直接從近年高難度的CSP-S/NOIP提高組題目開始容易產(chǎn)生挫敗感。從早年的普及組真題入手難度曲線更加平緩可以在解決問題的過程中不斷獲得正反饋逐步建立信心。同時可以模擬真實(shí)考試的時間分配練習(xí)如何在有限時間內(nèi)完成選擇題、問題求解和簡單編程題培養(yǎng)比賽節(jié)奏。那么如何高效地利用這些真題進(jìn)行訓(xùn)練呢模擬實(shí)戰(zhàn)限時完成找一個安靜的環(huán)境設(shè)定好90-120分鐘根據(jù)當(dāng)年考試時長像真實(shí)考試一樣完成一套題。不要查資料不要看答案完全獨(dú)立完成。這能最真實(shí)地反映你的當(dāng)前水平。深度復(fù)盤而非對答案做完后對照答案批改只是第一步。更重要的是復(fù)盤每一道錯題和不確定的題。對于選擇題/問題求解問自己我當(dāng)時是怎么想的哪個知識點(diǎn)模糊了是計算粗心還是概念理解有誤把涉及的知識點(diǎn)如組合數(shù)學(xué)公式、邏輯命題、計算機(jī)系統(tǒng)基礎(chǔ)重新梳理一遍。對于閱讀程序題在草稿紙上重新一步一步地“運(yùn)行”程序記錄每個變量在關(guān)鍵節(jié)點(diǎn)后的值。你的錯誤是發(fā)生在哪一步是循環(huán)次數(shù)算錯了還是條件判斷理解反了把這個“單步調(diào)試”的過程練熟。對于編程題如過河問題即使你做對了也要看看標(biāo)程或更優(yōu)的思路。思考我的算法效率如何有沒有邊界情況沒考慮到嘗試用不同的測試數(shù)據(jù)去驗(yàn)證自己程序的魯棒性。歸納總結(jié)形成專題把多套真題中同一類型的題目放在一起看。比如把所有涉及“模擬”的題歸為一類總結(jié)它們的共同特點(diǎn)和解題框架把所有涉及“簡單搜索”的題歸為一類。這樣能幫助你形成知識網(wǎng)絡(luò)下次遇到新題能快速識別出它屬于哪個“題型家族”從而調(diào)用相應(yīng)的解題策略。代碼實(shí)現(xiàn)哪怕題目不要求對于問題求解和閱讀程序題中的邏輯嘗試用代碼把它實(shí)現(xiàn)出來。比如“過河”問題親自寫代碼調(diào)試通過比如邏輯推理題寫一個程序來枚舉所有可能性并驗(yàn)證。這個過程能極大地加深你對問題本質(zhì)和算法過程的理解。最后我想分享一點(diǎn)個人體會。競賽真題尤其是這些相對基礎(chǔ)的題目最大的價值不在于那些具體的答案而在于思考的過程。它強(qiáng)迫你放下對高級算法和庫函數(shù)的依賴回歸到最原始的變量、循環(huán)、條件判斷去構(gòu)建解決方案。這種“從零搭建”的能力是編程內(nèi)功的體現(xiàn)。無論你將來是去做算法研究、軟件開發(fā)還是解決其他領(lǐng)域的復(fù)雜問題這種結(jié)構(gòu)化、邏輯化、步驟化的思維能力都是通用的財富。把每一道老題都吃透弄懂它背后的“為什么”比盲目刷很多新題但一知半解要有效得多。