简介面向北大POJ初学者的C题解集合涵盖从1000到1008、1011到1014以及1016、1017等百余道基础题目覆盖简单模拟、数学推理、字符串处理、动态规划等常见入门算法方向可作为算法竞赛起步阶段的代码参考。压缩包为RAR格式共157个文件其中156个为cpp源代码文件另有1个txt说明文件整体仅59KB便于下载后快速查找与使用。代码按题目编号独立组织每个cpp文件对应一道POJ题目读者可对照题目需求直接编译运行验证解法逻辑并参考不同题目的实现思路从中对比同类问题的不同处理方式。资源已有2653人学习适合ACM入门者、算法练习者在刷题遇到瓶颈时查阅也可作为课程设计或竞赛训练的辅助题库帮助系统积累基础题型的代码范式节省从零编写和调试的时间无论自学还是备赛都具有参考价值。1. POJ基础刷题卡住时这份参考答案就是一张地图一个周末晚上我在POJ上刷一道模拟题本地随便测都是对的一提交就是Wrong Answer翻来覆去改了快一小时没找到错在哪。这种经历在ACM基础刷题阶段几乎人人都会碰到不是不会写代码而是不知道OJ判题到底在跑什么。这份“北大POJ部分题目答案”收录了一批基础典型题目的AC代码从输入输出、模拟、搜索到图论入门都有涉及特别适合刚注册账号准备刷题的新手——卡住的时候打开对应题号的代码照着编译、对着输出通常一眼就能看出自己的问题。2. 资源全貌按题号组织的代码包与题目覆盖地图2.1 目录结构每个题号一个文件夹提交只需一个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看到这个结构就能明白这份资源不是排版精美的教程PDF而是刷题过程中真实积累下来的源码包。每个.cpp都是可直接提交到POJ的完整代码readme.txt通常是题目大意、思路笔记或者当时的调试记录README.md则是整个包的索引。提交时只需要把对应cpp的内容复制到网页提交框里即可文件夹本身只是为了本地好分类。正因为它是“答案包”而不是“题解书”所以代码里保留了刷题者当时的习惯——变量命名可能不讲究注释也可能只有一两行但优点是每道题都能编译能跑适合拿来对照而不是拿来背。2.2 题目覆盖从输入输出到算法入门的完整跨度包里的题目不算多但覆盖范围拎出来正好是POJ基础题的高频考点。我挑了六道有代表性的列成一张表你能直观看到这份资源的性价比题号类型核心考点典型坑点1000输入输出scanf/printf 与 EOF 循环多组数据处理1001高精度大数乘方、小数点位处理末尾零和整数部分为零1006数论同余方程组结果取模修正1008模拟两种历法互转月份天数表写错1088DP/递归记忆化搜索递归深度和方向数组1258图论Kruskal 并查集多组数据重置并查集从这张表能看出一个明显的阶梯先过输入输出关再写模拟题锻炼逻辑接着进入递归和搜索最后上手经典图论算法。这正是ACM刷题从零到一的主流路线也是很多开发者在准备算法笔试时走的捷径。资源里收录的“基础题”不是那种随便写两行的水题而是每道都有固定套路、值得反复揣摩的入门题。2.3 读答案的正确姿势先想后看逐段注释这类答案包最大的风险是让人直接抄。如果只把代码复制粘贴提交拿AC那这个包对你的价值基本归零。我拿到这份资源以后给自己定了个使用流程拿到一个题目编号先不打开答案自己在编辑器里写卡住以后再看cpp而且不是从头看到尾是先看readme.txt了解题目归类再只看关键函数比如忘了并查集就只看find函数不碰main。一个更有效的操作是把你自己写的半成品和答案放在左右两栏逐行找差异。曾经有一道模拟题我怎么都WA对照答案才发现自己月份天数表里二月写了28天没考虑闰年。这种差异靠肉眼盯着自己的代码很难发现但一对比就出来了。看完答案以后把文件关掉重新独立写一遍直到能不参考任何东西提交AC。这套流程走完题目套路才真正留在脑子里而不是留在下载文件夹里。3. 核心代码精读三道题看透POJ基础题的套路前面把资源全貌讲清了这一章我挑三道有代表性的题目——1000、1088、1258——把代码逐段拆开。这三题正好是三个阶段输入输出基础、递归搜索、图论经典算法。看懂这三段包里的其他题基本就是同一套思路换了个场景。3.1 POJ 1000EOF循环与格式化输出#include cstdio int main() { int a, b; while (scanf(%d %d, a, b) ! EOF) { printf(%d\n, a b); } return 0; }这段是POJ 1000的经典写法。OJ判题时会把一个输入文件喂给程序文件里可能有很多行a b但题目不会告诉你到底有几组。scanf的返回值是成功读到的变量个数读不到任何数据时返回EOF。while条件里的! EOF让程序持续读到文件尾才退出这样就能处理任意多组数据。参数说明scanf(%d %d, a, b)中第一个%d匹配a第二个匹配b中间的空白字符会自动跳过输入流里的空格、Tab 和换行。printf(%d\n, a b)则是在每次读入后立即输出结果并换行。有人习惯写for(;;) { cin a b; if (cin.fail()) break; }功能一样但scanf版本在POJ的G环境下更快当题目输入数据量比较大的时候IO快慢会对运行时间产生肉眼可见的影响。这道题唯一的坑就是多组输入。如果只写scanf和printf而没有while循环程序处理完第一行就退出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)出发能走的最长距离。dp[x][y]用来缓存已经算过的位置避免重复递归这就是记忆化搜索。longest初始为1表示当前点本身也算一步四个方向都试一遍只要下一个点高度严格低于当前点就递归往下走。主函数里遍历所有起点取最大值。参数说明dx和dy是方向数组按“左上右下”四个方向探测。map[nx][ny] map[x][y]是这道题的核心约束——只能往更低的地方滑不能相等否则路径就出现循环。memset(dp, -1, sizeof(dp))把缓存初始化为 -1因为合法的最短距离最小是1用 -1 表示“还没算过”。这里有个新手经常翻车的地方如果把写成题目要求严格递减所以相等高度不能走还有的写法在递归里回溯修改标记数组那是搜索的写法不是记忆化搜索。两种都能算对但搜索写法在这个数据范围下会重复计算大量子问题边界一大就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列的邻接矩阵问连接所有农场的最小网线长度典型的最小生成树问题。这里用Kruskal算法先把所有边按权值排序再用并查集判断两个端点是否已经在同一棵树上不在就合并同时累加边权。并查集的find函数写成了带路径压缩的递归形式每次查找会把链上所有节点直接挂到根节点下面后续查找接近O(1)。参数说明if (i j)是为了把邻接矩阵去重成无向边。因为矩阵是对称的i j保证了只取上半三角一条边只处理一次否则会重复加边导致结果偏大。cnt n - 1是提前退出的条件一棵n节点的树只需要n-1条边收集够了就没必要继续扫剩余边。注意fa数组没有初始化而是在每组测试数据开头用循环重置这是多组输入题目最容易漏的一步。这道题的价值在于Kruskal 并查集是图论入门的必修组合。代码量不大但一旦掌握后续的带权并查集、最小生成树变种都能从这个基础版本扩展出去。把这个版本理解透了再去看代码包里其他图论题会发现结构都差不多。4. 本地跑通从源码到亲手看到输出4.1 一条g命令完成编译运行代码拿到手先要跑起来。在Linux或者Mac终端上最直接的方式是g 1000.cpp -o 1000 ./1000-o 1000指定输出的可执行文件名不写默认是a.out。Windows下没有g的话可以用MinGW或者Dev-C命令基本一致生成的是1000.exe。我一般会顺手加一个编译警告参数让它更严格一些g -Wall 1000.cpp -o 1000加上-Wall后编译器会把未使用变量、类型转换不匹配这类问题也列出来。虽然警告不影响生成可执行文件但很多时候那些不起眼的warning就是WA的根源。比如%d对应了一个long long类型的变量GCC默认情况下不一定报错可输出就是错的。这类问题越早暴露越好。4.2 用题目样例验证输出结果POJ每道题都会在题目页面给出一组输入样例和输出样例。不要直接手动在终端里敲因为以后写到的模拟题、图论题输入动辄几十行手敲既慢又容易出错。正确做法是把样例保存成文件./1000 input.txt这个命令把input.txt作为标准输入喂给程序终端里直接看到输出。如果想和官方输出逐字节比对用重定向加diff./1000 input.txt output.txt diff output.txt expected.txtdiff没有任何输出就代表两个文件完全一致有输出会把每一处差异标出来。OJ判题的本质就是这个流程编译你的源码用测试文件作为输入然后把你的程序输出和标准答案文件逐字节比较。所以diff过了样例就一定过。4.3 自己造边界数据样例只是最低限度的验证提交前最好自己构造几组边界数据。常见的几个方向# 1258的边界n1时没有边MST总长应为0 1 0 # 1008的边界跨年的日期转换检查年份进位 # 1001的边界结果为0.0时输出0而不是0.0我一般会用Python写个小脚本生成随机数据再用暴力算法跑一个小数据量版本和参考答案程序对拍。这个习惯能提前拦截掉绝大多数WA原因。比如并查集忘记重置、数组开小、明知会溢出还用了int。边界数据的价值比样例高得多因为样例是题目作者给的绿灯而边界数据是你自己设定的红灯。5. 避坑指南POJ提交常见的四个问题5.1 本地编译通过一提交就WA现象本地跑样例、跑随机数据全对提交到POJ返回Wrong Answer没有任何其他提示。原因最常见的是数组长度小于题目给出的数据范围其次是多组测试数据之间没有完全重置全局状态。比如上一组输入的残值被这一组读到导致计算错乱。还有一种情况是scanf格式写错输入数据一多就读偏了。解决每次写完代码先检查数据范围对应的数组长度一律开到“上限5”。多组输入的程序在main开头把所有全局数组和计数器重新初始化不要信任上一次循环留下的任何残留值。另外scanf严格按格式串匹配输入末尾多一个空格都可能让后续读取错位格式化字符串里少用多余字符。5.2 Presentation Error空格和换行的格式陷阱现象OJ返回Presentation Error看输出内容全对就是格式不对。原因多输出了一个空格、行尾多了一个空格或者最后一行缺少换行。POJ对格式的挑剔程度超出预期PE已经算半个AC但仍然是错误。解决把所有输出语句统一成%d\n这种紧凑写法。题目要求两个数字之间用空格分隔就严格只在两个数字之间放一个空格行末不要加空格。我见过一个典型错误是用for循环输出数组每个数后面都跟了一个空格样例恰好只有一个数所以过了数据一多就PE。正确做法是判断不是最后一个元素才打印空格。5.3 Runtime Error数组越界与递归爆栈现象本地运行正常提交后返回Runtime Error。少数情况下本地也能复现程序直接崩溃或者报Segmentation fault。原因数组下标访问越界或者递归层数太深。POJ基础题的数据范围虽然不大但有些题目递归深度和矩阵规模是绑定的比如1088着滑雪题极端情况下递归链可能很长。局部定义的大数组也可能在栈上溢出因为默认栈空间有限。解决大数组一律定义成全局变量而不是main里的局部数组。全局变量在数据段分配空间大得多。递归型的DFS优先考虑改成记忆化搜索已经算过的状态直接返回既降低递归深度又省时间。如果题目确实需要深递归用vector或显式栈代替。5.4 语言选项选错导致CE现象本地用G编译运行都没问题提交时选了C报Compile Error。原因POJ的G和C选项背后是不同的编译器体系对个别语法支持不同。最典型的差异是__int64这种东西GNU系编译器有自己的long long而某些C编译器环境下直接写__int64会编译失败。解决统一提交语言选G。如果你做题时用的是C代码里就只写long long避免用编译器的私有扩展。另一个常见CE原因是提交时把代码复制漏了比如只复制了一部分、漏了头文件或者漏了using namespace std;。提交前自己先编译一遍再检查复制的代码首行是#include末行是return 0;}基本就能绕开这类低级错误。6. 二次改造把答案包变成你自己的模板库当你照着答案把几十道题跑通并理解后下一步不是继续抄新题而是对这份资源做一次“二次开发”把里面的代码精华提炼成自己的模板。我拿到答案包后的第一件事是建一个mytemplates/目录把每一类题目的通用骨架抽出来。以POJ 1000为基础我会把输入输出套路边角料整理成一个通用模板#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解耦调试时只需要盯着solve()内部。换新题时把数据结构定义和solve内容替换掉就行。模板整理好以后我再按“模拟、搜索、DP、图论”建四个子目录把答案包里每一道题的代码都塞进去并加上自己的注释。注释只写两个东西这题用了什么算法以及我第一次提交的时候错在哪。比如在并查集模板里我会注明“每组数据必须重置fa”在输出模板里注明“行末不要多余空格”。整理过程中有一个值得尝试的技巧把答案代码的变量名改成自己能理解的名字。原本可能是一个字母的d我改成dist或者depth。改名不是为了运行而是为了让三个月后的自己回看时不需要猜。做完这一步这份资源就变成了“我自己的题库”每次刷完一组题我强制自己把提交过的代码重新整理进模板库然后打开答案包删掉已经吃透的题目目录。从那以后我每次刷题都会先跑一遍边界数据再交再也不会出现本地全对一提交就WA的情况。希望帮到你。本文还有配套的精品资源点击获取