简介面向ACM算法入门者与北大POJ在线判题练习者这份答案合集收录一百五十余道题目的C参考实现覆盖基础语法训练、模拟枚举、递归搜索、动态规划、图论与数论等常见题型适合在刷题卡壳时对照代码结构、验证边界处理并复盘算法套路。压缩包为rar格式共157个文件其中156个cpp源码、1个txt说明文件整体仅59KB体积轻巧便于按题号检索、本地编译与快速运行。相关资源已有2654人学习下载在POJ入门练习中具备一定参考价值。读者可借此快速定位题目对应的实现方案观察输入输出格式处理、数组与循环写法、递归与搜索框架、状态设计等细节并在此基础上自行修改测试、补充注释逐步形成独立解题与排错能力。1. 从“样例过了却判错”说起基础题库到底在考什么在在线评测平台刷基础题库最常见的情况是样例跑出来一模一样提交后却是一屏红色判错。这份基础题目答案值得单独整理是因为它考察的是你能不能在没人提醒时把输入格式、边界条件、数据范围、输出细节一次做对而不是考“会不会写循环”。整份题库考点很集中输入输出与格式处理、枚举与模拟、简单数论与高精度、数组与字符串处理这四块占了绝大多数题目。先把格式和边界练成习惯再谈算法适合能写基本语法、但提交十道会错六道的读者。2. 输入输出与判题规则三类必考的多组数据写法基础题库里最容易拿分也最容易丢分的就是输入输出。很多人以为这类题“没有算法含量”结果在一道两数求和的变形题上反复失败回头一看代码逻辑完全正确错在只读了一组数据或者每组输出之后多打了一个空行。评测机不看你的思路它只看标准输出和你的输出是否逐字符一致。这一章要解决问题只有一个让你在读完题目的三十秒内就能判断出这题属于哪一种输入模型并且直接写出对应的读取骨架。2.1 评测机在读什么EOF 型、先给组数、哨兵结束基础题库的输入模型基本只有三种认清这三种八成格式问题就消失了。第一种是读到文件末尾也就是 EOF 型题目里通常写“多组输入”却不告诉你组数第二种是先给一个整数 T表示后面有 T 组第三种是哨兵结束比如“输入两个 0 时结束”这两个 0 本身不产生输出。三种模型的循环条件完全不同混用就是直接错。#include cstdio int main() { int a, b; // EOF 型scanf 返回成功读入的变量个数读到末尾时返回 EOF(-1) // 用 2 比 ! EOF 更稳能顺带挡掉读到一半就断掉的脏输入 while (scanf(%d%d, a, b) 2) { printf(%d\n, a b); } return 0; }这段代码里最关键的一个参数是scanf的返回值。它返回的是成功匹配并读入的变量个数不是“有没有读到东西”。所以判断 2的意思是“两个整数都读到了”而! EOF只保证“没到文件末尾”万一输入尾部多了一个空格或半个数字行为就会变得很难解释。用cin a b写在while条件里也是同样的效果表达式在流状态失效时转为假只是速度慢一些遇到输入量大的题目要加解绑或者直接换scanf。第二种“先给组数”的模型注意循环变量不要和题目里的数据变量撞名也不要在一开始就把 T 减成 T-1 而忘了循环次数。第三种哨兵模型判断条件写在读入之后、输出之前而且哨兵这一组绝对不能产生任何输出多打一行就是错。血泪经验是哨兵判断用if (a 0 b 0) break;单独一行写不要塞进while的括号里做复合条件出问题时连断点都不好下。提示本地测试 EOF 型题目时键盘输入需要手动发送结束信号直接在终端敲回车不会结束输入容易误以为程序死循环。2.2 真题演练组间空行与行末空格的处理题目描述大意是多组数据每组输出一行结果要求每组输出之后跟一个空行。很多人第一反应是printf(%d\n\n, ans);样例能过提交却判错。原因在最后一组有些题目的标准输出在最后一组之后不再需要空行多出来的空行会导致逐字符比对失败。正确做法是把“每组之后空行”改成“组与组之间空行”用一个标记变量控制第一组。#include cstdio int main() { int a, b; int first 1; // 标记是否是第一组数据 while (scanf(%d%d, a, b) 2) { if (!first) printf(\n); // 空行打在组前最后一组之后自然就没有空行 printf(%d\n, a b); first 0; } return 0; }这个写法的思路可以迁移到几乎所有“分隔符”类需求上多个数之间用逗号隔开、多组之间空一行、输出末尾不能有多余符号本质都是同一个模式——把分隔符打在元素前面并且让第一个元素不输出分隔符。反过来如果你的分隔符是“行末不能有空格”这种要求也要用同样的标记法而不是先输出再想办法删掉因为标准输出一旦写出去了就撤不回。行末空格是另一个高频失分点。有些题目对行末空格宽容有些则严格逐字符比对判题结果会显示格式错误而不是答案错误。稳妥的写法永远是最后一个元素单独处理或者用标记控制“元素前加空格”。这类细节没有办法靠临时检查发现只能靠写代码时的习惯。另外提醒一句题目里给的样例通常只有一组数据它验证不了多组逻辑。自己至少造三组一组正常、一组边界比如 0 或 1、一组数量较多。造数据这一步花两分钟能省下后面半小时的反复提交。2.3 精度与取整整数除法和浮点输出的分界线基础题库里有一类题目答案看着是整数但中间过程必须用浮点或者反过来看着要小数其实必须全程整数。分界线在于只要题目问的是“有多少个”“第几个”“是否整除”就一律用整数运算只要问的是“平均值”“比例”“几何长度”才引入浮点。整数除法的规则要记牢两个正整数相除是向下取整所以7 / 2是 3不是 4。要求向上取整时不要写(int)ceil((double)a / b)浮点误差会在大数上让你莫名其妙少一。整数的向上取整有固定写法前提是 a 非负、b 正数。// 向上取整的整数写法把余数补进去避免浮点误差 int ceil_div(int a, int b) { return (a b - 1) / b; // a 0, b 0 } // 四舍五入到整数正数用 0.5 截断负数要单独处理否则会往错误方向舍 int round_half_up(double x) { return x 0 ? (int)(x 0.5) : (int)(x - 0.5); }参数上要注意a b - 1这个式子在 a、b 都接近 int 上限时会溢出把参数改成long long就没事了。浮点输出用printf(%.2f, x)时保留位数的舍入由库函数处理但 x 本身可能已经是1.0049999这样的值所以涉及“能否整除”“是否相等”的判断一定要回到整数世界用取余做不要用fabs(x - y) 1e-8去判整除。注意浮点比较必须带误差容限直接写if (a b)在浮点上是无效写法误差会随运算次数累积。3. 枚举与模拟基础题库里占比最高的一类题怎么套模板如果统计一下基础题库的题型分布枚举和模拟加起来能占到一半以上。这类题的特点是不需要复杂算法但题面长、细节多、边界碎。很多人的误区是“这题我会”于是读完题直接开写写到一半发现状态定义错了推倒重来。真正稳定的做法是先花两分钟把状态、操作、边界、输出四件事写清楚再动手。3.1 枚举的三要素范围、判定、剪枝枚举题的通用骨架只有三件事枚举范围有多大、怎么判定一个候选是否合法、能不能提前剪掉不可能的分支。写之前先估一下最坏情况的计算量一秒钟的评测窗口大致能承受千万级别的简单操作超过这个量级就说明枚举方式需要改而不是硬交上去等超时。#include cstdio #include cmath int main() { const int LIM 100; // 找 100 以内的勾股数x^2 y^2 z^2 for (int x 1; x LIM; x) { for (int y x; y LIM; y) { // y 从 x 开始避免 (3,4) 和 (4,3) 重复 int s x * x y * y; int z (int)(sqrt((double)s) 0.5); // 开方后四舍五入取整 if (z * z s z LIM) { // 关键用整数回代验证别信浮点 printf(%d %d %d\n, x, y, z); } } } return 0; }这段代码里有两处值得记住的写法。第一处是y从x开始这是最朴素的剪枝直接把结果数量减半同时天然去掉了顺序不同的重复解。第二处是开方之后一定要用整数乘法回代验证因为sqrt对完全平方数可能返回4.999999直接截断就变成 4答案就错了。判定条件里加z LIM是为了防止开方后的边界溢出。更一般的剪枝思路是把多层循环里能提前算出来的量提到外层。比如判定条件只和x y有关就可以先枚举x y的取值再拆成 x 和 y把三重循环降到两重。这类改造不需要算法知识只需要在写之前问自己一句“这一层循环里有没有什么是不依赖最内层变量的”。3.2 模拟题的四步拆解与真题演练模拟题的题面通常描述一个过程若干盏灯被反复拨动、若干个人围成一圈报数、某一年某一天往后推若干天。这类题的正确打开方式是四步。第一步定状态也就是用什么变量或数组记录“当前局面”每个下标代表什么第二步定操作把题面里的一句话翻译成一行代码第三步定边界也就是下标的起止范围、循环轮数的上限第四步定输出明确要输出的是最终状态还是中途某一步。以开关灯为例有 n 盏灯初始全灭第 i 轮拨动所有编号为 i 的倍数的灯问最后哪些灯是亮的。#include cstdio const int N 1010; int lamp[N]; // 全局数组默认清零状态语义1 表示亮0 表示灭 int main() { int n; scanf(%d, n); for (int i 1; i n; i) { // i 是轮次 for (int j i; j n; j i) { // j 是灯编号每次跳 i 步 lamp[j] ^ 1; // 拨动一次状态翻转 } } for (int i 1; i n; i) { if (lamp[i]) printf(%d , i); } return 0; }状态定义是lamp[1..n]下标 0 空着不用这是为了避免“编号从 1 开始还是从 0 开始”在心里来回换算。操作翻译成lamp[j] ^ 1比写if (lamp[j]) lamp[j] 0; else lamp[j] 1;短且不易错。边界上j i保证只遍历倍数i n保证轮次不越界。整个算法的时间复杂度大约是 n 乘以调和级数n 到一万以内都很轻松。这题还有一个可以拿来验算的结论最后亮着的灯编号一定是完全平方数。手头没有评测机的时候用这个结论对小数据手动核对比盯着代码看有效得多。模拟题最怕的就是“逻辑看着对”一定要有一个独立于代码的验算手段。3.3 打表与预处理把重复计算搬到循环外面有一类题目会连续给很多次询问每次问的东西不一样但背后依赖同一张表。比如多次询问“某个数以内有多少个素数”如果每次都从头筛一遍时间必然不够正确做法是在程序开始时预处理一次之后每次询问直接查表。#include cstdio const int MAXN 1000000; bool notPrime[MAXN 1]; int cnt[MAXN 1]; // cnt[i] i 以内的素数个数 void init() { notPrime[0] notPrime[1] true; for (int i 2; i MAXN; i) { if (!notPrime[i]) { // j 必须用 long longi 接近 1e6 时 i*i 会超出 int 范围 for (long long j 1LL * i * i; j MAXN; j i) { notPrime[j] true; } } cnt[i] cnt[i - 1] (notPrime[i] ? 0 : 1); // 前缀和边筛边累加 } } int main() { init(); int q, x; scanf(%d, q); while (q--) { scanf(%d, x); printf(%d\n, cnt[x]); // O(1) 回答每次询问 } return 0; }这里有两个参数细节值得单独说。j从i * i开始而不是从2 * i开始因为比 i 小的倍数一定已经被更小的素数筛掉了从平方开始能省下近一半的重复标记。j的类型必须是 64 位i * i在 i 超过约 46340 时就会溢出成负数循环条件依然成立但行为完全错误最终结果是运行超时和答案错误同时出现很难排查。预处理和打表的适用条件是询问次数多且每次询问的答案只依赖于固定的预处理结果。如果答案还依赖每次询问的其他参数就不能直接查表需要考虑前缀和、差分这类能在 O(1) 时间内拼出答案的结构。判断标准很简单把所有询问按参数排序后答案能不能通过一次遍历递推出来。4. 数论与高精度一眼看不出算法时的保底拿分路线基础题库里总有那么几道题读完题没有任何思路既不是枚举也不像模拟。这类题九成落在这几块最大公约数与最小公倍数、素数判定与筛法、进制转换、高精度加减乘、以及“数因子个数”这类简单计数。它们的共同点是模板固定、变体少背下来就能直接用属于投入产出比最高的部分。4.1 最大公约数、素数判定、进制转换的固定写法最大公约数的辗转相除、素数判定的试除到根号、进制转换的短除法取余这三个模板建议练到不看资料也能写对。它们的共同坑是边界0 和 1 不是素数、负数取余、以及乘法溢出。// 辗转相除b 为 0 时 a 就是答案天然处理了 0 的情况 int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } // 最小公倍数先除后乘防止 a*b 溢出 int lcm(int a, int b) { return a / gcd(a, b) * b; } // 素数判定只试到根号条件用 1LL*i*i n 避免 i*i 溢出 bool isPrime(int n) { if (n 2) return false; // 0 和 1 都不是素数这一行最常被漏 for (int i 2; 1LL * i * i n; i) { if (n % i 0) return false; } return true; }lcm里先除后乘这个顺序不是风格问题而是正确性问题。两个接近 int 上限的数先乘再除中间结果早就溢出了最后得到的答案可能是个负数。isPrime里用1LL * i * i而不是i * i理由和上一节的筛法完全一样。进制转换的模板是短除法不断对目标进制取余把余数压进数组最后逆序输出。要注意的是超过十进制的进制需要把余数映射成字母而字母的大小写在不同题目里要求不一样题目说小写就小写别凭习惯写。另外负数要单独处理符号位0 要单独输出否则逆序输出会变成空。4.2 高精度加减乘数组模拟手算流程当题目里的数字超过 64 位能表示的范围时就要用高精度。高精度的思路很朴素把数字当成字符串读进来逐位存进数组低位在前然后像小学竖式一样逐位运算、处理进位。低位在前这个约定是为了让进位方向与数组下标增长方向一致写在纸上算一遍就明白了。#include iostream #include string #include vector using namespace std; // 高精度加法低位存在下标 0返回同样低位在前的数组 vectorint add(const vectorint A, const vectorint B) { vectorint C; int carry 0; // 进位 for (size_t i 0; i A.size() || i B.size() || carry; i) { int sum carry; if (i A.size()) sum A[i]; if (i B.size()) sum B[i]; C.push_back(sum % 10); // 当前位的值 carry sum / 10; // 留给下一位的进位 } return C; } // 高精度乘低精度适合大数 × 普通整数这类题 vectorint mulLow(const vectorint A, int b) { vectorint C; long long carry 0; for (size_t i 0; i A.size() || carry; i) { long long cur carry; if (i A.size()) cur 1LL * A[i] * b; C.push_back(cur % 10); carry cur / 10; } while (C.size() 1 C.back() 0) C.pop_back(); // 去掉多余的前导零 return C; }add的循环条件里带上carry是关键最高位产生进位时要能继续写一位否则99 1会输出00。mulLow里用long long存cur因为A[i] * b在 b 接近 int 上限时会溢出 int。最后那个while用来去掉前导零但要注意保留至少一位否则结果 0 会被删成空数组输出一片空白。提示高精度题的输入长度往往在几百到几千位读入用string比逐字符scanf稳转换时记得减去字符0而不是数字 0。4.3 真题演练阶乘末尾零的个数题目给定 n求 n! 末尾有多少个连续的 0。直接算阶乘再数零在 n 稍微大一点时就完全不可行但这题的解法只有三行。// n! 末尾连续 0 的个数 n! 中因子 5 的个数 // 因为因子 2 的数量永远多于 5配对的上限由 5 决定 int trailingZeroes(int n) { int cnt 0; while (n 0) { n / 5; // 先数 5 的倍数再数 25 的倍数它们贡献两个 5依次类推 cnt n; } return cnt; }答题思路可以拆成三层来想。第一层末尾的 0 来自 10而 10 2 × 5 分解成质因数所以问题变成数因子对。第二层1 到 n 里 2 的倍数明显比 5 的倍数多所以因子 2 一定够用瓶颈只在于 5。第三层5 的倍数里25 的倍数含两个 5125 的倍数含三个 5所以要逐层除以 5 累加而不是简单算n / 5就完事。这题最容易犯的错就是只写了一层return n / 5;在小数据上碰巧对n 到 25 就少算一个。判断自己有没有想清楚的方法手算 n 25 时答案是 6因为 5、10、15、20 各贡献一个 525 贡献两个。能手动算出这个 6才说明真的理解了这三层。5. 易错点五类在评测机上必挂的写法与改法基础题库的判错信息很少通常只有一句判错、超时、运行错误。想提高一次通过的比率与其反复提交试错不如把最常见的几类写法问题提前列出来写完代码逐条对一遍。下面五条是翻车频率最高的每一条都配了具体的错误写法和改法。5.1 数组越界与 0/1 下标混用错在哪题目里编号是 1 到 n代码里却习惯性地开int a[100]然后访问a[n]n 取到 100 时就越界了。为什么错数组长度写的是“元素个数”而下标最大值是“元素个数减一”一旦编号从 1 开始就必须多开一位。这类问题在本地不一定崩因为越界只写了一点点可能刚好落在别的变量上表现成“结果偶尔不对”非常难查。怎么答对长度一律按“最大编号 1”开并且养成把数组开在全局的习惯全局数组默认清零还能避免栈上开大数组导致的运行错误。下标从 1 开始的题就全场从 1 开始不要在循环里一会儿i n一会儿i n那是最容易混的地方。5.2 死循环与超时循环变量没更新错在哪多组输入的while里写了if (a 0) continue;本意是跳过这一组结果循环变量根本没读新的条件永远成立。为什么错continue只是跳到下一轮循环开头如果这一轮的输入语句在continue之后就再也不会执行循环变成空转。表现是本地运行时卡住不返回提交后判超时。怎么答对读入语句永远放在循环体的第一行所有判断都放在读入之后。需要跳过时确认跳过的只是处理逻辑不是读入逻辑。写完多组输入的代码后本地至少跑三组数据看程序能不能正常退出这是最省时间的自检。5.3 整数溢出int撑不住累加和乘积错在哪题目说 n 不超过十万于是用 int 存所有数的和结果每个数接近十亿累加后溢出成负数。为什么错判断溢出要看的是运算结果的量级不是单个输入的量级。n 个数相加的上界是 n 乘以单个数上限两个 int 相乘的上界是约 2×10^18早就超过 int 的 2.1×10^9。怎么答对只要涉及累加、累乘、平方、下标乘法一律先按 64 位思考确认范围后再决定要不要降回 int。快速判断口诀是题目里出现“和”“乘积”“平方”“方案数”默认开 64 位。另外输出格式符也要同步改用 int 变量配%d、64 位变量配对应的格式符类型不匹配本身就会输出垃圾值。5.4 多组数据不清空上一组的状态污染下一组错在哪把标记数组、计数器定义成全局变量多组数据之间没有重新初始化第二组数据的答案受第一组影响。为什么错全局变量在整个程序生命周期内只有一份第一组跑完留下的值会原样进入第二组。第一组数据往往就是样例所以本地测试完全看不出问题。怎么答对每组的处理逻辑开头统一做一次初始化位置固定不要分散在代码各处。用memset清数组时注意按字节清零对整型数组写 0 是安全的如果要用其他初始值得用循环或者专门的填充方式。判断标准很简单把同一组数据连跑两遍两次输出必须一致不一致就说明有状态没清干净。5.5 输出格式行末空格、大小写、多余空行错在哪输出一串数字时写成printf(%d , a[i]);最后一个数后面也带了一个空格。为什么错部分题目采用逐字符比对多一个空格就判格式错误。另一些题目会忽略行末空格于是同一份代码在不同题目上表现不一致让人误以为是算法问题。怎么答对输出序列时用“元素前加分隔符”的写法第一个元素单独处理输出多组时用“组间空行”的写法最后一组之后不加。题目里要求的单词大小写比如答案要求全大写就照抄题面不要按自己的习惯写。提交前把样例输出复制出来和题目给的样例逐字符比一遍肉眼看不出来就数一下空格。6. 答题节奏与自查清单从读题到提交的六步法把前面几章的东西收拢成一个可以重复执行的动作序列比记住一堆零散技巧更有用。我自己的习惯是六步前两步不写代码后四步不跳步。第一步读题两遍第一遍抓输入输出格式第二遍抓数据范围。格式决定读取骨架范围决定用 int 还是 64 位、用数组还是用表。第二步手算样例尤其是边界样例比如 n 1、全是 0、只有一组数据。手算过的题写代码时错误率明显下降因为你知道正确结果长什么样。第三步估复杂度。把最坏情况的循环次数在心里乘一遍超过千万级别就想办法降一维或者加预处理。第四步写代码同时写注释注释只写“这一段在干什么”不写废话。第五步自造数据至少三组一组最小、一组最大、一组有重复或特殊值。第六步提交前过一遍清单。自查项具体检查什么漏掉的后果输入模型EOF、先给组数、哨兵三者选对了吗只读一组答案错误数组长度是否按“最大编号 1”开是否放在全局越界结果随机或运行错误数据类型累加、乘积、平方是否用了 64 位溢出成负数初始化每组数据开头是否清空了标记和计数器第二组开始答案错边界0、1、最大值是否单独想过小数据对大数据错输出格式行末空格、组间空行、大小写格式错误或答案错误这张表我一般是在提交前扫一眼三十秒能过完但能挡掉大部分低级错误。真正需要动脑的题目其实不多多数失败是因为格式、边界、类型这三件不需要动脑的事没做对。从那以后我每次写完代码都强制走一遍“同一组数据连跑两遍”和“造一组最大数据”这两个动作不管题目多简单。这两个动作花不了两分钟却能让我少提交五六次。希望帮到你。本文还有配套的精品资源点击获取
