简介北大 POJ 部分基础题目答案合集面向 ACM 初学者和算法刷题者精选 1000 至 3673 号段中的百余道经典入门题覆盖 AB 输入输出练习、简单模拟、贪心、枚举、深度优先搜索、动态规划等常见基础算法常用于课程作业、实验室训练和 ACM 备赛前期的刷题参考。压缩包内共 157 个文件其中 156 个为 C 源程序文件cpp另附 1 个 txt 文本说明整包仅 59KB非常轻量便于直接下载、编译与查看。代码文件按照 POJ 题目编号逐一命名可以快速定位到对应题目的实现对于自制力较强的自学者卡题时可先读代码理清思路再独立重写对于集训队同学也可横向比较不同题解风格。目前已有 2652 人学习下载被不少入门选手用作日常练习时的代码参考适合正在系统准备 POJ 练习或 ACM 基础训练的同学。1. POJ是什么为什么基础题答案比你想的更值得对一遍北大POJPeking University Online Judge是国内最早的一批在线评测系统之一很多程序竞赛入门选手的第一道AC就诞生在这里。那些基础题不像竞赛题那么烧脑却把编译、输入输出、边界判断、格式错误这些坑一次性摆在你面前。我见过不少人刷到一半放弃不是因为题难而是因为“答案为什么是这样的”没人讲清楚。接下来我会把POJ前100号里的常考基础题拿出来梳理把每道题背后的规则、参数选择和常见误区拆开适合正在刷POJ入门、准备保研机试或想夯实C/C基本功的人。2. 从POJ 1000到1003送分题背后的输入输出与浮点陷阱2.1 用POJ 1000学会Online Judge的游戏规则POJ 1000是AB Problem题目描述只有两行读入两个整数输出和。看起来没有比这更简单的题但WA率不低。问题大多出在“多组输入”上。POJ的测试文件通常包含多组数据不是只跑一次。如果你写成#include stdio.h int main() { int a, b; scanf(%d%d, a, b); printf(%d\n, a b); return 0; }本地输入“1 2”输出3看着没问题可提交后往往Wrong Answer。因为评测系统会把多个测试用例放在同一个输入流里你的程序只读了第一组就退出了后面的数据没人处理。标准写法是循环读到文件结束#include stdio.h int main() { int a, b; while (scanf(%d%d, a, b) ! EOF) { printf(%d\n, a b); } return 0; }scanf的返回值是成功匹配的参数个数读到末尾返回EOF。这里用“!EOF”判断比“2”更通用因为当输入里混着非数字时返回值会小于2但出题人不会这么无聊。对AB这种题a和b的范围在int内不需要long long但如果你习惯用long long也不会错只是没必要。另一个隐形规则是“不要输出多余内容”。有些初学者喜欢在printf前加提示语比如“please input a,b:”这在本地练习没问题到了POJ就是WA。评测系统是把你的程序输出和标准输出逐字符比对多一个空格都不行。2.2 POJ 1001高精度乘方一上来就卡人的“基础题”POJ 1001计算R的n次方R是实数n最多25输出不能有多余前导零和尾随零。表面看用浮点运算就行但double直接pow会丢精度因为R的小数位数不同结果总和可能超过double的53位有效数字。这道题的通用解法是“去掉小数点变整数做高精度乘法最后把小数点放回去”。用Python写最直观import sys for line in sys.stdin: r, n line.split() n int(n) # 处理小数点记录小数位数再把字符串变成整数 if . in r: point len(r) - r.find(.) - 1 num int(r.replace(., )) else: point 0 num int(r) res str(num ** n) point * n # 如果整数位数不够补前导0这样才能插入小数点 if point len(res): res 0 * (point - len(res)) res if point 0: res res[:-point] . res[-point:] # 去除多余前导零整数部分只留一个0但题目要求不输出无意义的0 # 如果结果是纯小数常见的AC写法是去掉整数部分的0比如 .123 if point 0: res res.rstrip(0).rstrip(.) if res.startswith(0): res res[1:] if res.startswith(.): res res # 保留 .xxx else: res res.lstrip(0) or 0 print(res)这里的参数有三个point记录总小数位数num用整数做乘方避免浮点误差去零规则决定输出格式。POJ 1001的格式判定严格很多答案WA在“该去的零没去干净”。常见的争议点是0.0^1应该输出0还是0.0原题要求无多余尾随零所以输出0。另一个争议点是0.00001这类纯小数整数部分的0是前导零还是必需位数按题目“no unnecessary leading zeros”多数AC代码会输出.00001。如果你不确定就先把输出规则写在注释里逐个边界测。C/C也能做但要把高精度乘法和补零逻辑自己实现工作量主要在数组进位和字符串处理。建议新手先把Python版跑通理解规则后用C重写一遍因为POJ很多基础题在C上的速度优势明显。2.3 POJ 1002/1003字符串归一化与浮点累加的参数选择POJ 1002要把电话号码转成统一格式字母映射到数字去掉连字符然后统计重复号码并按字典序输出。映射表是基础参数char map[] 22233344455566677778889999;这里有个索引陷阱map的下标是字母减A但字母Q和Z并不存在所以表里第七个字符对应的是P后面跳过Q/Z。写错表会出现完全错误的结果。字符串处理时遇到字母就查表遇到数字保留遇到连字符跳过最后得到7位数字再输出成“XXX-XXXX”格式。这里如果用C的scanf(%s, s)读入要注意电话号码里没有空格所以%s能一次读完。统计重复用mapstring,int最省事但POJ老平台编译器较老需要包含和 。排序后遍历mapmap本身按键字典序排列正好满足输出要求。POJ 1003则是浮点累加的经典案例。题目给一个悬垂距离c求最少需要几块卡片。公式是1/2 1/3 ... 1/(n1)。代码很短#include stdio.h int main() { double c; while (scanf(%lf, c) c ! 0.0) { double sum 0.0; int n 0; while (sum c) { n; sum 1.0 / (n 1); } printf(%d card(s)\n, n); } return 0; }浮点累加的坑在于“c ! 0.0”的判断。如果测试数据里是0.000001浮点表示下不等于0会继续算但原题用0.0表示输入结束没有这种数据。为了避免非零极小值误判更稳的写法是 if (c 1e-9) break;。累加本身误差很小因为项数n最多几百double能覆盖。这个判断参数决定了程序能否正确退出别小看。3. 把基础题当模板题刷POJ 1004/1005/1007的常见套路3.1 均值与贷款读懂题目里的数学公式再动手POJ 1004 Financial Management给12个月的钱数求平均值并输出“$”加两位小数。代码三行但WA点有两个。第一个是格式化printf($%.2f\n, avg); 很多人写成printf($%f\n, avg)导致小数位数不对。第二个是浮点舍入12个浮点数的平均值double精度足够但某些数值在十进制下二进制无法精确表示例如其中有0.005这类值%.2f会按四舍五入可能产生离期望差0.01的结果。比较稳的做法是算完avg后加一个极小的修正量printf($%.2f\n, avg 1e-9);这个1e-9不会影响正常两位小数但能把因二进制误差导致的“比真实值略小”的情况扶正。类似技巧在POJ 1005里更好用。POJ 1005 I Think I Need a Houseboat给出一组点的坐标每年洪水侵蚀面积是50平方英里问第几年该点被淹没。半圆面积πr²/2设年份y需要πr²/2 50y所以 y ceil(r² * π / 100)。这里的r²就是x²y²读入都是整数但π用double表示最终结果取整。代码#include stdio.h #include math.h int main() { int t, kase 1; scanf(%d, t); while (t--) { double x, y; scanf(%lf%lf, x, y); double r2 x * x y * y; double years r2 * 3.141592653589793 / 100.0; int ans (int)ceil(years); printf(Property %d: This property will begin eroding in year %d.\n, kase, ans); } printf(END OF OUTPUT.\n); return 0; }注意输出格式里有“Property %d:”和“This property will begin eroding in year %d.”结尾还有一行“END OF OUTPUT.”漏掉任何标点都是Presentation Error。取整时如果years刚好是整数ceil不会让结果变大所以不需要担心边界。如果担心浮点误差把整数变成2.0000000001可以改成(int)ceil(years - 1e-9)但这里xy最大不超过100精度安全。3.2 排序与逆序数POJ 1007教会你的复杂度直觉POJ 1007 DNA Sorting输入若干等长DNA串要求按逆序数从小到大排序逆序数相同的保持输入顺序。逆序数定义为对于每个字符后面比它小的字符个数总和。计算时枚举两个字符int inversions(char *s, int len) { int cnt 0; for (int i 0; i len; i) for (int j i 1; j len; j) if (s[i] s[j]) cnt; return cnt; }DNA串只包含A/C/G/T所以也可以开一个长度为4的桶记录已出现字符的个数一遍扫描就能算出逆序数复杂度从O(n²)降到O(n)。但基础题里m和n都不大n≤50m≤100双重循环足够没必要优化。真正容易踩的是排序稳定性。C标准库的qsort不保证稳定如果你用qsort直接按逆序数比较逆序数相等的串顺序可能被打乱。C的sort也不是稳定排序stable_sort才是。所以要么把输入顺序作为第二关键字要么直接用stable_sort。struct DNA { char s[60]; int inv; int idx; }; bool cmp(const DNA a, const DNA b) { if (a.inv ! b.inv) return a.inv b.inv; return a.idx b.idx; }这里idx参数是顺序保证的关键。我见过有人用qsort然后怀疑评测数据有问题查了半天才发现是稳定性的锅。这类“参数补丁”在基础题里很常见不是题难是你用的函数行为和你以为的不一样。3.3 从答案到模板怎么把每道题沉淀成可复用的代码块刷到POJ 1007时你会发现自己已经积累了四类模板多组输入的main框架、浮点精度修正、字符串映射、稳定排序。建议每AC一道题就把核心片段存成一个文件命名成“poj1007_stable_sort.cpp”。后面遇到“稳定排序”需求直接把cmp拷贝改名不用重新想。模板库不需要大关键是分类清楚。我自己会把代码按“数学”“字符串”“排序”“高精度”“图论”分目录基础题里大多归前四类。另一个做法是写注释时把“为什么选这个参数”写进去。比如“用double不用float是因为float只有7位有效数字累计12个月误差超过0.01”。这样三个月后再看还是能回忆起当时的判断。很多答案帖子只贴代码不解释你复制粘贴AC了过两天又忘。真正值钱的是注释里的“因为”。4. 写答案前必看的输入输出细节EOF、多组数据与边界值4.1 EOF与while(scanf)的三种写法POJ基础题里多组输入的结束条件有三种读到EOF、读到0、读到特定字符串。对应写法是while (scanf(%d, n) ! EOF) { ... } while (scanf(%d, n) n ! 0) { ... } while (scanf(%s, s) ! EOF) { ... }第三种对字符串要小心因为%s遇到空格会断。如果一行里可能有空格应该用gets或fgets。有个老坑POJ的编译器支持gets但现代GCC已经移除gets建议用fgetschar buf[128]; while (fgets(buf, sizeof(buf), stdin) ! NULL) { // 处理buf }fgets会把换行符也读进来需要手动去掉否则字符串比较时多一个\n导致WA。处理方法是找出换行符的位置并置成\0buf[strcspn(buf, \n)] \0;这里strcspn是标准库函数会把尾部换行替换成字符串结束符。如果一行末尾是\r\n还需要先去掉\r但POJ通常是Unix换行只处理\n就够了。这类细节直接决定你“看着没问题”的字符串比较为什么WA。4.2 数组开多大POJ常见RE的元凶Runtime Error十有八九是数组越界。POJ 1002的电话号码有100000条每条串长不超过100但如果你开char s[50]某组数据行长一点就越界了。经验法则是题目给的上限再加10到20。比如说“length ≤ 50”就开char s[64]。说“n ≤ 100000”就开int a[100005]。多出来的几个位置用来放结束符和缓冲是刷题圈的默认习惯。还有一种越界发生在高精度乘法里POJ 1001小数位最多25位n最大25结果最多600多位。如果开char res[200]乘到一半就越界。建议开1000或者直接用动态字符串。数组开大不扣内存POJ一般内存限制64MB开个100万int也就8MB放心多给。// 常见错误写法按题面长度开没有预留结束符空间 char s[100]; // 假设题面说长度不超过100 scanf(%100s, s); // 即使这样s最多读100字符再加\0越界正确写法是char s[100 5]并且scanf里写%100s限制长度防止测试数据超长。另一个RE来源是除数为0比如 POJ 1005 里如果年份算出来为0ceil没问题但如果你在循环里除一个可变的n就要先判0。4.3 多组数据的变量重置翻车重灾区同样的代码第一组样例能过第二组开始错基本就是变量没重置。比如循环里用的sum、cnt、head指针声明在循环外但没在每轮清零。解法有两种把变量声明移到循环内每次自动初始化或者每轮开始手动memset。我倾向于“声明在循环内”因为这样不可能忘记重置。但注意某些结构体数组需要全部清空时memset比循环赋值快struct Node arr[1005]; memset(arr, 0, sizeof(arr));memset的参数是字节数sizeof(arr)这里的写法能自动算完整长度不要手写数字否则结构体大小变化时会错。重置和“多组输入”紧密相关我一般写完算法先自问这一轮结束到下一轮哪些变量还残留着把它加进每轮最前面。例如POJ 1007里如果保存逆序数的数组没清零下一组数据会把上一轮的旧值一起排序直接WA。5. POJ基础题避坑与常见问题排查现象→原因→解决5.1 Wrong Answer你的输出多了空行还是精度不对现象本地样例全对提交后立刻WA。原因输出格式和评测系统期望不一致最常见是多了一个换行或浮点小数位数不对。解决把样例输出复制到本地用diff对比看是不是行尾多空格。对于浮点题把printf的格式串单独拿出来检查%lf和%f混用不会崩但会输出错误。另外检查循环结束后是否多打了空白行POJ对“行尾空格”通常容忍但“多出空行”一定WA。我习惯把所有输出先拼成字符串或直接printf最后统一加换行而不是每行末尾都加。这里还有个玄学printf的%.2f在部分C库实现里对x.xx5这样的值会舍向偶数导致结果和标准答案差一分钱。虽然POJ的数据很少这么极端但刷题时多个1e-9的修正量能省去很多复查时间。5.2 Runtime Error数组越界与除零现象评测返回Runtime Error但本地跑没崩溃。原因评测数据里有你没预料的极端值。比如除数为参数n而n可以为0数组长度刚好是100但字符串长度也是100需要结尾符位。解决加边界判断if (n 0) continue; 数组开n5。还有一种RE是递归太深导致栈溢出基础题很少见但搜索题可能遇到把递归改成循环或增加栈空间。排查RE时先在本地把输入改成最大规模跑一遍比如n100000的随机数据看程序是否段错误。如果出现在scanf附近多半是没给字符数组留结束符位置出现在循环里多半是下标越界。可以用printf在可疑位置打点但提交前要删掉这些调试输出否则WA。5.3 Time Limit Exceeded基础题也会超时现象用了最直观的双重循环结果TLE。原因数据规模不是入门题里那么小。POJ 1002如果对每个号码都用strcmp插入到有序数组再前移最坏O(n²)n100000时直接超时。解决用sortmap复杂度O(n log n)或者读取时直接放unordered_map。基础题里TLE还会来自死循环比如while里条件写错导致sum永远小于c此时可以加一个计数器上限预防但根本上要检查循环变量是否每轮更新。// 某个循环里忘记更新i的经典翻车现场 int i 0; while (i n) { // 处理a[i] // 漏了i于是i永远等于0 }这类错误在本地很难发现因为本地测试数据量小死循环会立刻让你注意到但POJ评测机上程序会一直跑满时间限制才被系统杀掉。所以看到TLE先检查所有while循环的条件变量有没有更新再考虑复杂度优化。5.4 Presentation Error被忽视的格式错误现象返回PE。含义是答案正确但输出格式不对比如数字间应该有一个空格你输出了两个应该在每行末尾换行你忘了。PE比WA好诊断因为说明核心逻辑没问题。解决严格按样例输出排版注意样例里的Case、冒号、点号。我自己最常掉进“行末多空格”的坑所以在输出循环里写成for (int i 0; i n; i) { printf(%d%c, a[i], i n - 1 ? \n : ); }这个%c的写法用三元运算符决定分隔符既是模板也根治PE。另一个常见PE是“Case”和“case”大小写不一致或者冒号后漏了空格。提交前把样例输出逐字符看一遍别只看数字。6. 基础题答案的正确用法从抄答案到写题解一个老选手的收尾习惯刷到一定量后你会发现“答案”真正的作用不是让你AC而是让你停下来对比自己的实现和别人的实现。我最早的代码是从学长那拷来的POJ 1001 Python版当时只会改改变量名应付作业后来重看才发现里面处理前导零那段我从不理解。等到自己把补零逻辑重新推一遍才明白为什么要先补0再插入小数点。从那以后我的习惯变了无论题目多简单AC后一定做两件事第一把它归类进自己的模板目录第二在代码头部写三行注释——输入格式、输出格式、复杂度。这看起来笨却让基础题真正变成了地基。另一个收尾技巧是“看答案前给自己十分钟”。如果一道题卡超过半小时可以去看别人的题解但看完必须合上代码自己重写一遍而不是复制粘贴。教科书可能会告诉你算法原理但不会告诉你“printf的%c写法避免PE”这种血泪经验这些只在写题解和复盘时慢慢沉淀。我自己的目录里现在还有一份“POJ基础题避坑检查单”开数组看边界、多组数据看重置、浮点输出看误差、字符串看结尾符。每次提交前扫一遍WA率能降一半。基础题答案网上到处都是但不经过踩坑那些代码永远是别人的。希望这个习惯也能帮到你少走我当年走过的弯路。本文还有配套的精品资源点击获取