简介面向北京大学在线评测系统POJ入门练习者的 C 答案合集覆盖一百余道基础题目适合 ACM 初学者对照调试、理解常见算法套路。资源包内含 157 个文件其中 156 个为 cpp 源代码另有 1 个 txt 说明文档压缩后仅 59KB体量小巧可按题号直接检索。收录范围涵盖 10001008、10111014、1016、1017 等经典题号涉及枚举、模拟、递推、动态规划、数论与字符串处理等常见基础题型每组代码均可独立运行便于对照输入输出样例验证解法。目前已有 2653 人浏览学习该资料。对正在刷题备赛或刚接触 POJ 的读者这些代码既能帮助快速定位思路偏差也可作为基础算法模板参考有效减少重复调试的时间成本题目由易到难、题号清晰适合课后自测与赛前集中复习亦可作为课堂练习的配套参考。1. 先看结论POJ基础题答案值得拆的不是代码而是输入输出习惯先说结论这份POJ基础题答案真正值得读的不是那些“AC代码”本身而是代码里藏着的一套输入输出习惯。我拿到资源后从头翻了十几个文件发现最见功夫的不是算法——排序、搜索、动态规划这些模板谁都会背——而是怎么处理EOF、怎么防止输出格式出错、怎么在数据规模未知时保住性能。这些东西正是ACM入门阶段最容易自己翻车的地方。如果你正在刷POJ的入门题或者准备参加ACM训练这份基础题答案适合拿来当“对照模板”而不是“抄作业素材”。新手照着代码看一遍能少踩一半坑熟手则可以把它当作整理自己模板库的起点。下面我按从阅读到运行的顺序把这份资源拆开讲清楚。2. 项目定位与技术选型一份答案里真正值钱的是I/O习惯打开解压目录第一眼看到的就是“一题一个文件夹”或“一题一个独立cpp”的排布方式。命名直接对应POJ题号像T1000、T1001、T1003这种配套说明有的写了思路有的只留一句“与某某题类似”。质量不算统一但这不影响使用老牌OJ的提交方式就是“把整个文件复制进页面”单文件不需要构建脚本拿来就能编这也是这类题解资源最方便的地方。2.1 资源结构题号、算法类型与独立编译单元POJ基础题的覆盖范围其实很固定数学题AB、高精度、进制转换、字符串题加密、排序、查找、搜索题棋盘、迷宫、八皇后、动态规划题数字三角形、最长公共子序列。对应到这份资源里文件形态大致如下表题型分组典型题目类型文件形式数学基础多组AB、高精度乘法、进制转换单cpp字符串处理字符统计、简单加密、字典序排序单cpp搜索棋盘摆放、迷宫可行性、八皇后变体单cpp动态规划数字三角形、最长公共子序列、背包变体单cpp这种“一个cpp一道题”的结构对阅读者非常友好没有工程化的目录嵌套没有跨文件的类继承每一份代码都能独立编译、独立提交。我一般拿到这类资源会先按题型归个类把同类型的题放在一起对比着看这样比按题号顺序读更容易看出套路。2.2 技术选型为什么是C和stdio而不是别的翻看这份答案的代码绝大多数文件用的是C语言风格的输入输出scanf、printf、while(scanf(...) ! EOF)。这不是偶然POJ这类老牌OJ的G编译器对纯C风格的代码支持最稳而且基础题的输入量常常很大cin/cout在取消同步之前性能明显吃亏。也有一部分文件混用了C的algorithm头文件里的sort、max等函数注释里还会标注“该方法在G 4.7下测试通过”——这种版本敏感的信息对你有用它提醒你提交时最好不要依赖最新的C17特性。我自己的习惯是不论原代码用什么版本写的本地统一用-stdc11编译一次因为这是大部分OJ当前支持的底线编译不过的地方一眼就能看出来。3. 核心代码拆解从多组AB到搜索与DP的三类必背写法这一章是重点。基础题答案的代码普遍不长但里面有几个出现频率极高的模式值得逐行读。理解了它们再看其他文件会快很多。3.1 多组输入输出while(scanf(...) ! EOF)没有你想的那么简单POJ的很多入门题都不会告诉你“输入有多少组”而是让你自己读到文件结尾。第一题AB的标准写法是这样的// POJ 1000 标准AB写法支持多组数据 #include cstdio int main() { int a, b; while (scanf(%d %d, a, b) ! EOF) { printf(%d\n, a b); } return 0; }这里的scanf返回值是“成功读到的变量个数”如果读到文件末尾返回的是EOF值是-1。很多新手把scanf当“读一个值”用只写一次结果提交后要么只处理了第一组数据要么因为读不到数据而输出错误结果。printf(%d\n, ...)后面的\n也是重点OJ判题时比对的是“字节流”多一个空格、少一个换行都会被判Presentation Error。基础题的答案代码里大量使用\n结尾这就是为了严格匹配输出格式。我自己写这类题时会先看题目给的Example Output数清楚每个数之间的分隔符再决定用空格还是换行。3.2 高精度计算逆序存储与进位顺序是关键POJ一部分基础题涉及超出long long范围的大数运算。这类题不能直接定义整数变量而是把数字当字符串读进来再用竖式模拟。以高精度乘法为例// 高精度乘法字符串模拟竖式计算支持多组输入 #include cstdio #include cstring const int MAXN 100; // 支持最多99位数字相乘的结果位数 int res[MAXN]; // 逆序存储每位结果 int main() { char sa[100], sb[100]; while (scanf(%s %s, sa, sb) ! EOF) { memset(res, 0, sizeof(res)); int la strlen(sa); int lb strlen(sb); // 从个位开始逐位相乘i、j都从低位往高位走 for (int i 0; i la; i) { for (int j 0; j lb; j) { res[i j] (sa[la - 1 - i] - 0) * (sb[lb - 1 - j] - 0); res[i j 1] res[i j] / 10; // 进位放到下一位 res[i j] % 10; // 当前位只保留个位 } } // 去掉前导零但至少保留一位 int len la lb; while (len 1 res[len - 1] 0) len--; for (int i len - 1; i 0; i--) { printf(%d, res[i]); } printf(\n); } return 0; }res按下标从小到大存储的是结果的个位、十位、百位也就是“逆序存储”。这样做的好处是进位可以自然地向右扩展不需要预先知道结果位数。两个循环负责把s1的第i位与s2的第j位相乘结果累加到res[ij]随后马上处理进位——注意这里必须先加进位、再取个位顺序颠倒就会丢失进位。参数MAXN100对应结果最多99位遇到更大的数据把它改成500或1000即可。3.3 搜索题用DFS加剪枝替代暴力枚举基础题里的搜索主要考的是“能不能用递归把状态枚举完再剪掉明显不可能的路径”。八皇后变体和棋盘摆放类题目是常客。一个典型的棋盘问题DFS框架如下// 棋盘放棋子问题DFS深度优先搜索按行尝试放置 #include cstdio #include cstring const int MAXN 10; char board[MAXN][MAXN]; // 棋盘#表示可放位置 bool colUsed[MAXN]; // 该列是否已经放过棋子 int n, k, ans; // row: 当前搜索到第几行, placed: 已经放下的棋子数 void dfs(int row, int placed) { if (placed k) { // 放满k个方案数加一 ans; return; } if (row n) return; // 行数越界直接返回 // 分支1当前行不放棋子 dfs(row 1, placed); // 分支2在当前行找一个可放且列未被占用的位置 for (int c 1; c n; c) { if (board[row][c] # !colUsed[c]) { colUsed[c] true; dfs(row 1, placed 1); colUsed[c] false; // 回溯恢复现场 } } } int main() { while (scanf(%d %d, n, k) ! EOF) { if (n -1 k -1) break; // 结束条件 for (int i 1; i n; i) scanf(%s, board[i] 1); ans 0; memset(colUsed, false, sizeof(colUsed)); dfs(1, 0); printf(%d\n, ans); } return 0; }这个框架的核心是“按行枚举 列去重”两件事。dfs(row, placed)的两个分支分别对应“这行不放”和“这行放一个”第二种分支里通过colUsed保证同一列不会重复使用。回溯时把colUsed[c]恢复成false保证另一条分支的搜索空间不受污染。这里的剪枝其实只用了最基础的可行性约束但对基础题足够因为棋盘规模n不超过10状态总量可控。3.4 动态规划记忆化搜索是递推的直白翻译数字三角形这类DP题在答案资源里最常见的实现不是递推而是记忆化搜索。因为它的状态转移天然是“自顶向下”的写起来比循环更直观// 数字三角形从上往下走求路径上数字和最大值 #include cstdio #include cstring #include algorithm using namespace std; const int MAXN 105; int tri[MAXN][MAXN]; // 原始三角形 int dp[MAXN][MAXN]; // 记忆化数组-1表示还没算过 int n; int dfs(int i, int j) { if (dp[i][j] 0) return dp[i][j]; // 已经算过直接返回 if (i n) return tri[i][j]; // 到底部路径值就是自身 int left dfs(i 1, j); // 往左下方走 int right dfs(i 1, j 1); // 往右下方走 dp[i][j] tri[i][j] max(left, right); return dp[i][j]; } int main() { scanf(%d, n); for (int i 1; i n; i) { for (int j 1; j i; j) { scanf(%d, tri[i][j]); } } memset(dp, -1, sizeof(dp)); printf(%d\n, dfs(1, 1)); return 0; }dp[i][j]存的是“从第i行第j列出发能得到的最大和”初始化为-1表示未计算。当递归到i n时路径和就是该点本身否则取“左下”和“右下”两条路中较大的那个加上当前值后存入dp。记忆化搜索相比递推好处是免去了手动确定循环顺序的麻烦递归天然代表了状态依赖关系。缺点是递归深度受限于n这里n最大100完全不会栈溢出。4. 本地运行与自测把答案跑起来再往下读读代码不如跑代码。这部分教你把这堆cpp在你的机器上编译运行并且用本地数据验证答案正确性。整个过程不需要IDE命令行就够。4.1 文件命名与一键编译这份资源里的文件基本叫main.cpp或T1001.cpp前者直接g main.cpp -o main就能编后者按文件名编译即可。我建议你新建一个build.sh脚本把常用参数固定下来避免每次手打#!/bin/bash # 用法: ./build.sh T1001 # 编译OJ题解: 开启O2优化和C11标准显示所有警告 g -O2 -stdc11 -Wall -o main $1.cpp echo 编译完成: ./main-O2是开启优化对计算密集型题解能明显提升运行速度-stdc11锁死语言标准防止用到OJ不支持的语法-Wall打开全部警告基础题代码里常见的未使用变量、类型转换隐患都能暴露出来。编译参数不用再改后面只需要替换文件名参数。4.2 手工样例与diff验证OJ题目的Example Input和Example Output就是你的第一个测试集。我习惯把它们分别存成sample.in和sample.out然后./main sample.in my.out diff my.out sample.out是输入重定向让程序从sample.in读数据是输出重定向把结果写到my.out。diff逐行比较两个文件没有任何输出说明完全一致。这一步能筛掉大部分由于空格、换行不一致导致的格式错误。4.3 批量构造边界数据只跑样例远远不够。基础题最容易错的是边界n0、n取最大值、单组数据、多组数据。我一般会多写几个.in文件比如edge1.in里放最大规模数据edge2.in里放最小输入。再用一个循环批量跑for f in test_*.in; do ./main $f ${f%.in}.out echo 已处理 $f done注意标准输入的大数据量测试最好用文件重定向而不是手动粘贴否则本地能过、提交超时的案例很难复现。跑完后再把所有.out汇总对比一遍错误会在第一时间暴露。5. 常见问题排查编译、WA、TLE三类翻车场景的解决办法刷题的人谁没翻过车。这里把这份答案资源最容易碰到的问题整理成“现象→原因→解决”的记录都是实际踩过的坑。5.1 编译失败main.cpp在本地GCC编译不过现象自己机器上g main.cpp -o main直接报错错误信息长到看不完。原因老题解按当年的编译器标准书写有的用了gets有的漏掉某些头文件还有的依赖using namespace std;后面跟着的隐式类型转换。当前GCC版本更严格把过去的“能用”变成了“编译错误”。解决打开文件先看报错位置是不是gets——C11标准已经移除这个函数改成fgets(buf, sizeof(buf), stdin)再看头文件是否缺少cstring或algorithm补齐即可。我一般遇到这类文件会顺手把gets都替换成fgets并重新编译一遍确认。5.2 提交后WA本地秒过一到OJ就错现象sample.in输出和sample.out完全一致但一提交就是Wrong Answer。原因最常见的是把freopen(in.txt, r, stdin);这类本地重定向代码留在了提交版本里。OJ评测时读不到你的本地文件scanf返回EOF程序逻辑直接崩坏。解决提交前全局搜索freopen确认删除干净。另一个常见原因是代码里带了中文提示语比如printf(请输入n:);这也会污染输出。我在每次提交前都会做一遍“删除重定向删除提示语”的检查几乎可以消除这类低级WA。5.3 TLE数据一多就超时剪枝没做到位现象搜索类题目小数据秒出结果把n调大之后程序像卡住一样最终TLE。原因基础搜索题的隐藏数据往往比Example大很多纯暴力枚举状态数呈指数增长搜索树没有被有效剪枝。解决对照代码检查剪枝条件。像3.3节那个棋盘DFSif (row n) return和colUsed列去重都是必要的如果题目还要求“放满k个”可以再加一条if (placed k) return和“剩余行数不足”的剪枝。判断一个DFS写得对不对用n20的数据量自测运行时间超过1秒就要考虑加剪枝或换思路。6. 二次开发把答案库改造成你自己的刷题脚手架读题解只是第一步我更建议你把这堆杂乱的文件整理成一个自己的模板库。这一步做得好以后刷任何OJ都用得上。我给这份资源重新规划了目录结构把cpp文件按题型细分到math/、search/、dp/、string/四个文件夹里每个文件头部统一加上注释模板记录题号、算法类型、时间复杂度和个人备注。然后写了一个统一测试脚本#!/bin/bash # 用法: ./judge.sh T1001 # 自动完成: 编译 - 跑样例 - 对比输出 g -O2 -stdc11 -o main $1.cpp if [ $? -ne 0 ]; then echo 编译失败 exit 1 fi ./main test/${1}.in test/${1}.out if diff -q test/${1}.out test/${1}.expected /dev/null; then echo 答案正确 else echo 输出不一致 diff test/${1}.out test/${1}.expected fi这个脚本把“编译→重定向→diff”三件事合并成一条命令$?拿到编译返回值非零则中止避免带着编译错误继续跑。${1}是传入的题号参数比如./judge.sh T1001就会自动处理对应文件。在这个基础上你还可以加一个-p参数来指定只跑部分测试或者把脚本接到文件系统监听上保存代码后自动跑测试。对我来说整理题解库最大的收获不是收藏代码而是强制自己给每个文件写一行“这题为什么用这个方法”。从那以后我每次拿到一套新的题解资源都会强制走一遍“先分类、再编译、最后写注释”的流程确认每一个文件都能跑通后再谈阅读。这个方法帮我避免了很多“收藏了等于学会了”的错觉。希望帮到你。本文还有配套的精品资源点击获取