說來也巧每年到這個階段總有學(xué)弟學(xué)妹跑到我這兒問同一個問題東華OJ的基礎(chǔ)題刷到六十幾題了卡在69到73這一片代碼寫了、樣例也過了一提交就是紅紅的WA心態(tài)直接崩掉。我當年也是從這條路上趟過來的所以今天專門寫一篇把這五道題掰開揉碎聊一聊。不管你卡在哪一題、是C還是C選手、甚至用Python刷這份思路都適用。先說清楚東華OJ是什么。它是東華大學(xué)在線的編程評測系統(tǒng)題目按難度和專題排列前面六十多題基本把輸入輸出、分支循環(huán)、數(shù)組字符串這些基礎(chǔ)語法都過了一遍。做到69到73題這個位置意味著你已經(jīng)跨過了“能寫代碼”的門檻開始進入“用代碼解決具體問題”的階段。這組題我不能把原題照抄出來但可以負責任地講它們都屬于一個典型專題——數(shù)組、數(shù)字處理和循環(huán)模擬的綜合應(yīng)用。這篇文章會用這五題的常見考法做樣例把每一類題的分析思路、代碼寫法和調(diào)試技巧全部分享出來。1. 東華OJ基礎(chǔ)題69-73內(nèi)容定位與考察方向1.1 從題號安排看這組題的定位東華OJ的題號順序基本和知識點推進順序一致。前面幾題考順序結(jié)構(gòu)、簡單計算中間開始考分支和循環(huán)到了60到70這個區(qū)間數(shù)組正式登場。你可能已經(jīng)注意到從這附近開始題面變長了不再是一句話講完“輸入一個數(shù)輸出一個數(shù)”而是給你一段完整的場景描述比如“輸入n個整數(shù)按要求處理后輸出”。69到73這五題在這個區(qū)間里扮演的角色很特殊。它們不是純數(shù)組題也不是純數(shù)學(xué)題而是把數(shù)組、循環(huán)、條件判斷、數(shù)字拆分這些東西混在一起考。這正是OJ出題最喜歡的手法和真實場景下寫代碼最常遇到的情況——你很少會只用一個知識點解決一個完整問題。我翻了一下自己做題時候的記錄和跟別人對題目的討論這五題里出現(xiàn)過的知識點主要集中在這幾個方面從一行輸入中讀入多個整數(shù)并存入數(shù)組對數(shù)組進行遍歷、篩選、統(tǒng)計把一個多位數(shù)拆成各個數(shù)位再重組在循環(huán)里維護一個“當前最值”或者“累計結(jié)果”。這些東西單獨拿出來你基本都會但合在一起、再加上OJ嚴格的格式判定就成了新手殺手。1.2 基礎(chǔ)題背后真正想考的東西說實話東華OJ這五道題本身的算法難度并不高任何一道放到競賽里都屬于送分題。但為什么這么多人在這一片卡住因為從這一組題開始OJ不再考你“語法會不會”而是考你“思路清不清楚、代碼嚴不嚴謹”。舉個例子數(shù)字拆分這類題很多人第一反應(yīng)是用字符串處理讀一個整數(shù)轉(zhuǎn)成字符串再一位一位取。這個思路在本地跑完全沒問題但東華OJ這類題目的輸入約定往往是“每行一個整數(shù)可能包含多行”而且數(shù)字范圍是int范圍內(nèi)字符串處理反而容易在格式和轉(zhuǎn)換上出幺蛾子。更穩(wěn)的做法是用除法和取余運算把每一位摳出來這也是這一類題目默認的標準方法。這五題集中訓(xùn)練的是三種能力。第一把題目描述翻譯成變量和操作的能力比如“統(tǒng)計個位數(shù)為某個數(shù)的數(shù)字個數(shù)”這句話你要能立刻想到用n % 10判斷個位第二循環(huán)邊界控制能力比如“共T組數(shù)據(jù)”和“讀到文件末尾EOF”是兩種不同的輸入方式對應(yīng)完全不同的循環(huán)寫法第三輸出格式的強迫癥級嚴謹度空格、換行、最后一個數(shù)后面要不要空格這些細節(jié)直接決定你能不能AC。2. 解題前的準備工作讀題、設(shè)計、復(fù)雜度估算2.1 三遍讀題法樣例不是擺設(shè)我看到太多人做OJ題目的姿勢不對題目掃一眼覺得看懂了直接開寫寫完拿樣例跑一下對了就交錯了就懵。這種做法在基礎(chǔ)題階段還能靠運氣混過去到了69-73這種綜合題十有八九要栽。我自己的習慣是三遍讀題法這么多年帶人刷題一直推薦給新手反饋很好。第一遍快速瀏覽題面只搞清楚三個問題輸入是什么、輸出是什么、中間要做什么操作。這一遍不追求理解所有細節(jié)但要能用自己的話把題目復(fù)述一遍。第二遍從頭精讀重點關(guān)注約束條件和邊界描述。比如“正整數(shù)”意味著你不用處理負數(shù)和零“n不超過100”意味著你甚至可以用最暴力的方法“如果不存在則輸出-1”這種話就是典型的邊界陷阱很多人漏看的都是這種補丁說明。第三遍拿著樣例手動模擬。把樣例輸入里的數(shù)據(jù)按你理解的流程在草稿紙上走一遍看能不能得到樣例輸出。這一步是性價比最高的排查方式。你代碼還沒寫思路里的邏輯漏洞就已經(jīng)暴露出來一大半。我見過一個特別典型的例子一道題要求“輸出排序后的結(jié)果每個數(shù)之間用一個空格隔開”樣例輸出是1 2 3看起來人畜無害。但提交后WA了十幾次最后發(fā)現(xiàn)題目在輸出格式里寫的是“行末不要有多余空格”而他的代碼在最后一個數(shù)后面也打了個空格。這就是樣例不會告訴你、但評測系統(tǒng)一定會檢查你的地方。2.2 復(fù)雜度心里要有數(shù)“這題我能不能暴力解”是每個刷OJ的人都問過的問題。答案是看數(shù)據(jù)范圍。東華OJ基礎(chǔ)題的n通常非常小幾十到幾百的量級O(n2)的算法跑起來毫無壓力。但這不代表你可以完全不顧算法效率因為這一片題目里經(jīng)常出現(xiàn)“多組輸入”的情況。比如一道題說“輸入數(shù)據(jù)有多組每組第一行為一個正整數(shù)n”但沒有告訴你一共有多少組。如果單組內(nèi)你做的是O(n2)的冒泡排序n只有100那沒問題可如果題目沒有明說n的范圍或者n能到10的5次方甚至更大O(n2)就會超時。我給新手的建議是寫代碼之前先花三十秒估算一下最外層循環(huán)大概執(zhí)行多少次、里面還有沒有嵌套循環(huán)、總的計算量在什么量級。如果總量超過一億次就得思考能不能優(yōu)化?；A(chǔ)題階段你大概率用不到什么高級算法但“用桶計數(shù)替代雙重循環(huán)查找”這種技巧在數(shù)組統(tǒng)計類題目里非常常見69-73這組題里就有類似的考法。另外別因為數(shù)據(jù)弱就放飛自我。養(yǎng)成計算復(fù)雜度的習慣等到后面刷中檔題的時候你會感謝自己現(xiàn)在多花的這三十秒。3. 核心知識點逐個擊破3.1 數(shù)字拆分與重組基礎(chǔ)中的基礎(chǔ)數(shù)字拆分是東華OJ從基礎(chǔ)到進階反復(fù)出現(xiàn)的知識點69-73里基本一定會涉及。所謂數(shù)字拆分就是給定一個整數(shù)把它的個位、十位、百位……一位一位分離出來做處理。標準做法是用取余和整除循環(huán)#include stdio.h int main() { int n; while (scanf(%d, n) ! EOF) { int sum 0; while (n 0) { sum n % 10; // 取出當前最低位 n / 10; // 去掉最低位 } printf(%d\n, sum); } return 0; }這段代碼做的事情很直觀n % 10拿到當前個位n / 10把個位砍掉循環(huán)直到n變成0。比如n12345過程就是取出5、4、3、2、1最后sum15。實際操作中有三個細節(jié)容易翻車。第一如果輸入的n本身就是0上面這個循環(huán)一次都不會執(zhí)行sum就是0這個沒問題。但如果題目要求“逆序輸出數(shù)字”n0時你應(yīng)該輸出0而不是什么都不輸出這時候就要用do-while而不是while。第二負數(shù)的取余在不同語言里行為不一樣C語言里-5 % 10結(jié)果是-5所以如果題目里沒說n是正整數(shù)最好先把負數(shù)轉(zhuǎn)成正數(shù)處理或者用絕對值。第三如果題目要求把拆出來的數(shù)位再重組比如“把各位數(shù)字逆序排列后輸出”你要注意前導(dǎo)零的問題比如1020逆序變成0201輸出的時候要不要保留0完全取決于題目描述。3.2 數(shù)組存值、統(tǒng)計與最值處理到了69-73這組題數(shù)組操作是躲不開的。常見的考法有這么幾類讀入n個數(shù)存入數(shù)組然后做某種篩選或者直接不存數(shù)組邊讀邊處理。這兩種思路的效率差別不大但代碼復(fù)雜度差別很大。給你一個建議需要“先全部讀入再統(tǒng)一處理”的題老老實實開數(shù)組存可以“邊讀邊算”的題就別浪費內(nèi)存。比如求一組數(shù)的最大值和次大值其實不需要數(shù)組#include stdio.h int main() { int n, i, x; while (scanf(%d, n) ! EOF) { int max1 -1, max2 -1; // 假設(shè)數(shù)據(jù)都是非負數(shù) for (i 0; i n; i) { scanf(%d, x); if (x max1) { max2 max1; max1 x; } else if (x max2) { max2 x; } } printf(%d %d\n, max1, max2); } return 0; }這段代碼的巧妙之處在于只用兩個變量就完成了最大值和次大值的維護。每一步更新的時候如果當前數(shù)比最大值還大原來的最大值就“降級”成次大值如果當前數(shù)介于兩者之間只更新次大值。這個過程實際上就是一次遍歷里同時維護兩個排序狀態(tài)比“先存數(shù)組再排序再取前兩個”的要快而且不需要額外空間。另一種高頻考法是“統(tǒng)計類”比如統(tǒng)計每個數(shù)字出現(xiàn)的次數(shù)。這種題最標準的解法是桶計數(shù)開一個數(shù)組下標當數(shù)字本身數(shù)組值當次數(shù)。比如統(tǒng)計n個1到100之間的整數(shù)中每個數(shù)出現(xiàn)了幾次int count[101] {0}; for (int i 0; i n; i) { scanf(%d, x); count[x]; }這個思路之所以重要是因為它在O(n)時間內(nèi)完成了統(tǒng)計而如果每次查詢都去遍歷原數(shù)組復(fù)雜度就是O(n*m)數(shù)據(jù)稍大就會超時。桶計數(shù)的本質(zhì)是用空間換時間在數(shù)據(jù)范圍有限的時候非常實用。3.3 循環(huán)嵌套與多組輸入的寫法東華OJ從基礎(chǔ)題開始就很喜歡考“多組測試數(shù)據(jù)”69-73也不例外。很多在這五題上翻車的人問題不是出在業(yè)務(wù)邏輯上而是連最外層輸入循環(huán)的寫法都沒掌握。最常見的兩種輸入模式你要爛熟于心。第一種題目明確說“第一行是一個整數(shù)T表示測試數(shù)據(jù)的組數(shù)”這種寫起來最簡單int T; scanf(%d, T); while (T--) { // 處理一組數(shù)據(jù) }第二種題目說“輸入包含多組測試數(shù)據(jù)處理到文件末尾”這種要配合scanf的返回值來判斷int n; while (scanf(%d, n) ! EOF) { // 處理一組數(shù)據(jù) }這里的關(guān)鍵是理解scanf的返回值它返回成功讀取的變量個數(shù)讀不到數(shù)據(jù)時返回EOF即-1。所以while (scanf(...) ! EOF)的意思就是“只要能讀到數(shù)據(jù)就一直處理”這樣就不需要用戶手動輸入一個終止標記。還有一個非常常見的坑多組數(shù)據(jù)之間變量沒有重置。比如求每組數(shù)據(jù)的和如果你把sum定義在while循環(huán)外面又沒有在每組開始時清零那第二組數(shù)據(jù)的和就會把第一組的結(jié)果累加進去結(jié)果自然錯得離譜。記住一條鐵律任何“每組數(shù)據(jù)獨立”的變量都要在循環(huán)體內(nèi)部定義或者每輪循環(huán)開始前初始化。4. 判題反饋與調(diào)試實錄4.1 常見判題結(jié)果到底在說什么提交代碼之后OJ會返回一個判題結(jié)果。很多新手看到紅字就慌其實每一種結(jié)果的含義完全不同排查方向也是天差地別。我按東華OJ常見的幾種反饋給你列一張表。判題結(jié)果含義重點排查方向Accepted代碼通過不用排查做下一題Wrong Answer答案錯誤算法邏輯、邊界條件、輸出格式Runtime Error運行時錯誤數(shù)組越界、除零、遞歸過深Time Limit Exceeded超時算法復(fù)雜度太高、死循環(huán)Compile Error編譯錯誤語法問題、頭文件缺失、函數(shù)名拼寫Presentation Error格式錯誤空格、換行與要求不一致這里我重點講一下Presentation Error因為這道題區(qū)間里太容易觸發(fā)了。PE和WA的區(qū)別在于你輸出的內(nèi)容在數(shù)值上是對的但輸出格式和題目要求不完全一致。比如多打了一個空格、少打了一個換行、行末多了個空格。我當年帶過一個學(xué)弟一道“輸出n個整數(shù)之和”的題他犯的錯是每組數(shù)據(jù)之間多打了一個空行。他自己看輸出覺得“差不多”但OJ不認識“差不多”它拿你的輸出和標準答案逐字符比對一個字符不一樣就是WA或者PE。所以寫輸出的時候一定要跟題目要求的字節(jié)級格式對齊。4.2 我是怎么定位“答案錯誤”的WA是刷OJ路上最常見的反饋也是新手最難解決的因為OJ只告訴你“錯了”卻不告訴你“哪里錯了”。在處理69-73這幾題時我的排查套路已經(jīng)固定下來了你照做能省一大半時間。第一步重新讀題。不是掃一眼是精讀。重點看三塊數(shù)據(jù)范圍有沒有限制比如是否可能為0、負數(shù)、輸出格式有沒有特殊要求比如“行末無空格”、“每組數(shù)據(jù)后跟一個空行”、有沒有隱含條件比如“按輸入順序輸出”而不是“按從小到大輸出”。第二步自造邊界測試數(shù)據(jù)。樣例給的數(shù)據(jù)往往很溫和你要自己制造極端情況。比如n1時能不能過n100且所有數(shù)都一樣時能不能過最小值和最大值出現(xiàn)時能不能過我之前幫人調(diào)一道統(tǒng)計題樣例全過但n1時直接崩了因為代碼里假設(shè)了“至少有兩個數(shù)”才去求次大值。這種問題只有邊界測試能暴露出來。第三步打表調(diào)試。在關(guān)鍵位置加printf輸出中間變量把程序的實際執(zhí)行過程“看”一遍printf(debug: i%d, x%d, max1%d, max2%d\n, i, x, max1, max2);看完之后記得刪掉這些調(diào)試代碼不然這些多余的輸出會讓你直接WA。第四步如果你的邏輯實在看不出破綻重新審視“每輪循環(huán)變量重置”問題。這是多組輸入題目里最隱蔽的坑。我自己的經(jīng)驗里至少有三分之一幫別人排查的WA最后都是“某個變量忘了清零”導(dǎo)致的。4.3 提交前必查清單我在東華OJ刷到后面養(yǎng)成了一個習慣寫完整段代碼之后先不急著交按一份固定清單自查一遍。這套習慣幫我減少了很多無效提交。清單內(nèi)容如下。數(shù)組開得夠不夠大如果題目說n最大1000就開1005而不是1000留一點余量防越界。變量是否初始化全局變量默認是0但局部變量默認是隨機值局部變量不初始化是新手最常見的RE來源。循環(huán)條件是否正確是i n還是i n是while (T--)還是while (T)這種差一個字符的bug最難查。scanf有沒有加給int變量讀值漏了在本地可能碰巧不崩但在OJ上幾乎必RE。輸出格式是否逐字核對空格、換行、冒號、逗號全都要跟題目要求一致。多組數(shù)據(jù)的變量重置是否完成每一輪循環(huán)開始時的狀態(tài)是否干凈。int會不會溢出如果累加結(jié)果可能超過21億就換成long long。這套清單看起來都是小細節(jié)但OJ就是這么不留情面一個字符的差異就能讓你的通過率從100%變0%。5. 新手排錯速查與避坑心得5.1 高頻問題對照表把69-73這組題里我見過、以及我自己踩過的高頻問題匯總一下做成速查表提交WA的時候拿出來對照效率很高。癥狀可能原因解決方案樣例能過但提交WA邊界條件沒處理補測n1、n最大值、全同數(shù)據(jù)等邊界多組數(shù)據(jù)時答案越算越離譜累計變量沒清零把sum、count等變量移到循環(huán)內(nèi)定義輸出結(jié)果正確但格式被打回來行末空格或空行不匹配核對題目輸出說明最后一個數(shù)不打印空格運行直接崩數(shù)組越界檢查數(shù)組大小確認下標從0還是從1開始結(jié)果全是同一數(shù)值忘了讀入新數(shù)據(jù)檢查scanf是否寫在了循環(huán)里面且每次執(zhí)行所有輸出都比預(yù)期大一點多個樣例累計沒清空每輪處理前把結(jié)果變量重置為初始值這里的每一條都是我或者我?guī)н^的人真真切切踩過的。以前總覺得“這種低級錯誤怎么會犯”真到OJ上熬夜調(diào)代碼的時候才發(fā)現(xiàn)低級錯誤反而是最消耗時間的。5.2 幾條專門講給新手的經(jīng)驗最后分享幾條我刷東華OJ多年的經(jīng)驗算不上什么高深技巧但都是實戰(zhàn)里反復(fù)驗證過的。第一本地編譯器能跑不等于OJ能過。本地你的代碼可能依賴了一個沒有初始化的變量的“幸運值”這在你的電腦上碰巧是0在OJ的編譯器上就成了隨機數(shù)。所以寫代碼的時候別依賴任何未初始化的狀態(tài)老老實實把變量都賦值。第二代碼能寫出來之后花一分鐘手動推演一遍。這一步不能省尤其是循環(huán)嵌套的題目。你把第一次循環(huán)、最后一次循環(huán)分別手動跑一遍能抓住80%的邊界問題。我教過的一個學(xué)生每次寫循環(huán)都會差一個數(shù)后來我強制他每次寫代碼都推演首尾兩次循環(huán)這個問題基本絕跡。第三調(diào)試用的printf一定要刪干凈。這不是玩笑。有一次我調(diào)完代碼忘記刪調(diào)試輸出交上去WA盯著判題結(jié)果發(fā)呆了十分鐘才反應(yīng)過來。建議把調(diào)試代碼統(tǒng)一加一個特征標記比如printf(DBG...)最后全局搜索“DBG”一次清干凈。第四如果你實在卡在一個題超過兩小時別硬扛。去洗把臉、走一走或者換一道簡單題做做給自己二十分鐘的緩沖。很多次我都是離開了屏幕再回來突然想起“啊那個數(shù)據(jù)可能是多組”一下就解決了?？}的時候最怕鉆牛角尖走出去反而能讓大腦切換狀態(tài)。東華OJ基礎(chǔ)題69-73這五道題難點不在算法而在“嚴謹”二字。數(shù)據(jù)怎么讀、循環(huán)怎么控制、格式怎么輸出、邊界怎么防護每一環(huán)都嚴絲合縫才能換來一個綠色的Accepted。把這五道題吃透你不僅是拿到了幾道題的AC記錄更重要的是建立了面對OJ題目的系統(tǒng)化排查思維。這套思維往后做任何題目都用得上包括后面那些真正的算法題。