ACM OJ基础题AC代码集：C++17模板与本地对拍实践

简介这份资料面向准备北京大学POJ在线评测、ACM算法入门与课程作业练习的学习者汇集百余道基础与常见题目的C参考实现可用于对照思路、排查边界条件并复盘输入输出处理。压缩包共157个文件其中156个cpp源码文件和1个txt说明文件整体约59KB体量轻便便于按题号查找和本地编译调试。相关题目覆盖枚举、模拟、数论、动态规划、搜索、字符串与基础数据结构等入门至进阶内容代码可作为算法实现范本也能帮助读者理解评测平台的常见输入格式与输出要求。目前已有2654人学习下载适合刚接触POJ、需要刷题参考或希望补齐基础算法短板的读者使用。1. 一份散装的 OJ 基础题 AC 代码集比题解文章更接近实战刷 ACM 风格的基础题真正卡人的往往不是思路而是那个怎么也过不去的边界多组输入忘了读到文件尾、答案明明对却败在行末多了一个空格、大数乘法用 int 一存就溢出。这份资源就是冲着这些场景来的——它不是一篇讲思路的题解文章而是一批已经 AC 过的 OJ 基础题答案代码按题号归档拿到手就能编译、能对样例、能直接提交。适合两类人刚接触在线评测、想找一份能对着跑的标准答案来核对自己代码的新手以及想把零散的基础题代码整理成个人模板库、以后比赛前能快速翻查的老手。下面按“它长什么样、怎么跑起来、怎么改”的顺序往下拆。2. 目录与技术栈题号即文件名一份能直接扔进 IDE 的工程结构2.1 目录树一道题一个文件夹题号就是索引这类答案包最容易踩的坑是“所有 cpp 堆在一个目录里”几十道题之后完全找不到东西。这份资源的结构是按题号分目录每题一个文件夹主程序统一叫main.cpp方便单独编译也方便以后往里加样例文件和暴力解。oj-basic-answers/ ├── 1001-add-a-b/ │ ├── main.cpp │ ├── sample.in │ └── sample.out ├── 1002-big-mul/ │ ├── main.cpp │ ├── sample.in │ └── sample.out ├── 1007-interval/ │ ├── main.cpp │ ├── sample.in │ └── sample.out ├── 1012-knapsack/ │ ├── main.cpp │ └── sample.in ├── 1018-grid-bfs/ │ ├── main.cpp │ └── sample.in └── README.md目录名用“题号 一句话题意”的写法是有意为之题号保证唯一题干关键词保证半年后你还认得出这是哪道题。sample.in/sample.out存的是题目页面上给的样例作用不是给你提交而是本地跑完拿来diff一下确认编译和输入输出都没有问题。提示如果题目本身有多组测试数据sample.in里要把多组数据整段贴进去包括那个看起来多余的结尾空行否则本地能过、线上挂了。2.2 每个源文件的公共骨架头文件与 IO 加速打开任意一个main.cpp前半段几乎长得一样。基础题不需要复杂工程结构一个文件从#include到main结束所有逻辑自包含。#include bits/stdc.h // 基础题图省事一次带全标准库 using namespace std; int main() { // 关同步 解绑cin/cout 在大量输入时性能能追平 scanf ios::sync_with_stdio(false); cin.tie(nullptr); int a, b; while (cin a b) { // 读到 EOF 自动退出天然支持多组输入 cout a b \n; // 用 \n 而不是 endl避免反复刷新缓冲区 } return 0; }这段骨架里有三个值得单独说的点。bits/stdc.h不是标准头文件是 GCC 提供的聚合头线上评测机只要用 g 编译就能过用 MSVC 或者某些严格环境的编译器会报错本地编译不过时先换成具体头文件试试。ios::sync_with_stdio(false)关掉 C 流和 C 流的同步cin.tie(nullptr)解除cin对cout的绑定这两行是 IO 密集题能不能过时间限制的分水岭常见做法是抄模板时顺手就带上。用\n不用endl因为endl每次都会强制刷缓冲区几十万行输出下来差距很明显。参数上没什么可调的唯一的开关是那两行同步设置如果你在同一个程序里混用了scanf和cin就绝对不能关同步否则读入顺序会乱。我的习惯是要么全用cin/cout要么全用scanf/printf不混着来。2.3 编译环境与标准选择答案包里的代码统一按 C17 写编译命令固定成下面这行写进脚本以后每题都跑一遍g -stdc17 -O2 -Wall -Wextra -o main main.cpp-stdc17对齐绝大多数在线评测机现在默认或可选的语言标准-O2打开二级优化很多时间限制紧的题在本地不加优化跑得慢加了才接近线上表现-Wall -Wextra把警告全打开像“变量未初始化”“有符号和无符号比较”这类警告往往直接对应线上的 WA 或 RE本地看到就别忽略。编译参数作用什么时候必须加-stdc17指定语言标准用到auto、结构化绑定、bits/stdc.h新特性时-O2二级优化模拟或提交前压时间本地调边界可先不加-Wall -Wextra打开全部常用警告每次编译都建议加早发现未初始化变量-g -fsanitizeaddress调试符号 内存检查出现 RE 时定位数组越界、空指针最后一行那个-fsanitizeaddress是排查 RE 的后悔药加上之后数组越界会直接打印出越界位置和调用栈。代价是程序变慢、占用内存变大所以只在本地调试时开提交前必须去掉这些调试参数不然线上要么超时要么编译不过。3. 核心代码拆解五类基础题的通用写法3.1 多组输入EOF 循环是最高频的失分点基础题里最典型的输入形态是“不知道有多少组读到文件结束”。C 风格和 C 风格两种写法都对但要选一种用到底。// C 风格scanf 的返回值是成功读入的变量个数读到文件尾返回 EOF(-1) int n; while (scanf(%d, n) 1) { printf(%d\n, n * 2); } // C 风格cin 在流状态失效时布尔值为 false写法更短 int m; while (cin m) { cout m * 2 \n; }逻辑上scanf(%d, n) 1的判据是“成功读到了 1 个整数”比! EOF更严谨——如果输入里混进了非数字字符scanf会返回 0 而不是 EOF用! EOF判断就会陷入死循环。while (cin m)则是利用流对象重载的bool转换读到 EOF 或格式错误都会退出。参数上要注意scanf必须传地址n漏了是新手最常见的崩溃来源而且编译器不一定报错。还有一种变体是“第一行给组数 T接下来 T 组”这种反而简单cin T; while (T--) { ... }就行别和 EOF 循环搞混。我见过把while (T--)写成while (--T)的第一组数据直接被吃掉。3.2 高精度运算把 int 存不下的数当字符串处理大数题是基础题里的分水岭思路不复杂但实现细节多。以最基础的大数加法为例核心是倒序存、逐位加、处理进位。#include bits/stdc.h using namespace std; string addBig(string a, string b) { // 反转后从低位开始对齐长度不同时短的那边补 0 reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); if (a.size() b.size()) swap(a, b); string res; int carry 0; for (size_t i 0; i a.size(); i) { int da a[i] - 0; int db (i b.size()) ? b[i] - 0 : 0; int sum da db carry; res.push_back(char(0 sum % 10)); // 当前位 carry sum / 10; // 进位留到下一位 } if (carry) res.push_back(1); // 最高位还有进位别丢 reverse(res.begin(), res.end()); return res; }逻辑分三步反转让字符串下标和数位权重对齐逐位相加时用i b.size()判断短的那个数是不是已经取完最后把残留的进位补成最高位。参数上最容易翻车的是最后那个if (carry)比如99 1循环走完还留一个进位漏掉这行结果就变成00。乘法是同样的套路内外两层循环模拟竖式res[i j]累加最后统一从低位处理进位string mulBig(string a, string b) { if (a 0 || b 0) return 0; vectorint res(a.size() b.size(), 0); for (int i a.size() - 1; i 0; i--) for (int j b.size() - 1; j 0; j--) { int mul (a[i] - 0) * (b[j] - 0); int p1 i j, p2 i j 1; // 乘积落在两个位置 int sum mul res[p2]; res[p2] sum % 10; res[p1] sum / 10; } // 跳过前导零 string s; for (int v : res) if (!(s.empty() v 0)) s.push_back(char(0 v)); return s.empty() ? 0 : s; }p1 / p2这个下标分配是乘法实现的核心i j 1是当前乘积的个位落点i j承接进位。用vectorint而不是string存中间结果是因为中间某一位可能超过 9先存成整数最后统一进位比边算边处理进位清晰得多。3.3 贪心与排序区间调度为什么按右端点排区间调度是贪心入门题的标准形态给一堆区间选出最多互不重叠的。答案是按右端点升序能选就选。struct Interval { int l, r; }; int maxNonOverlap(vectorInterval v) { sort(v.begin(), v.end(), [](const Interval a, const Interval b) { return a.r b.r; // 关键按右端点排序不是左端点 }); int cnt 0, lastEnd INT_MIN; for (auto it : v) { if (it.l lastEnd) { // 与前一个选中区间不重叠 cnt; lastEnd it.r; } } return cnt; }逻辑上按右端点排序保证了每次选择都让“已占用空间的结束点尽量靠左”给后面留出最大余量这是贪心正确性的直接来源。如果按左端点排遇到一个从很早就开始、跨度极长的区间会白白占掉名额。参数上要注意it.l lastEnd里的等号题目说“端点可以相接”就带等号说“不能接触”就去掉等号这一处等号错了就是 WA on test 2 这种很难受的挂法。3.4 一维滚动数组的 0-1 背包0-1 背包的二维写法直观但基础题的容量往往开得大必须压成一维。int knapsack(int W, vectorint w, vectorint v) { vectorint dp(W 1, 0); for (size_t i 0; i w.size(); i) { // 关键容量必须从大到小遍历保证每件物品只用一次 for (int j W; j w[i]; j--) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } } return dp[W]; }倒序遍历是这段代码的全部精髓。正序遍历时dp[j - w[i]]可能刚被本轮更新过等于同一件物品被拿了两次那就变成完全背包了。dp数组大小开W 1是为了下标能直接对应容量dp[0] 0是初始状态其余默认 0 在“求最大价值、可以不装满”的场景下是正确的如果题目要求“恰好装满”初始值就要设成负无穷只在dp[0]处设 0。3.5 网格 BFS 最短路方向数组与访问标记网格类搜索题的模板高度固定写熟了几乎可以盲打。int bfs(vectorvectorint grid, int sr, int sc, int er, int ec) { int n grid.size(), m grid[0].size(); const int dir[4][2] {{1,0},{-1,0},{0,1},{0,-1}}; vectorvectorint dist(n, vectorint(m, -1)); // -1 表示未访问 queuepairint,int q; dist[sr][sc] 0; q.push({sr, sc}); while (!q.empty()) { auto [x, y] q.front(); q.pop(); if (x er y ec) return dist[x][y]; // 第一次到达即最短 for (auto d : dir) { int nx x d[0], ny y d[1]; if (nx 0 || nx n || ny 0 || ny m) continue; // 越界 if (grid[nx][ny] 1) continue; // 障碍 if (dist[nx][ny] ! -1) continue; // 已访问 dist[nx][ny] dist[x][y] 1; q.push({nx, ny}); } } return -1; // 不可达 }用dist数组同时承担“访问标记”和“距离记录”两个职责比单开一个visited数组省事也避免了两处状态不同步。方向数组定义成const int dir[4][2]放在栈上编译器能完全展开如果题目是八方向就连通改成dir[8][2]补上四个对角即可。越界判断要写在访问判断之前顺序反了虽然结果不错但多了一次越界下标访问在开了地址检查的环境里会直接报错。4. 本地跑通编译、样例比对与对拍验证4.1 单题编译与样例比对进入某一题的目录编译、喂样例、比对输出三步就能确认代码是否可用cd 1002-big-mul g -stdc17 -O2 -Wall -o main main.cpp ./main sample.in my.out diff -w my.out sample.out echo 样例通过把样例文件喂给标准输入把输出重定向到文件diff -w里的-w表示忽略所有空白字符差异这一条很重要很多题目样例输出里有行末空格手抄进sample.out时对不齐不加-w会一直报差异。保证只有diff返回成功才打印提示。如果diff输出了具体差异行先别改代码回头看一眼输出的换行数量——多一行或少一行空行是最常见的格式问题。4.2 批量编译脚本几十道题一次过一遍题目多了以后一道一道手编不现实写个脚本扫一遍重点是区分编译错误和样例不通过。#!/usr/bin/env bash # 放在答案包根目录一次性编译并测试所有题目 set -u fail0 for dir in */ ; do [ -f $dir/main.cpp ] || continue echo $dir if ! g -stdc17 -O2 -Wall -o $dir/main $dir/main.cpp 2 $dir/build.log; then echo 编译失败详情见 $dir/build.log fail$((fail1)); continue fi if [ -f $dir/sample.in ] [ -f $dir/sample.out ]; then $dir/main $dir/sample.in $dir/my.out if diff -wq $dir/my.out $dir/sample.out /dev/null; then echo 样例通过 else echo 样例不匹配; fail$((fail1)) fi fi done echo 失败数$fail脚本里有几个细节值得说。set -u让未定义变量直接报错退出避免路径拼接出空串后误删文件编译错误重定向到各题目录下的build.log一次跑完能拿到全部错误而不是第一个就中断diff -wq的-q只关心“是否不同”输出更干净。参数上如果你习惯用printf把-w换成-b忽略空格数量变化也行具体看题目对空格的容忍度。4.3 对拍用暴力解验证正解样例过了不代表对尤其是贪心、DP 这类“样例太弱”的题。对拍是血泪经验里最值钱的一招写一个必然正确但很慢的暴力解随机生成小数据两边的输出比对。# 对拍脚本随机造小数据对比正解 brute 两份输出 import random, subprocess, sys for case in range(500): n random.randint(1, 8) # 数据规模必须小暴力才跑得动 arr [random.randint(-20, 20) for _ in range(n)] data f{n}\n .join(map(str, arr)) \n out1 subprocess.run([./main], inputdata, capture_outputTrue, textTrue).stdout out2 subprocess.run([./brute], inputdata, capture_outputTrue, textTrue).stdout if out1.split() ! out2.split(): # 按 token 比对忽略空白差异 print(f第 {case} 组不一致\n输入{data}\n正解{out1}\n暴力{out2}) sys.exit(1) print(500 组全部一致)random.randint的范围要故意包含负数、零、边界值很多 bug 只在负数或者全相等的数据上暴露。out1.split() ! out2.split()是把输出按空白切成 token 再比比逐字符比对宽松避免格式细节干扰真正的逻辑错误。跑够 500 组还没差异这道题基本可以放心交了。5. 避坑与排查WA、TLE、RE 的五条高频现场现象本地样例全过提交 WA on test 1。原因八成是多组输入没读全只处理了第一组就退出。题目描述里“多组数据”“输入包含若干组”这种措辞容易被忽略。解决是把cin n外面套一层while (cin n)并且把每组之间的空行、初始化清空检查一遍全局数组记得每组开始前memset。现象本地瞬间出结果提交 TLE。常见原因有三个cin没关同步、循环里用了endl、以及把O(n²)的暴力当正解交上去了。前两个按 2.2 的骨架改掉第三个老实换算法。还有一种隐蔽情况是函数传参传了vector的拷贝而不是const几万次调用下来开销惊人。解决顺序是先关同步再查算法复杂度最后才怀疑评测机。现象运行直接 RE没有任何输出。数组开小了是头号嫌疑题目说n ≤ 10000你开了int a[1000]其次是递归层数过深爆栈网格 DFS 在 1000×1000 上递归必炸。解决是给数组多留 5 到 10 个余量下标从 1 开始用的话大规模搜索改成 BFS 或者手写栈。本地复现时加-fsanitizeaddress越界位置会直接打出来。现象输出看着一模一样但还是 WA。格式问题。有的题要求“每组数据后输出一个空行”有的命令“最后一个数字后不能有空格”还有的用printf(%d , x)循环完多打了一个空格。解决是严格控制分隔符的位置常见写法是第一个元素单独输出后续元素用printf( %d, x)这样行末不会残留空格。现象大数题答案前几位对、后面全错。整数溢出。int最大约 21 亿两个 10 万相乘直接爆long long在累加求和、阶乘题里同样会爆。解决是估算量级后换long long再往上就得上 3.2 的高精度字符串。另外负数取模在 C 里结果符号跟被除数走题目要求非负余数时需要手动(a % m m) % m。6. 二次开发把这些散文件改造成自己的模板库答案包直接当模板用用久了会散找一道“高精度乘法”要翻半天目录。我一般做三件事把它变成能长期复用的东西。第一件是按知识点重构目录而不是按题号。建立math/、dp/、graph/、greedy/、string/五个一级目录原来的题号目录整体挪进去同时在根目录维护一份INDEX.md每条记录写成“知识点 → 文件路径 → 原题号 → 复杂度”。这张表不写长一行一条半年后翻起来比任何注释都快。改完之后原来的题号信息没丢查旧题和新题两条路都通。第二件是把 4.2 的批量脚本升级成带索引生成的版本。脚本除了编译测试还顺手扫每个main.cpp的第一行注释把“知识点标签”抓出来追加到INDEX.md。约定每个文件第一行写// tag: dp,knapsack这样新增题目时只要写这一行索引自动更新不需要手动维护表格。这条约定比任何文档规范都管用因为它把“维护”这件事的成本降到了写一行注释。第三件是给模板加可复用性。答案代码是为了 AC 写的函数都嵌在main里想直接调用得复制粘贴。我的做法是把 3.2 到 3.5 那几个函数抽到tpl/bigint.hpp、tpl/graph.hpp里做成头文件主程序只#include再调用。抽的时候把using namespace std从全局挪进函数内部或者干脆用std::前缀否则一旦和别人的代码混编就是命名冲突。抽完拿 4.3 的对拍脚本回归一遍确认重构没改行为。再补一个容易忽略的点给每道题记录“失败过的原因”。我会在文件末尾写一行// WA: 多组输入没读EOF / TLE: 用endl这行注释比代码本身更有价值下次遇到同类题第一眼就能看到当初在哪翻车。从那以后我每次整理这类答案包都强制走一遍“编译脚本 对拍 索引更新”的完整流程一步不省。散文件谁都会存能一键验证、一眼查到知识点的才叫自己的库。希望帮到你。本文还有配套的精品资源点击获取