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