簡(jiǎn)介西工大noj100題解析項(xiàng)目代碼圍繞西北工業(yè)大學(xué)NOJC/C題庫(kù)的100道練習(xí)題提供配套參考題解與算法實(shí)現(xiàn)適合正在刷題、準(zhǔn)備期末上機(jī)或備考算法的學(xué)生對(duì)照學(xué)習(xí)。壓縮包共3個(gè)文件、大小僅6KB以HTML頁(yè)面為主體內(nèi)含每道題的代碼示例與注釋還附帶inscode項(xiàng)目配置和gitignore文件方便導(dǎo)入開發(fā)環(huán)境按需查看。題解覆蓋遞歸、動(dòng)態(tài)規(guī)劃、貪心等高頻算法思想也針對(duì)素?cái)?shù)判斷、字符串處理、矩陣運(yùn)算等常見題型給出高效解法和優(yōu)化技巧同時(shí)提供模板化代碼與復(fù)習(xí)建議可幫助讀者快速定位薄弱環(huán)節(jié)。這套題解已有198人瀏覽學(xué)習(xí)雖然體量精簡(jiǎn)但濃縮了從基礎(chǔ)語(yǔ)法到進(jìn)階算法的關(guān)鍵內(nèi)容建議讀者先閱讀題解中的思路注釋再動(dòng)手復(fù)現(xiàn)代碼以此加深對(duì)題型和解法的理解。 最近把西工大NOJNorthwestern Polytechnical University Online Judge的前100題完整刷完順手整理成了一個(gè)題庫(kù)解析可運(yùn)行代碼的項(xiàng)目。這個(gè)項(xiàng)目對(duì)我來(lái)說不只是刷題記錄更重要的是把每一道題的思路、易錯(cuò)點(diǎn)、代碼模板沉淀下來(lái)形成一份能反復(fù)查閱的資料。如果你正在刷OJ、學(xué)數(shù)據(jù)結(jié)構(gòu)與算法或者想在校招筆試前快速過一遍常見題型那這份整理方式很值得參考。先說下這個(gè)項(xiàng)目能解決什么問題很多同學(xué)刷OJ的時(shí)候往往是題刷過了就忘了下次遇到同類型的題還是沒思路。我做的這件事就是把前100題按算法主題拆解歸類每題給出思路推導(dǎo)、復(fù)雜度分析、C/C可運(yùn)行代碼并且全部跑通驗(yàn)證過。項(xiàng)目本身用git管理代碼結(jié)構(gòu)清晰方便按需檢索和復(fù)習(xí)。1. 項(xiàng)目啟動(dòng)前先想清楚這100題到底要整理成什么1.1 題目解析的核心價(jià)值不只是“答案”刷OJ最忌諱的就是對(duì)著別人的代碼抄一遍就完事。我在整理這套解析的時(shí)候給自己定了一個(gè)硬性要求每道題必須能回答三個(gè)問題——這題考的是什么知識(shí)點(diǎn)為什么用這個(gè)解法而不是別的代碼里有哪些邊界情況容易踩坑比如NOJ前100題里有很多看似簡(jiǎn)單的模擬題像日期計(jì)算、字符串處理、矩陣操作。這類題入門容易但想一次性ACAccepted很難因?yàn)檫吔鐥l件多。我把這些題的共同坑點(diǎn)抽出來(lái)單獨(dú)整理成“邊界條件自查清單”放在項(xiàng)目文檔里。這樣下次做題前先過一遍清單能少交很多次Wrong Answer。我給自己定的整理原則很簡(jiǎn)單不求多但求每個(gè)題都能講清楚。100道題如果只是貼代碼那這個(gè)項(xiàng)目沒有復(fù)用的價(jià)值只有把思路和坑點(diǎn)寫透三個(gè)月后回頭看還能秒懂才算真正的沉淀。1.2 為什么選擇“題解代碼”的倉(cāng)庫(kù)結(jié)構(gòu)項(xiàng)目初期我猶豫過一陣是寫成一篇一篇的博客還是直接維護(hù)一個(gè)代碼倉(cāng)庫(kù)最后選了后者主要理由有三點(diǎn)。第一代碼倉(cāng)庫(kù)可以保留每一次提交的歷史方便回溯這道題當(dāng)時(shí)是怎么改到AC的。很多題不是一次寫對(duì)的中間會(huì)經(jīng)歷TLE超時(shí)、RE運(yùn)行錯(cuò)誤、WA答案錯(cuò)誤各種狀態(tài)。git的提交記錄天然就是一個(gè)調(diào)試日志。第二代碼和文檔放在同一個(gè)倉(cāng)庫(kù)里查起來(lái)方便。我用“題目編號(hào)題名”命名目錄每個(gè)目錄下有solution.cpp和README.mdREADME里寫清思路和復(fù)雜度。這樣在終端里直接ls就能看到所有題的進(jìn)展比翻博客效率高得多。第三后期可以擴(kuò)展。倉(cāng)庫(kù)跑通之后我可以在同一套結(jié)構(gòu)下繼續(xù)刷200題、300題甚至把代碼從C擴(kuò)展到Python版本完全不需要重構(gòu)。2. NOJ前100題的知識(shí)點(diǎn)地圖與難度分層2.1 按算法類型給題目分組整理完后我對(duì)照了一下NOJ前100題基本覆蓋了OJ平臺(tái)的經(jīng)典題型大致可以分成這幾類輸入輸出與格式處理約占10%看似簡(jiǎn)單但字符串讀取、多組數(shù)據(jù)輸入這些細(xì)節(jié)最容易讓人栽跟頭。模擬與暴力枚舉約占20%純邏輯題考驗(yàn)細(xì)心程度和代碼組織能力。排序與查找約占15%包括快排、歸并、二分查找的變體。貪心算法約占10%難點(diǎn)在于證明貪心策略的正確性以及怎么排序才是最優(yōu)的。搜索DFS/BFS約占15%從最樸素的遞歸到剪枝優(yōu)化都有涉及。動(dòng)態(tài)規(guī)劃約占15%從01背包到最長(zhǎng)上升子序列是區(qū)分度最大的部分。圖論基礎(chǔ)約占10%包括最短路徑Dijkstra、Floyd、最小生成樹、并查集。數(shù)學(xué)與數(shù)論約占5%比如最大公約數(shù)、素?cái)?shù)篩、快速冪。這個(gè)分布其實(shí)很有代表性。它說明前100題不是只考某一種套路而是要求你有一個(gè)完整的算法知識(shí)體系。所以我整理項(xiàng)目時(shí)不是按AC時(shí)間排序而是按知識(shí)點(diǎn)重新組織目錄每一類題集中放在一起方便橫向?qū)Ρ取?.2 同類型題目的共性解法做OJ題目整理最有價(jià)值的事情就是發(fā)現(xiàn)同類型題目的“套路”。比如搜索類題目幾乎都有一個(gè)固定的思考框架先確定搜索狀態(tài)再確定狀態(tài)轉(zhuǎn)移方式最后考慮如何判重或剪枝。我以BFS為例簡(jiǎn)單說明。BFS廣度優(yōu)先搜索適合求最短路徑類的題目因?yàn)樗侵饘訑U(kuò)展的第一次到達(dá)目標(biāo)點(diǎn)時(shí)的步數(shù)一定是最短的。很多同學(xué)寫B(tài)FS時(shí)會(huì)忽略“入隊(duì)時(shí)就要標(biāo)記訪問”而不是“出隊(duì)時(shí)再標(biāo)記”這會(huì)直接導(dǎo)致同一個(gè)節(jié)點(diǎn)被重復(fù)入隊(duì)輕則超時(shí)重則進(jìn)入死循環(huán)。我在項(xiàng)目里專門標(biāo)注了這個(gè)細(xì)節(jié)還給了對(duì)比代碼。再比如動(dòng)態(tài)規(guī)劃類題目關(guān)鍵在于狀態(tài)定義。很多題的狀態(tài)不是平白無(wú)故想出來(lái)的需要從題目中的約束條件反向推導(dǎo)。比如遇到“最多”“最少”“方案數(shù)”這類關(guān)鍵詞大概率是DP題遇到“所有可能”“是否存在”這類關(guān)鍵詞大概率是搜索或DP。這種題型歸類的手感是刷了相當(dāng)數(shù)量之后才有的我把這些判斷標(biāo)準(zhǔn)也寫進(jìn)了每篇解析里。2.3 難度分層與刷題節(jié)奏建議前100題里難度并不是均勻分布的。我按自己的實(shí)際體驗(yàn)把它們分成了三個(gè)梯度入門題約30題主要考察基礎(chǔ)語(yǔ)法、輸入輸出、簡(jiǎn)單模擬。適合剛接觸OJ的同學(xué)熱身目標(biāo)是一天能刷3到5題。進(jìn)階題約45題涉及排序、二分、貪心、簡(jiǎn)單搜索和基礎(chǔ)DP。這是最需要花時(shí)間理解的一批題建議每題控制在1到2小時(shí)內(nèi)。挑戰(zhàn)題約25題包括復(fù)雜搜索、圖論算法、動(dòng)態(tài)規(guī)劃優(yōu)化如滾動(dòng)數(shù)組、狀態(tài)壓縮。這類題即使有思路寫代碼也容易出錯(cuò)建議留出整塊時(shí)間專門攻克。這個(gè)分類我直接在項(xiàng)目目錄上用文件夾前綴標(biāo)注了比如01-basic、02-intermediate、03-advanced。刷的時(shí)候可以先從基礎(chǔ)部分找信心再逐步提升難度不會(huì)因?yàn)橐簧蟻?lái)就碰到硬骨頭而勸退。3. 實(shí)操記錄搭建題目解析項(xiàng)目的過程3.1 目錄結(jié)構(gòu)與文件命名規(guī)范項(xiàng)目的目錄結(jié)構(gòu)我最終定成這樣noj-100/ ├── README.md ├── 01-basic/ │ ├── 1001-hello-world/ │ │ ├── solution.cpp │ │ └── README.md │ ├── 1002-a-plus-b/ │ │ ├── solution.cpp │ │ └── README.md │ └── ... ├── 02-intermediate/ ├── 03-advanced/ ├── templates/ │ ├── bfs_template.cpp │ ├── dfs_template.cpp │ └── dij_template.cpp └── scripts/ └── run_all.sh文件命名上我用“題號(hào)簡(jiǎn)短題名”作為目錄名這樣既不會(huì)丟失原始題目的辨識(shí)度又能通過目錄名快速判斷這題大概在說什么。templates目錄放的是我自己總結(jié)的算法模板刷題時(shí)直接復(fù)制改改就能用。run_all.sh這個(gè)腳本是我后加的“偷懶利器”作用很簡(jiǎn)單遍歷所有題目目錄編譯并運(yùn)行每個(gè)solution.cpp根據(jù)退出碼判斷是否通過。這樣我每改完一道題可以直接腳本跑一遍全集確保改動(dòng)沒有破壞其他題目的代碼。3.2 每道題的README模板剛開始我寫解析時(shí)內(nèi)容寫得比較隨意后期回看發(fā)現(xiàn)好多已經(jīng)看不懂當(dāng)時(shí)想表達(dá)什么了。所以我給每道題統(tǒng)一了一個(gè)README模板# 題目編號(hào)-題目名稱 ## 題目大意 一句話概括題目在問什么不超過兩行。 ## 思路分析 - 這題屬于哪類問題 - 核心解法是什么 - 為什么這樣解是正確的 ## 復(fù)雜度 - 時(shí)間復(fù)雜度O(xxx) - 空間復(fù)雜度O(xxx) ## 易錯(cuò)點(diǎn) - 邊界條件1 - 邊界條件2 ## 代碼思路 關(guān)鍵代碼段的解釋不超過五句話。這個(gè)模板看起來(lái)很樸素但它逼著我用最精簡(jiǎn)的語(yǔ)言把每道題想清楚。尤其是“思路分析”和“易錯(cuò)點(diǎn)”兩部分寫的時(shí)候其實(shí)是逼自己再過一遍整個(gè)思考過程這比單純把AC代碼貼上去有用得多。3.3 測(cè)試與驗(yàn)證確保每一份代碼都能跑項(xiàng)目里最核心的一條原則是代碼必須能編譯運(yùn)行不能只是“看起來(lái)對(duì)”。我每寫完一道題的解析都會(huì)做以下三步驗(yàn)證用編譯器編譯確保零警告通過我用的-Wall -Wextra參數(shù)警告也當(dāng)錯(cuò)誤處理。用樣例輸入跑一遍比對(duì)輸出。自己構(gòu)造幾組邊界測(cè)試數(shù)據(jù)比如最大輸入規(guī)模、空輸入、只有一個(gè)元素的情況。有一條命令我強(qiáng)烈建議加進(jìn)自己的刷題流程g -stdc17 -Wall -Wextra -o solution solution.cpp ./solution test_input.txt這樣能一次性完成編譯加測(cè)試。如果沒有現(xiàn)成的測(cè)試用例提前準(zhǔn)備好test_input.txt是個(gè)好習(xí)慣能省下大量反復(fù)提交平臺(tái)的時(shí)間。4. 代碼倉(cāng)庫(kù)管理與git協(xié)作經(jīng)驗(yàn)4.1 初始化倉(cāng)庫(kù)與分支策略做這類個(gè)人項(xiàng)目git管理不需要搞得很復(fù)雜但基礎(chǔ)的模式還是要建立起來(lái)。我的做法是倉(cāng)庫(kù)只保留一個(gè)main分支所有改動(dòng)直接提交到主干但每次提交的commit message寫清楚是“新增/修復(fù)/重構(gòu)”。比如git init git add . git commit -m feat: 完成1001題的題解和代碼如果中途發(fā)現(xiàn)某道題代碼有bug修完后我會(huì)單獨(dú)提交一條git commit -m fix: 修正1001題的邊界判斷邏輯這種簡(jiǎn)單的提交規(guī)范看起來(lái)不起眼但當(dāng)倉(cāng)庫(kù)積累了上百次提交之后查歷史、回退版本都很方便。想找某道題什么時(shí)候改過直接git log -- 1001-hello-world/就能定位。4.2 把常用代碼抽到公共目錄整理到后面我發(fā)現(xiàn)一個(gè)問題很多題的代碼結(jié)構(gòu)高度相似比如都需要快讀、都需要封裝一個(gè)gcd函數(shù)。如果每題都復(fù)制粘貼一遍不僅代碼冗余后期想改公共邏輯還得全局搜索替換。于是我在項(xiàng)目里增加了templates/和include/這兩個(gè)目錄。templates/放算法模板include/放公共頭文件。C代碼里可以通過相對(duì)路徑引入自己寫的頭文件#include ../include/common.h這里有個(gè)小坑需要提醒一下OJ平臺(tái)提交代碼時(shí)通常不支持除了標(biāo)準(zhǔn)庫(kù)之外的本地頭文件所以我提交到平臺(tái)前會(huì)把公共代碼手動(dòng)內(nèi)聯(lián)進(jìn)solution.cpp。我在項(xiàng)目里特意加了一個(gè)scripts/inline.sh腳本自動(dòng)把#include ../include/common.h替換成對(duì)應(yīng)頭文件的實(shí)際內(nèi)容這樣既能本地保持代碼整潔又能一鍵生成可直接提交的單文件版本。4.3 關(guān)于分支協(xié)作的補(bǔ)充如果后續(xù)你想把這套項(xiàng)目開放給同學(xué)一起維護(hù)建議不要直接在main上推來(lái)推去。最簡(jiǎn)單的協(xié)作流程是每個(gè)人從main拉一個(gè)功能分支比如feat/1002-solution做完后提PR合并回主干。這個(gè)模式在GitHub/Gitee上都是標(biāo)準(zhǔn)操作能避免兩個(gè)人同時(shí)改同一個(gè)文件導(dǎo)致的沖突。就算目前只有你自己在維護(hù)養(yǎng)成“先在分支上改測(cè)試通過再合并”的習(xí)慣也能明顯減少翻車的概率。我就有過直接在main上改代碼手滑刪掉了一個(gè)大括號(hào)導(dǎo)致后面好幾道題都編譯失敗的經(jīng)歷教訓(xùn)還是挺深刻的。5. 常見問題與排查技巧實(shí)錄5.1 編譯報(bào)錯(cuò)與警告C題解最常見的報(bào)錯(cuò)就是少頭文件或命名空間問題。我的建議是不要依賴競(jìng)賽模板里的using namespace std;僥幸通過而是顯式使用std::前綴或者明確列出需要的頭文件。這樣在NOJ這種嚴(yán)格編譯器環(huán)境下不容易因?yàn)榄h(huán)境差異導(dǎo)致編譯失敗。另外如果你用-Wall -Wextra編譯能看到警告強(qiáng)烈建議不要忽略它。比如“未使用的變量”“有符號(hào)數(shù)和無(wú)符號(hào)數(shù)比較”這類警告往往是隱藏bug的前兆。我遇到過最典型的就是int和size_t比較導(dǎo)致的死循環(huán)編譯不報(bào)錯(cuò)但運(yùn)行就是不對(duì)查了半天才發(fā)現(xiàn)是類型隱式轉(zhuǎn)換的問題。5.2 超時(shí)TLE與死循環(huán)TLE是OJ刷題中特別讓人崩潰的錯(cuò)誤。通常原因有兩種算法復(fù)雜度太高或者代碼里有隱藏的死循環(huán)。我在項(xiàng)目里專門記錄了幾次排TLE的過程。最典型的一次是BFS題目沒有在入隊(duì)時(shí)標(biāo)記訪問狀態(tài)導(dǎo)致同一個(gè)節(jié)點(diǎn)被反復(fù)加入隊(duì)列數(shù)據(jù)規(guī)模一大就直接超時(shí)。這個(gè)坑在上面提到過但再說一遍完全有必要因?yàn)樗[蔽了看代碼邏輯時(shí)很難一眼發(fā)現(xiàn)。排查TLE的小技巧是先在本地生成最大規(guī)模的數(shù)據(jù)跑一遍如果本地就要好幾秒那平臺(tái)大概率超時(shí)。這時(shí)優(yōu)先考慮優(yōu)化算法而不是優(yōu)化常數(shù)。比如把cin/cout換成scanf/printf能快一些但根本問題還是要從算法復(fù)雜度上解決。5.3 數(shù)組越界與段錯(cuò)誤數(shù)組越界是C里最常見的運(yùn)行時(shí)錯(cuò)誤尤其在OJ題里題目給的數(shù)組最大長(zhǎng)度是10^5你開了一個(gè)100000的數(shù)組但實(shí)際訪問了下標(biāo)100000直接段錯(cuò)誤。我的做法是定義數(shù)組大小時(shí)在原題要求的基礎(chǔ)上多加5到10個(gè)空間。比如題目說最多10^5個(gè)元素我就用const int MAXN 100000 5;。這種做法雖然看起來(lái)不夠精確但能有效避免由于邊界判斷失誤導(dǎo)致的越界訪問屬于性價(jià)比極高的防御性編程。5.4 結(jié)果錯(cuò)誤WA的排查路徑如果代碼編譯通過、運(yùn)行不崩潰、但答案就是不對(duì)按下面這個(gè)順序排查會(huì)快很多先用題目給的樣例輸入確認(rèn)樣例輸出完全匹配。自己構(gòu)造和題目描述極端情況一致的測(cè)試數(shù)據(jù)比如全0、最大值、最小值。檢查是否有多余輸出或格式錯(cuò)誤比如多打了一個(gè)空格、少換了行。檢查算法邏輯里的邊界條件尤其是循環(huán)的起止下標(biāo)是否差1。如果還是查不出來(lái)再用二分定位法注釋掉大段邏輯只保留最小可測(cè)部分逐步加回代碼鎖定問題產(chǎn)生的代碼塊。這種方法雖然原始但大多數(shù)WA都能靠它在一兩輪內(nèi)解決。真正難的WA往往是思路層面的漏洞比如貪心策略不對(duì)、狀態(tài)轉(zhuǎn)移方程寫錯(cuò)了這種就不是調(diào)試能解決的需要回到紙面上重新推導(dǎo)。6. 最后的幾點(diǎn)實(shí)操心得把這一整套項(xiàng)目做完我最深的感受是刷OJ的收益很大程度上不取決于刷了多少題而取決于你整理了多少題。形式化的記錄比如貼個(gè)AC代碼幾乎沒有復(fù)習(xí)價(jià)值只有把“為什么這么做”寫清楚把“易錯(cuò)點(diǎn)在哪兒”標(biāo)注出來(lái)這個(gè)項(xiàng)目才真正變成自己的知識(shí)庫(kù)。如果你也打算整理自己的刷題項(xiàng)目我的建議是先別追求面面俱到從10道題開始跑通流程把目錄結(jié)構(gòu)、README模板、git提交規(guī)范都定好后面只是機(jī)械地填充內(nèi)容而已。畢竟100道題的整理工作量不小流程順了才能堅(jiān)持到最后。本文還有配套的精品資源點(diǎn)擊獲取