簡(jiǎn)介面向北大POJ初學(xué)者的C題解集合涵蓋從1000到1008、1011到1014以及1016、1017等百余道基礎(chǔ)題目覆蓋簡(jiǎn)單模擬、數(shù)學(xué)推理、字符串處理、動(dòng)態(tài)規(guī)劃等常見入門算法方向可作為算法競(jìng)賽起步階段的代碼參考。壓縮包為RAR格式共157個(gè)文件其中156個(gè)為cpp源代碼文件另有1個(gè)txt說明文件整體僅59KB便于下載后快速查找與使用。代碼按題目編號(hào)獨(dú)立組織每個(gè)cpp文件對(duì)應(yīng)一道POJ題目讀者可對(duì)照題目需求直接編譯運(yùn)行驗(yàn)證解法邏輯并參考不同題目的實(shí)現(xiàn)思路從中對(duì)比同類問題的不同處理方式。資源已有2653人學(xué)習(xí)適合ACM入門者、算法練習(xí)者在刷題遇到瓶頸時(shí)查閱也可作為課程設(shè)計(jì)或競(jìng)賽訓(xùn)練的輔助題庫幫助系統(tǒng)積累基礎(chǔ)題型的代碼范式節(jié)省從零編寫和調(diào)試的時(shí)間無論自學(xué)還是備賽都具有參考價(jià)值。1. POJ基礎(chǔ)刷題卡住時(shí)這份參考答案就是一張地圖一個(gè)周末晚上我在POJ上刷一道模擬題本地隨便測(cè)都是對(duì)的一提交就是Wrong Answer翻來覆去改了快一小時(shí)沒找到錯(cuò)在哪。這種經(jīng)歷在ACM基礎(chǔ)刷題階段幾乎人人都會(huì)碰到不是不會(huì)寫代碼而是不知道OJ判題到底在跑什么。這份“北大POJ部分題目答案”收錄了一批基礎(chǔ)典型題目的AC代碼從輸入輸出、模擬、搜索到圖論入門都有涉及特別適合剛注冊(cè)賬號(hào)準(zhǔn)備刷題的新手——卡住的時(shí)候打開對(duì)應(yīng)題號(hào)的代碼照著編譯、對(duì)著輸出通常一眼就能看出自己的問題。2. 資源全貌按題號(hào)組織的代碼包與題目覆蓋地圖2.1 目錄結(jié)構(gòu)每個(gè)題號(hào)一個(gè)文件夾提交只需一個(gè)cpp拿到手先看整體。這類刷題整理包解壓出來通常是按題號(hào)分目錄的因?yàn)镻OJ提交時(shí)不支持子目錄本地放一個(gè)文件夾方便自己歸檔。常見的組織方式長這樣POJ-basic-answers/ ├── 1000-AB/ │ ├── 1000.cpp │ └── readme.txt ├── 1001-Exponentiation/ │ ├── 1001.cpp │ └── readme.txt ├── 1006-Biorhythms/ │ └── 1006.cpp ├── 1008-Maya-Calendar/ │ └── 1008.cpp ├── 1028-Web-Navigation/ │ └── 1028.cpp ├── 1088-Ski/ │ └── 1088.cpp ├── 1258-Agri-Net/ │ └── 1258.cpp └── README.md看到這個(gè)結(jié)構(gòu)就能明白這份資源不是排版精美的教程PDF而是刷題過程中真實(shí)積累下來的源碼包。每個(gè).cpp都是可直接提交到POJ的完整代碼readme.txt通常是題目大意、思路筆記或者當(dāng)時(shí)的調(diào)試記錄README.md則是整個(gè)包的索引。提交時(shí)只需要把對(duì)應(yīng)cpp的內(nèi)容復(fù)制到網(wǎng)頁提交框里即可文件夾本身只是為了本地好分類。正因?yàn)樗恰按鸢赴倍皇恰邦}解書”所以代碼里保留了刷題者當(dāng)時(shí)的習(xí)慣——變量命名可能不講究注釋也可能只有一兩行但優(yōu)點(diǎn)是每道題都能編譯能跑適合拿來對(duì)照而不是拿來背。2.2 題目覆蓋從輸入輸出到算法入門的完整跨度包里的題目不算多但覆蓋范圍拎出來正好是POJ基礎(chǔ)題的高頻考點(diǎn)。我挑了六道有代表性的列成一張表你能直觀看到這份資源的性價(jià)比題號(hào)類型核心考點(diǎn)典型坑點(diǎn)1000輸入輸出scanf/printf 與 EOF 循環(huán)多組數(shù)據(jù)處理1001高精度大數(shù)乘方、小數(shù)點(diǎn)位處理末尾零和整數(shù)部分為零1006數(shù)論同余方程組結(jié)果取模修正1008模擬兩種歷法互轉(zhuǎn)月份天數(shù)表寫錯(cuò)1088DP/遞歸記憶化搜索遞歸深度和方向數(shù)組1258圖論Kruskal 并查集多組數(shù)據(jù)重置并查集從這張表能看出一個(gè)明顯的階梯先過輸入輸出關(guān)再寫模擬題鍛煉邏輯接著進(jìn)入遞歸和搜索最后上手經(jīng)典圖論算法。這正是ACM刷題從零到一的主流路線也是很多開發(fā)者在準(zhǔn)備算法筆試時(shí)走的捷徑。資源里收錄的“基礎(chǔ)題”不是那種隨便寫兩行的水題而是每道都有固定套路、值得反復(fù)揣摩的入門題。2.3 讀答案的正確姿勢(shì)先想后看逐段注釋這類答案包最大的風(fēng)險(xiǎn)是讓人直接抄。如果只把代碼復(fù)制粘貼提交拿AC那這個(gè)包對(duì)你的價(jià)值基本歸零。我拿到這份資源以后給自己定了個(gè)使用流程拿到一個(gè)題目編號(hào)先不打開答案自己在編輯器里寫卡住以后再看cpp而且不是從頭看到尾是先看readme.txt了解題目歸類再只看關(guān)鍵函數(shù)比如忘了并查集就只看find函數(shù)不碰main。一個(gè)更有效的操作是把你自己寫的半成品和答案放在左右兩欄逐行找差異。曾經(jīng)有一道模擬題我怎么都WA對(duì)照答案才發(fā)現(xiàn)自己月份天數(shù)表里二月寫了28天沒考慮閏年。這種差異靠肉眼盯著自己的代碼很難發(fā)現(xiàn)但一對(duì)比就出來了。看完答案以后把文件關(guān)掉重新獨(dú)立寫一遍直到能不參考任何東西提交AC。這套流程走完題目套路才真正留在腦子里而不是留在下載文件夾里。3. 核心代碼精讀三道題看透POJ基礎(chǔ)題的套路前面把資源全貌講清了這一章我挑三道有代表性的題目——1000、1088、1258——把代碼逐段拆開。這三題正好是三個(gè)階段輸入輸出基礎(chǔ)、遞歸搜索、圖論經(jīng)典算法?？炊@三段包里的其他題基本就是同一套思路換了個(gè)場(chǎng)景。3.1 POJ 1000EOF循環(huán)與格式化輸出#include cstdio int main() { int a, b; while (scanf(%d %d, a, b) ! EOF) { printf(%d\n, a b); } return 0; }這段是POJ 1000的經(jīng)典寫法。OJ判題時(shí)會(huì)把一個(gè)輸入文件喂給程序文件里可能有很多行a b但題目不會(huì)告訴你到底有幾組。scanf的返回值是成功讀到的變量個(gè)數(shù)讀不到任何數(shù)據(jù)時(shí)返回EOF。while條件里的! EOF讓程序持續(xù)讀到文件尾才退出這樣就能處理任意多組數(shù)據(jù)。參數(shù)說明scanf(%d %d, a, b)中第一個(gè)%d匹配a第二個(gè)匹配b中間的空白字符會(huì)自動(dòng)跳過輸入流里的空格、Tab 和換行。printf(%d\n, a b)則是在每次讀入后立即輸出結(jié)果并換行。有人習(xí)慣寫for(;;) { cin a b; if (cin.fail()) break; }功能一樣但scanf版本在POJ的G環(huán)境下更快當(dāng)題目輸入數(shù)據(jù)量比較大的時(shí)候IO快慢會(huì)對(duì)運(yùn)行時(shí)間產(chǎn)生肉眼可見的影響。這道題唯一的坑就是多組輸入。如果只寫scanf和printf而沒有while循環(huán)程序處理完第一行就退出OJ會(huì)認(rèn)為輸出不完整直接判WA。很多新手第一次提交POJ就是掛在這一點(diǎn)上。3.2 POJ 1088滑雪與記憶化搜索#include cstdio #include cstring #include algorithm using namespace std; const int MAXN 105; int map[MAXN][MAXN]; int dp[MAXN][MAXN]; int r, c; int dx[] {0, 0, -1, 1}; int dy[] {-1, 1, 0, 0}; int dfs(int x, int y) { if (dp[x][y] ! -1) return dp[x][y]; int longest 1; for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; if (nx 0 nx r ny 0 ny c map[nx][ny] map[x][y]) { longest max(longest, dfs(nx, ny) 1); } } return dp[x][y] longest; } int main() { scanf(%d %d, r, c); for (int i 0; i r; i) for (int j 0; j c; j) scanf(%d, map[i][j]); memset(dp, -1, sizeof(dp)); int ans 0; for (int i 0; i r; i) for (int j 0; j c; j) ans max(ans, dfs(i, j)); printf(%d\n, ans); return 0; }邏輯說明滑雪題要求找出一條最長的嚴(yán)格遞減路徑。dfs(x, y)返回從(x, y)出發(fā)能走的最長距離。dp[x][y]用來緩存已經(jīng)算過的位置避免重復(fù)遞歸這就是記憶化搜索。longest初始為1表示當(dāng)前點(diǎn)本身也算一步四個(gè)方向都試一遍只要下一個(gè)點(diǎn)高度嚴(yán)格低于當(dāng)前點(diǎn)就遞歸往下走。主函數(shù)里遍歷所有起點(diǎn)取最大值。參數(shù)說明dx和dy是方向數(shù)組按“左上右下”四個(gè)方向探測(cè)。map[nx][ny] map[x][y]是這道題的核心約束——只能往更低的地方滑不能相等否則路徑就出現(xiàn)循環(huán)。memset(dp, -1, sizeof(dp))把緩存初始化為 -1因?yàn)楹戏ǖ淖疃叹嚯x最小是1用 -1 表示“還沒算過”。這里有個(gè)新手經(jīng)常翻車的地方如果把寫成題目要求嚴(yán)格遞減所以相等高度不能走還有的寫法在遞歸里回溯修改標(biāo)記數(shù)組那是搜索的寫法不是記憶化搜索。兩種都能算對(duì)但搜索寫法在這個(gè)數(shù)據(jù)范圍下會(huì)重復(fù)計(jì)算大量子問題邊界一大就TLE。3.3 POJ 1258Kruskal最小生成樹與并查集#include cstdio #include vector #include algorithm using namespace std; struct Edge { int u, v, w; bool operator (const Edge o) const { return w o.w; } }; int fa[105]; int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } int main() { int n; while (scanf(%d, n) ! EOF) { vectorEdge edges; for (int i 0; i n; i) { for (int j 0; j n; j) { int w; scanf(%d, w); if (i j) edges.push_back({i, j, w}); } } sort(edges.begin(), edges.end()); for (int i 0; i n; i) fa[i] i; int ans 0, cnt 0; for (Edge e : edges) { int fu find(e.u); int fv find(e.v); if (fu ! fv) { fa[fu] fv; ans e.w; cnt; if (cnt n - 1) break; } } printf(%d\n, ans); } return 0; }邏輯說明1258給的是一個(gè)n行n列的鄰接矩陣問連接所有農(nóng)場(chǎng)的最小網(wǎng)線長度典型的最小生成樹問題。這里用Kruskal算法先把所有邊按權(quán)值排序再用并查集判斷兩個(gè)端點(diǎn)是否已經(jīng)在同一棵樹上不在就合并同時(shí)累加邊權(quán)。并查集的find函數(shù)寫成了帶路徑壓縮的遞歸形式每次查找會(huì)把鏈上所有節(jié)點(diǎn)直接掛到根節(jié)點(diǎn)下面后續(xù)查找接近O(1)。參數(shù)說明if (i j)是為了把鄰接矩陣去重成無向邊。因?yàn)榫仃囀菍?duì)稱的i j保證了只取上半三角一條邊只處理一次否則會(huì)重復(fù)加邊導(dǎo)致結(jié)果偏大。cnt n - 1是提前退出的條件一棵n節(jié)點(diǎn)的樹只需要n-1條邊收集夠了就沒必要繼續(xù)掃剩余邊。注意fa數(shù)組沒有初始化而是在每組測(cè)試數(shù)據(jù)開頭用循環(huán)重置這是多組輸入題目最容易漏的一步。這道題的價(jià)值在于Kruskal 并查集是圖論入門的必修組合。代碼量不大但一旦掌握后續(xù)的帶權(quán)并查集、最小生成樹變種都能從這個(gè)基礎(chǔ)版本擴(kuò)展出去。把這個(gè)版本理解透了再去看代碼包里其他圖論題會(huì)發(fā)現(xiàn)結(jié)構(gòu)都差不多。4. 本地跑通從源碼到親手看到輸出4.1 一條g命令完成編譯運(yùn)行代碼拿到手先要跑起來。在Linux或者M(jìn)ac終端上最直接的方式是g 1000.cpp -o 1000 ./1000-o 1000指定輸出的可執(zhí)行文件名不寫默認(rèn)是a.out。Windows下沒有g(shù)的話可以用MinGW或者Dev-C命令基本一致生成的是1000.exe。我一般會(huì)順手加一個(gè)編譯警告參數(shù)讓它更嚴(yán)格一些g -Wall 1000.cpp -o 1000加上-Wall后編譯器會(huì)把未使用變量、類型轉(zhuǎn)換不匹配這類問題也列出來。雖然警告不影響生成可執(zhí)行文件但很多時(shí)候那些不起眼的warning就是WA的根源。比如%d對(duì)應(yīng)了一個(gè)long long類型的變量GCC默認(rèn)情況下不一定報(bào)錯(cuò)可輸出就是錯(cuò)的。這類問題越早暴露越好。4.2 用題目樣例驗(yàn)證輸出結(jié)果POJ每道題都會(huì)在題目頁面給出一組輸入樣例和輸出樣例。不要直接手動(dòng)在終端里敲因?yàn)橐院髮懙降哪M題、圖論題輸入動(dòng)輒幾十行手敲既慢又容易出錯(cuò)。正確做法是把樣例保存成文件./1000 input.txt這個(gè)命令把input.txt作為標(biāo)準(zhǔn)輸入喂給程序終端里直接看到輸出。如果想和官方輸出逐字節(jié)比對(duì)用重定向加diff./1000 input.txt output.txt diff output.txt expected.txtdiff沒有任何輸出就代表兩個(gè)文件完全一致有輸出會(huì)把每一處差異標(biāo)出來。OJ判題的本質(zhì)就是這個(gè)流程編譯你的源碼用測(cè)試文件作為輸入然后把你的程序輸出和標(biāo)準(zhǔn)答案文件逐字節(jié)比較。所以diff過了樣例就一定過。4.3 自己造邊界數(shù)據(jù)樣例只是最低限度的驗(yàn)證提交前最好自己構(gòu)造幾組邊界數(shù)據(jù)。常見的幾個(gè)方向# 1258的邊界n1時(shí)沒有邊MST總長應(yīng)為0 1 0 # 1008的邊界跨年的日期轉(zhuǎn)換檢查年份進(jìn)位 # 1001的邊界結(jié)果為0.0時(shí)輸出0而不是0.0我一般會(huì)用Python寫個(gè)小腳本生成隨機(jī)數(shù)據(jù)再用暴力算法跑一個(gè)小數(shù)據(jù)量版本和參考答案程序?qū)ε摹＿@個(gè)習(xí)慣能提前攔截掉絕大多數(shù)WA原因。比如并查集忘記重置、數(shù)組開小、明知會(huì)溢出還用了int。邊界數(shù)據(jù)的價(jià)值比樣例高得多因?yàn)闃永穷}目作者給的綠燈而邊界數(shù)據(jù)是你自己設(shè)定的紅燈。5. 避坑指南POJ提交常見的四個(gè)問題5.1 本地編譯通過一提交就WA現(xiàn)象本地跑樣例、跑隨機(jī)數(shù)據(jù)全對(duì)提交到POJ返回Wrong Answer沒有任何其他提示。原因最常見的是數(shù)組長度小于題目給出的數(shù)據(jù)范圍其次是多組測(cè)試數(shù)據(jù)之間沒有完全重置全局狀態(tài)。比如上一組輸入的殘值被這一組讀到導(dǎo)致計(jì)算錯(cuò)亂。還有一種情況是scanf格式寫錯(cuò)輸入數(shù)據(jù)一多就讀偏了。解決每次寫完代碼先檢查數(shù)據(jù)范圍對(duì)應(yīng)的數(shù)組長度一律開到“上限5”。多組輸入的程序在main開頭把所有全局?jǐn)?shù)組和計(jì)數(shù)器重新初始化不要信任上一次循環(huán)留下的任何殘留值。另外scanf嚴(yán)格按格式串匹配輸入末尾多一個(gè)空格都可能讓后續(xù)讀取錯(cuò)位格式化字符串里少用多余字符。5.2 Presentation Error空格和換行的格式陷阱現(xiàn)象OJ返回Presentation Error看輸出內(nèi)容全對(duì)就是格式不對(duì)。原因多輸出了一個(gè)空格、行尾多了一個(gè)空格或者最后一行缺少換行。POJ對(duì)格式的挑剔程度超出預(yù)期PE已經(jīng)算半個(gè)AC但仍然是錯(cuò)誤。解決把所有輸出語句統(tǒng)一成%d\n這種緊湊寫法。題目要求兩個(gè)數(shù)字之間用空格分隔就嚴(yán)格只在兩個(gè)數(shù)字之間放一個(gè)空格行末不要加空格。我見過一個(gè)典型錯(cuò)誤是用for循環(huán)輸出數(shù)組每個(gè)數(shù)后面都跟了一個(gè)空格樣例恰好只有一個(gè)數(shù)所以過了數(shù)據(jù)一多就PE。正確做法是判斷不是最后一個(gè)元素才打印空格。5.3 Runtime Error數(shù)組越界與遞歸爆?，F(xiàn)象本地運(yùn)行正常提交后返回Runtime Error。少數(shù)情況下本地也能復(fù)現(xiàn)程序直接崩潰或者報(bào)Segmentation fault。原因數(shù)組下標(biāo)訪問越界或者遞歸層數(shù)太深。POJ基礎(chǔ)題的數(shù)據(jù)范圍雖然不大但有些題目遞歸深度和矩陣規(guī)模是綁定的比如1088著滑雪題極端情況下遞歸鏈可能很長。局部定義的大數(shù)組也可能在棧上溢出因?yàn)槟J(rèn)?？臻g有限。解決大數(shù)組一律定義成全局變量而不是main里的局部數(shù)組。全局變量在數(shù)據(jù)段分配空間大得多。遞歸型的DFS優(yōu)先考慮改成記憶化搜索已經(jīng)算過的狀態(tài)直接返回既降低遞歸深度又省時(shí)間。如果題目確實(shí)需要深遞歸用vector或顯式棧代替。5.4 語言選項(xiàng)選錯(cuò)導(dǎo)致CE現(xiàn)象本地用G編譯運(yùn)行都沒問題提交時(shí)選了C報(bào)Compile Error。原因POJ的G和C選項(xiàng)背后是不同的編譯器體系對(duì)個(gè)別語法支持不同。最典型的差異是__int64這種東西GNU系編譯器有自己的long long而某些C編譯器環(huán)境下直接寫__int64會(huì)編譯失敗。解決統(tǒng)一提交語言選G。如果你做題時(shí)用的是C代碼里就只寫long long避免用編譯器的私有擴(kuò)展。另一個(gè)常見CE原因是提交時(shí)把代碼復(fù)制漏了比如只復(fù)制了一部分、漏了頭文件或者漏了using namespace std;。提交前自己先編譯一遍再檢查復(fù)制的代碼首行是#include末行是return 0;}基本就能繞開這類低級(jí)錯(cuò)誤。6. 二次改造把答案包變成你自己的模板庫當(dāng)你照著答案把幾十道題跑通并理解后下一步不是繼續(xù)抄新題而是對(duì)這份資源做一次“二次開發(fā)”把里面的代碼精華提煉成自己的模板。我拿到答案包后的第一件事是建一個(gè)mytemplates/目錄把每一類題目的通用骨架抽出來。以POJ 1000為基礎(chǔ)我會(huì)把輸入輸出套路邊角料整理成一個(gè)通用模板#include cstdio #include cstring #include vector #include algorithm using namespace std; const int MAXN 105; void solve() { // 每道題的核心邏輯寫在這里 } int main() { int n; while (scanf(%d, n) ! EOF) { solve(); } return 0; }這個(gè)模板的好處是主邏輯和IO解耦調(diào)試時(shí)只需要盯著solve()內(nèi)部。換新題時(shí)把數(shù)據(jù)結(jié)構(gòu)定義和solve內(nèi)容替換掉就行。模板整理好以后我再按“模擬、搜索、DP、圖論”建四個(gè)子目錄把答案包里每一道題的代碼都塞進(jìn)去并加上自己的注釋。注釋只寫兩個(gè)東西這題用了什么算法以及我第一次提交的時(shí)候錯(cuò)在哪。比如在并查集模板里我會(huì)注明“每組數(shù)據(jù)必須重置fa”在輸出模板里注明“行末不要多余空格”。整理過程中有一個(gè)值得嘗試的技巧把答案代碼的變量名改成自己能理解的名字。原本可能是一個(gè)字母的d我改成dist或者depth。改名不是為了運(yùn)行而是為了讓三個(gè)月后的自己回看時(shí)不需要猜。做完這一步這份資源就變成了“我自己的題庫”每次刷完一組題我強(qiáng)制自己把提交過的代碼重新整理進(jìn)模板庫然后打開答案包刪掉已經(jīng)吃透的題目目錄。從那以后我每次刷題都會(huì)先跑一遍邊界數(shù)據(jù)再交再也不會(huì)出現(xiàn)本地全對(duì)一提交就WA的情況。希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取