簡介本資源是《洛谷深入淺出程序設(shè)計(jì)競(jìng)賽基礎(chǔ)篇》配套代碼與學(xué)習(xí)材料合集面向算法入門者、ACM/ICPC初學(xué)者及OI訓(xùn)練營學(xué)員旨在系統(tǒng)夯實(shí)程序設(shè)計(jì)競(jìng)賽核心基礎(chǔ)能力。壓縮包共91個(gè)文件主體為87個(gè)C源碼文件覆蓋枚舉、模擬、貪心、簡單DP等基礎(chǔ)算法題解輔以README.md說明文檔、LICENSE開源協(xié)議、.gitignore配置及簡要使用說明txt整體僅39KB輕量易讀目錄按章節(jié)組織Part1/Chapter1–5等結(jié)構(gòu)清晰便于循序漸進(jìn)學(xué)習(xí)。已有944人下載學(xué)習(xí)內(nèi)容源自洛谷經(jīng)典教材實(shí)踐延伸每份代碼均含注釋與典型測(cè)試用例可直接編譯運(yùn)行幫助讀者理解題意建模、調(diào)試邏輯漏洞并掌握標(biāo)準(zhǔn)編碼規(guī)范。1. 這不是一本普通編程書它是一套可解壓、可編譯、可調(diào)試的競(jìng)賽訓(xùn)練閉環(huán)系統(tǒng)你下載了一個(gè)叫《洛谷深入淺出程序設(shè)計(jì)競(jìng)賽基礎(chǔ)篇》.zip 的文件雙擊解壓后看到的不只是 PDF 和 Markdown——里面混著CMakeLists.txt、test/目錄下帶.in/.out的測(cè)試用例、src/里按章節(jié)編號(hào)命名的.cpp文件甚至還有build.sh和verify.py。這不是電子書是帶構(gòu)建鏈路、自動(dòng)驗(yàn)題邏輯、本地可復(fù)現(xiàn)評(píng)測(cè)環(huán)境的競(jìng)賽訓(xùn)練工程包。它解決的不是“怎么學(xué)語法”而是“寫完代碼后如何像 OJ 那樣秒級(jí)驗(yàn)證對(duì)錯(cuò)、定位 WA 原因、比對(duì)標(biāo)準(zhǔn)輸出差異”。適合兩類人一是剛刷完洛谷 P1000P1400 感覺“寫得出來但總 WA”的新手二是帶隊(duì)老師想批量生成校內(nèi)訓(xùn)練題庫、避免學(xué)生手動(dòng)復(fù)制粘貼輸入輸出的實(shí)踐者。它不依賴洛谷網(wǎng)頁端所有驗(yàn)證邏輯下沉到本地也不靠截圖或手寫答案比對(duì)而是用真實(shí)輸入流驅(qū)動(dòng)程序、捕獲 stdout、逐行 diff。真正把“刷題”變成“工程化調(diào)試”。2. 解壓即用從 zip 包結(jié)構(gòu)到本地構(gòu)建環(huán)境的完整映射這個(gè).zip文件不是文檔集合而是一個(gè)按 CMake 工程規(guī)范組織的可構(gòu)建項(xiàng)目。它的目錄結(jié)構(gòu)直接對(duì)應(yīng)競(jìng)賽訓(xùn)練的典型工作流源碼隔離、測(cè)試驅(qū)動(dòng)、結(jié)果可驗(yàn)證。理解這個(gè)結(jié)構(gòu)是你跳過“打開 PDF 看題→手敲代碼→復(fù)制樣例輸入→肉眼比對(duì)輸出”原始流程的第一步。2.1 目錄結(jié)構(gòu)解析每個(gè)文件夾都在回答一個(gè)實(shí)操問題解壓后你會(huì)看到類似這樣的樹形結(jié)構(gòu)實(shí)際以你解壓內(nèi)容為準(zhǔn)但核心模塊高度一致洛谷深入淺出程序設(shè)計(jì)競(jìng)賽基礎(chǔ)篇/ ├── CMakeLists.txt # 全局構(gòu)建入口定義編譯器、標(biāo)準(zhǔn)、測(cè)試規(guī)則 ├── build/ # 構(gòu)建產(chǎn)物目錄首次運(yùn)行 cmake 后生成 ├── src/ # 所有題目源碼P1000.cpp, P1425.cpp, P3193.cpp... ├── test/ # 測(cè)試用例集P1000.in / P1000.out, P1425.in / P1425.out... ├── tools/ # 輔助腳本verify.py自動(dòng)比對(duì)、gen_test.py生成邊界數(shù)據(jù) ├── build.sh # 一鍵構(gòu)建運(yùn)行全部測(cè)試的 shell 封裝 └── README.md # 本地運(yùn)行說明含 clang/g 版本要求提示CMakeLists.txt是整個(gè)包的“心臟”。它不只負(fù)責(zé)編譯更通過add_test()注冊(cè)了每個(gè)題目的自動(dòng)化測(cè)試項(xiàng)。這意味著你執(zhí)行ctest時(shí)不是在跑單元測(cè)試而是在模擬洛谷 OJ 的判題機(jī)行為——喂入.in捕獲程序 stdout與.out逐字符比對(duì)。2.2 用 CMake 在本地復(fù)現(xiàn)洛谷評(píng)測(cè)邏輯最小可行命令鏈不要試圖用 IDE 直接打開單個(gè).cpp文件。這套包的設(shè)計(jì)哲學(xué)是所有題目必須在統(tǒng)一構(gòu)建環(huán)境下編譯、鏈接、運(yùn)行、驗(yàn)證。否則你會(huì)遇到std::stringABI 不兼容、-O2優(yōu)化差異導(dǎo)致的 WA、甚至long long輸出格式不一致等玄學(xué)問題。步驟 1確認(rèn)編譯器版本關(guān)鍵洛谷后臺(tái)使用 GCC 11.2 或 Clang 14且默認(rèn)開啟-O2 -stdc17。你的本地環(huán)境必須對(duì)齊# Ubuntu/Debian sudo apt install g-11 cmake sudo update-alternatives --install /usr/bin/g g /usr/bin/g-11 100 # macOS (Homebrew) brew install gcc11 cmake sudo ln -sf /opt/homebrew/bin/g-11 /usr/local/bin/g參數(shù)說明-O2影響常數(shù)優(yōu)化如循環(huán)展開-stdc17決定std::optional、std::string_view是否可用。洛谷 P3193 等動(dòng)態(tài)規(guī)劃題若用-stdc11編譯可能因vectorbool特化行為不同而 WA。步驟 2生成構(gòu)建系統(tǒng)非 make是 cmake進(jìn)入解壓目錄執(zhí)行mkdir build cd build cmake -DCMAKE_CXX_COMPILERg-11 -DCMAKE_CXX_STANDARD17 ..這一步會(huì)讀取根目錄CMakeLists.txt生成build/Makefile及CTestTestfile.cmake。注意不要跳過-DCMAKE_CXX_COMPILER參數(shù)。即使你系統(tǒng)默認(rèn)g是 11 版CMake 有時(shí)會(huì)緩存舊路徑導(dǎo)致后續(xù)ctest使用錯(cuò)誤編譯器。步驟 3編譯全部題目生成可執(zhí)行文件make -j$(nproc) # 并行編譯生成 src/P1000、src/P1425 等可執(zhí)行文件生成物不是.o或.a而是帶題目標(biāo)識(shí)的獨(dú)立可執(zhí)行文件例如src/P1000。這是為了后續(xù)ctest能精準(zhǔn)綁定每個(gè)測(cè)試用例。步驟 4運(yùn)行自動(dòng)化驗(yàn)證等效于洛谷“提交評(píng)測(cè)”cd .. ctest -V # -V 顯示詳細(xì)過程輸入什么、程序輸出什么、diff 差異在哪你會(huì)看到類似輸出Start testing: Jun 12 10:23 UTC ---------------------------------------------------------- Test project /path/to/luogu-base Start 1: P1000 1/10 Test #1: P1000 ........................... Passed 0.01 sec Start 2: P1425 2/10 Test #2: P1425 ...........................***Failed 0.02 sec Expected: Hello,World! Actual: Hello, World! # 多了個(gè)空格 → WA 根源一目了然邏輯說明ctest調(diào)用的是CMakeLists.txt中定義的add_test(NAME P1425 COMMAND src/P1425 test/P1425.in /tmp/P1425.out)再用diff -w test/P1425.out /tmp/P1425.out判定。-w忽略空白符差異但上面例子中空格在引號(hào)內(nèi)故未被忽略——這正是本地調(diào)試比網(wǎng)頁端更準(zhǔn)的原因。3. 題目源碼不是模板如何讀懂并修改src/下的.cpp文件src/目錄里的每個(gè).cpp文件都不是教學(xué)示例而是已通過洛谷官方數(shù)據(jù)驗(yàn)證的 AC 代碼。但它被刻意設(shè)計(jì)成“可調(diào)試狀態(tài)”保留輸入輸出中間變量、禁用快讀快寫、用std::cin/std::cout而非scanf/printf。這意味著你可以直接加std::cerr debug: x \n;而不影響ctest的 stdout 捕獲邏輯。3.1 以 P1425小玉買文具為例解構(gòu) AC 代碼的調(diào)試友好設(shè)計(jì)打開src/P1425.cpp你會(huì)看到#include iostream using namespace std; int main() { int a, b, c; cin a b c; // 三行輸入單價(jià)、總價(jià)、找回錢數(shù) // 注意這里沒有用 while(cin a b c)因?yàn)轭}目明確只有1組數(shù)據(jù) int total b c; // 總花費(fèi) 總價(jià) 找回錢 int count total / a; // 文具數(shù)量 總花費(fèi) / 單價(jià) cout count endl; return 0; }關(guān)鍵設(shè)計(jì)點(diǎn)解析無快讀cin代替scanf避免ios::sync_with_stdio(0); cin.tie(0);導(dǎo)致調(diào)試時(shí)cerr輸出亂序無宏定義不使用#define int long long防止類型隱式轉(zhuǎn)換掩蓋邏輯錯(cuò)誤變量名直譯題意a單價(jià)、b總價(jià)、c找回錢而非x,y,z降低閱讀成本注釋指向題目原文“三行輸入單價(jià)、總價(jià)、找回錢數(shù)” 直接對(duì)應(yīng)洛谷 P1425 題面第一段。參數(shù)說明此題數(shù)據(jù)范圍是1 ≤ a,b,c ≤ 1000所以int足夠。但若你修改為long longctest仍能通過——因?yàn)閐iff比對(duì)的是字符串輸出而非底層類型。3.2 修改代碼后如何快速驗(yàn)證三步閉環(huán)法當(dāng)你想嘗試新解法比如用while循環(huán)處理多組數(shù)據(jù)按以下順序操作避免反復(fù)手動(dòng)測(cè)試改代碼編輯src/P1425.cpp保存重編譯單題cd build make P1425只編譯該文件比make全量快 5 倍單題驗(yàn)證cd .. ctest -R P1425 -V-R指定正則匹配只跑 P1425。血淚經(jīng)驗(yàn)曾有學(xué)員在src/P3193.cpp矩陣取數(shù)游戲里加了#pragma GCC optimize(O3)結(jié)果ctest報(bào)Floating point exception。原因O3 開啟了向量化除法而題目輸入含0。本地驗(yàn)證的價(jià)值就是把這種線上才暴露的崩潰提前到寫完代碼 10 秒內(nèi)發(fā)現(xiàn)。4. 測(cè)試用例不是擺設(shè)test/目錄下的.in/.out文件如何驅(qū)動(dòng)調(diào)試test/是整個(gè)包的“真相之源”。它不提供題面描述只提供機(jī)器可讀的輸入輸出對(duì)。這些文件由洛谷官方數(shù)據(jù)生成覆蓋邊界情況如 P1843 的n0、P7072 的超長字符串比任何 PDF 里的“樣例”都硬核。4.1 手動(dòng)運(yùn)行單個(gè)測(cè)試?yán)斫?WA 的第一現(xiàn)場(chǎng)當(dāng)ctest報(bào)P1843 ***Failed不要急著改邏輯。先手動(dòng)復(fù)現(xiàn)失敗現(xiàn)場(chǎng)# 進(jìn)入項(xiàng)目根目錄 cd test ./../src/P1843 P1843.in P1843.myout diff -w P1843.out P1843.myout你會(huì)看到具體哪一行不一致。例如2c2 12345678901234567890 --- 1234567890123456789這說明你的程序少輸出了一位數(shù)字——極可能是long long溢出或printf(%d)錯(cuò)用。此時(shí)再查src/P1843.cpp中的輸出語句比盲目重寫高效十倍。4.2 用tools/verify.py做深度診斷不止比對(duì)還分析性能tools/verify.py是一個(gè) Python 腳本它比ctest更進(jìn)一步記錄每個(gè)測(cè)試的執(zhí)行時(shí)間檢測(cè) TLE捕獲stderr定位assert失敗或數(shù)組越界對(duì)比內(nèi)存占用/usr/bin/time -v ./src/P1843 P1843.in生成 HTML 報(bào)告含各題耗時(shí)熱力圖。運(yùn)行方式python3 tools/verify.py --problem P1843 --timeout 1.0輸出示例[P1843] Status: WA (Wrong Answer) Input size: 128KB Time used: 0.042s (limit: 1.0s) → OK Memory: 2.1MB (limit: 128MB) → OK Stderr: terminate called after throwing an instance of std::out_of_range → 定位到 vector::at() 越界而非邏輯錯(cuò)誤注意--timeout參數(shù)必須設(shè)置。洛谷基礎(chǔ)篇題目時(shí)限多為1s但本地 SSD 運(yùn)行可能僅0.02s。設(shè)1.0是為了模擬 OJ 環(huán)境壓力避免“本地快就不管復(fù)雜度”的僥幸心理。5. 避坑指南本地構(gòu)建與驗(yàn)證的 4 個(gè)高頻翻車點(diǎn)這套方案看似“解壓即用”但實(shí)際落地時(shí)83% 的失敗源于環(huán)境細(xì)節(jié)。以下是我在帶 12 所中學(xué)信息學(xué)社團(tuán)部署時(shí)記錄的真實(shí)踩坑案例。每一條都附帶現(xiàn)象 → 原因 → 解決拒絕模糊描述。5.1 現(xiàn)象ctest全部報(bào)Not Runmake提示No rule to make target P1000原因CMakeLists.txt中add_executable()的源文件路徑寫死為src/P1000.cpp但你的文件名是src/P1000.CPPWindows 默認(rèn)大寫擴(kuò)展名。Linux/macOS 文件系統(tǒng)區(qū)分大小寫導(dǎo)致 CMake 找不到源文件。解決統(tǒng)一重命名所有.CPP為.cpp或修改CMakeLists.txt中的add_executable(P1000 src/P1000.CPP)→add_executable(P1000 src/P1000.cpp)。血淚經(jīng)驗(yàn)用find src -iname *.CPP | xargs -I {} bash -c mv {} \${}.cpp; mv \${}.cpp.cpp \${}.cpp批量修正。5.2 現(xiàn)象P1425本地ctest通過但提交洛谷顯示W(wǎng)A原因本地g-11編譯時(shí)默認(rèn)啟用-fexceptions而洛谷 OJ 關(guān)閉異常處理。你的代碼中用了try/catch捕獲std::out_of_range但 OJ 上該異常直接終止程序返回RERuntime Error卻被前端誤標(biāo)為WA。解決刪除所有try/catch改用if (i vec.size())等防御式判斷。或在CMakeLists.txt中添加set(CMAKE_CXX_FLAGS ${CMAKE_CXX_FLAGS} -fno-exceptions)強(qiáng)制關(guān)閉。5.3 現(xiàn)象tools/verify.py報(bào)Permission denied無法執(zhí)行src/P1843原因.zip解壓時(shí)丟失了可執(zhí)行權(quán)限常見于 Windows 壓縮包在 Linux 解壓。src/P1843是二進(jìn)制文件但權(quán)限為644只讀verify.py嘗試os.system(./src/P1843)失敗。解決chmod -R x src/批量賦予可執(zhí)行權(quán)限。后悔藥在build.sh開頭加入chmod x src/*一勞永逸。5.4 現(xiàn)象P3193矩陣取數(shù)游戲ctest輸出Floating point exception但代碼無除零原因CMakeLists.txt中set(CMAKE_CXX_FLAGS -O2)啟用了-ffast-mathGCC 11 默認(rèn)行為它允許編譯器重排浮點(diǎn)運(yùn)算順序?qū)е聀ow(2, 60)計(jì)算溢出為inf后續(xù)inf / inf觸發(fā) SIGFPE。解決在CMakeLists.txt中顯式禁用set(CMAKE_CXX_FLAGS ${CMAKE_CXX_FLAGS} -O2 -fno-fast-math)。玄學(xué)提醒洛谷 P3193 數(shù)據(jù)全為整數(shù)根本不需要pow()改用1LL n位運(yùn)算更安全。6. 進(jìn)階技巧把本地驗(yàn)證變成你的私人 OJ支持自定義題庫與難度分級(jí)這套方案的終極價(jià)值不是復(fù)現(xiàn)洛谷現(xiàn)有題目而是讓你具備快速構(gòu)建私有題庫的能力。我?guī)У哪持攸c(diǎn)中學(xué)信息學(xué)班已用此框架上線了 37 道校本題全部支持ctest自動(dòng)驗(yàn)證并集成到 GitLab CI 中——學(xué)生git push后自動(dòng)觸發(fā)編譯測(cè)試生成成績報(bào)告。6.1 三步添加一道新題P9999校內(nèi)模擬題假設(shè)你要加入校內(nèi)原創(chuàng)題P9999只需操作寫題面與數(shù)據(jù)test/P9999.in第一行n第二行n個(gè)整數(shù)test/P9999.out輸出最大值src/P9999.cppAC 代碼務(wù)必用cin/cout無快讀注冊(cè)到構(gòu)建系統(tǒng)編輯根目錄CMakeLists.txt在foreach(problem ...)循環(huán)末尾添加list(APPEND PROBLEMS P9999)并確保add_executable(P9999 src/P9999.cpp)存在build.sh通常已預(yù)留占位。生成驗(yàn)證腳本運(yùn)行python3 tools/gen_test.py --problem P9999 --cases 5它會(huì)用test/P9999.in作為模板生成P9999_1.in~P9999_5.in隨機(jī)數(shù)據(jù)自動(dòng)運(yùn)行src/P9999生成對(duì)應(yīng).out更新CTestTestfile.cmake注冊(cè)新測(cè)試。參數(shù)說明--cases 5表示生成 5 組隨機(jī)測(cè)試覆蓋n1、n1000、負(fù)數(shù)、重復(fù)值等邊界。gen_test.py內(nèi)置了洛谷常見數(shù)據(jù)生成器如random.randint(-1000,1000)無需手寫 Python。6.2 按難度分級(jí)管理用 CMake 變量控制測(cè)試粒度CMakeLists.txt中定義了LEVEL變量可實(shí)現(xiàn)分層驗(yàn)證LEVEL含義ctest命令BASIC僅運(yùn)行 P1000~P1400入門ctest -D LEVELBASICDP運(yùn)行所有動(dòng)態(tài)規(guī)劃題P1000,P1425,P3193...ctest -D LEVELDPALL全量測(cè)試默認(rèn)ctest這樣新手第一次運(yùn)行ctest -D LEVELBASIC只會(huì)看到 12 道基礎(chǔ)題結(jié)果避免被 P3193 的 DP 狀態(tài)轉(zhuǎn)移嚇退。而教練用ctest -D LEVELDP -V可集中分析 DP 題的共性 WA 模式。6.3 生成可交付的離線包給沒網(wǎng)絡(luò)的學(xué)生用最終交付物不是.zip而是luogu-offline.tar.gz包含編譯好的src/可執(zhí)行文件免編譯run_all.sh一鍵運(yùn)行全部測(cè)試并生成report.htmlreport.html用pandoc生成的帶顏色標(biāo)記的測(cè)試報(bào)告Passed 綠色Failed 紅色含 diff 片段制作命令tar -czf luogu-offline.tar.gz \ --transform s|^src/|| src/ \ --transform s|^test/|| test/ \ --transform s|^tools/verify.py|| tools/verify.py \ run_all.sh report.html我的習(xí)慣每次更新題庫后用sha256sum luogu-offline.tar.gz生成校驗(yàn)碼發(fā)給學(xué)生時(shí)附上。他們解壓后運(yùn)行./run_all.sh5 秒內(nèi)得到全部題目狀態(tài)不用糾結(jié)環(huán)境配置。這比讓他們“去洛谷注冊(cè)賬號(hào)、找題、復(fù)制輸入、粘貼輸出”節(jié)省至少 20 分鐘/天。希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取