POJ基础题单AC指南：判题规则、六类模板与易错点

简介面向ACM算法入门与课程练习的北大POJ题解代码包覆盖1000至1008、1011至1014等一批基础题目适合刚开始接触在线评测、需要对照参考实现来理解题意与边界处理的读者。压缩包共157个文件其中156个cpp源码和1个txt说明文件整体仅59KB体积轻巧便于按题号检索和在本地编译调试。已有2654人学习或下载说明这套基础题解在入门阶段具有一定参考价值。读者可从中获得常见输入输出格式的处理方式、基础数据结构与算法题的实现思路以及针对易错边界条件的代码写法用来复盘自己的提交、排查WA原因或补充课堂练习。源码以单题单文件组织适合作为刷题过程中的对照材料而非直接提交的最终答案。1. POJ 基础题单不是考算法是考你有没有把判题规则当回事POJ 这套 ACM 入门题单真正让人翻车的往往不是算法难度而是读入形态、输出格式和边界条件。同一道枚举题有人三分钟写完一次 AC有人改到凌晨还在 WA差别基本都在这些“非算法”的地方。这份题单适合两类人刚接触 ACM 赛制、要过机试和课程上机的读者以及刷过一些题但一上机就掉链子的选手。拿分路径很清楚——先把三种输入形态和六类题型模板背到能默写再用数据范围反推复杂度最后照易错清单逐条自查。下面按“考什么、高频怎么考、错了怎么改”的顺序拆开讲。2. 题型地图六类基础题的占比、数据范围与判定标准基础题单看着散其实就六类外加一类“不算算法”的输入输出。真题里失分最多的不是难题是那些“一看就会、一交就 WA”的题因为它们的判定标准藏在题面最后一段和样例里而不是藏在算法里。2.1 六类题的出现频率与判分特征题类题面里的典型说法真正在考什么新手失分率输入输出与格式“多组数据”“以文件结束为终止”读入循环、行尾处理、Case 编号很高枚举与模拟“按规则依次执行”“求所有满足条件的”边界控制、状态维护高贪心“最多能选多少个”“总花费最少”排序依据、交换论证中二分“最小的最大值”“第一个满足条件的”单调性、边界收缩高搜索“最少步数”“一共有多少种走法”状态去重、剪枝中递推与简单 DP“方案数”“最大和”“路径条数”状态定义、转移顺序中数论小工具“素数”“最大公约数”“进制转换”筛法边界、整数溢出中低按题量估算输入输出与枚举模拟这两类加起来能占到基础题单的四成左右贪心、二分、搜索、递推各占一成上下数论通常是零散穿插。分数分布上的血泪经验是难度高的题不一定丢分格式题一定丢分。一道 AB 型的题写对了加法却漏了“每组输出后空一行”照样是 Presentation Error 或者直接 WA。判分标准只有一条你的输出必须和标准输出逐字节一致有些平台对行尾空格宽容但不要赌。这意味着三件事必须做到——每组数据的输出对应正确、行尾不主动加多余空格、浮点数按题目要求的位数输出。判断题面时先看样例输出最后有没有空行再决定要不要多打一个换行。2.2 用数据范围反推算法题面里最值钱的那行字题面里1 ≤ n ≤ 100000这种约束不是装饰是出题人直接把算法复杂度告诉你了。养成先抄数据范围、再选写法的习惯能省掉一半的返工。数据范围可接受的复杂度对应的常见写法n ≤ 10O(2^n)、O(n!)全排列枚举、状压搜索n ≤ 20 ~ 25O(2^n · n)状压 DP、折半枚举n ≤ 100O(n^3)三层枚举、Floyd 型最短路n ≤ 1000O(n^2)双重循环、朴素 DPn ≤ 10^5O(n log n)排序、二分、堆、前缀和n ≤ 10^7O(n)线性筛、一次扫描、差分n ≤ 10^9O(log n)、O(1)快速幂、公式、二分答案举个具体判断题面写“给出一个长度不超过 10^5 的序列多次询问区间和”如果老老实实每次循环累加是 O(n·q)q 也是 10^5 时就是 10^10 次运算必超时换成前缀和预处理 O(n)、单次询问 O(1)总运算量降到 2×10^5。同一道题写法的差别就是超时和 AC 的差别。反过来也要小心数据范围小不代表可以乱写。n ≤ 10 时用全排列没问题但如果题目里还有一层 10^5 的询问枚举就得放进预处理里而不是每次询问重跑一遍。2.3 一秒能跑多少次运算复杂度不是玄学是算得出来的老平台的评测机单核性能保守一秒大致能完成 10^7 到 10^8 次简单运算涉及除法、取模、浮点、函数调用时要往下压。面试或机试环境通常更快但按 10^7 估最保险。心算方法把循环层数乘起来。双重循环、每层 10^4就是 10^8卡在临界线上双重循环、每层 10^5是 10^10直接放弃这个写法。带 log 的写法可以放宽——sort 对 10^5 个元素大约是 1.7×10^6 次比较完全安全。递归搜索要另外算二叉递归深度 20 就是 10^6 个节点深度 30 是 10^9 个节点差别巨大所以搜索题必须剪枝或者记忆化。还有一类隐蔽的超时在循环里用strlen、s.length()、vector.size()反复求长度。字符串长度 10^5、循环 10^5 时就是 10^10。把长度提到循环外存成变量这类问题立刻消失。3. 输入输出三种读入形态和四个格式坑先拿下这 30 分算法题丢分叫技不如人格式题丢分叫冤枉。判题系统不知道你思路多漂亮它只比对字符。基础题单里三种读入形态几乎每份题解都会遇到写熟之后就是条件反射。3.1 单组、多组定长、读到文件结束三种形态第一种是单组数据读一次、算一次、输出一次最省事。第二种是多组定长题面第一行给组数 T之后跟 T 组数据。第三种是读到结束题面写“多组数据直到输入结束”没有给组数。第三种是新手的第一个坑正确写法是判断读入函数的返回值而不是判断变量值#include cstdio int main() { int a, b; // scanf 返回成功读入的变量个数读到结尾返回 EOF(-1) // 这里期望读到 2 个整数所以比较 2 while (scanf(%d%d, a, b) 2) { printf(%d\n, a b); } return 0; }这段的逻辑是只要还能完整读到两个整数就处理一次少读到一个就退出。参数上唯一要改的是比较的数字——读三个变量就写 3读字符串就写 1。两种常见写错的方式要避开while (scanf(%d%d, a, b))在读到结尾时返回 -1非零为真于是多循环一次输出一组垃圾数据while (!feof(stdin))的毛病是 feof 只在读失败之后才置位循环体内会多做一轮处理。这两种写法在本地看起来正常交上去就是多一行输出。用 Python 时对应写法是把标准输入当成可迭代对象import sys for line in sys.stdin: # 文件结束自动停止不需要额外判断 line line.strip() if not line: # 跳过空行避免 split 后解包报错 continue a, b map(int, line.split()) print(a b)strip()去掉行尾换行空行判断是保命的——有些数据的组间会夹空行不跳过就会抛 ValueError。3.2 输出格式的四个坑行尾空格、Case 编号、空行、精度第一坑是行尾空格。输出一行 n 个数常见写法是每个数后面跟一个空格最后多出一个。严格的比对会判错稳妥写法是“第一个数不加分隔符之后每个数前加”或者用标记变量控制。第二坑是 Case 编号。题目要求Case 1: 42时冒号后面有没有空格、Case 的 C 是不是大写都必须逐字照抄样例。编号从 1 开始还是从 0 开始也看样例不要凭习惯。第三坑是组间空行。有些题要求“每组输出之间空一行”意味着第一组前面不能有空行、最后一组后面也不能有。写法上是用if (cas 1) printf(\n);在输出内容前补换行而不是在每组后面无条件加。第四坑是浮点精度。题目要求保留三位小数就写printf(%.3f\n, ans)不要用cout默认的 6 位有效数字。四舍五入的误差要靠加一个极小量规避printf(%.3f\n, ans 1e-9)前提是答案非负。这个技巧在几何和期望值题里经常救命。3.3 读入提速与混用陷阱C 里cin默认和 stdio 同步读 10^5 行以上会明显变慢。两种解法一是ios::sync_with_stdio(false); cin.tie(nullptr);放在 main 开头之后不能再用 scanf二是干脆全用 scanf。混用是实打实的踩坑高发区。加了上面那行之后又用scanf读数据缓冲区不同步读进来的值是乱的。判断标准很简单一份代码里只留一套输入输出别两边都用。getline前面接cin 也有类似问题cin 遇到空格停下把换行符留在缓冲区紧接着的getline读到空串。修法是在两者之间加一句cin.ignore()。字符串题里这个坑出现频率极高读到“第一行是整数 n接下来 n 行是字符串”就该警觉。提示每道题先在纸上写清楚三件事——几组数据、怎么结束、输出里有没有 Case 和空行。写完再动手比交五次改三次快。4. 模板默写枚举、贪心、二分、搜索、递推五套可直接背的写法基础题的算法本身不复杂难在写对。下面五套模板覆盖了题单里绝大多数基础题型背到能默写、能改参数上机时就不用现推。4.1 枚举与模拟把规则翻译成循环先处理边界再处理主体枚举题的坑在边界模拟题的坑在顺序。写枚举时先问自己枚举的变量有几个、每个的范围是什么、判定条件能不能提前跳出。三重枚举以内基本可以直接写四重以上就该想别的办法。模拟题的正确姿势是“先写清楚状态有哪些”再写状态怎么变最后写什么时候结束。次序颠倒就会出现“改了一个变量忘了另一个”的情况。比如报数类题目需要维护“当前报到几”和“还剩几个人”两个量删人的时候两个量都要动。// 枚举型在 [1, n] 里找满足条件的最小整数 int answer -1; for (int x 1; x n; x) { if (check(x)) { // check 内部只做判定不改外部状态 answer x; break; // 找最小命中就退出省掉后续枚举 } }check写成独立函数是有意为之判定逻辑和枚举骨架分离改条件时只动一处也方便单独对着样例手算验证。4.2 贪心先定排序依据再用交换论证说服自己贪心题错得最多的地方不是代码是排序依据选错。判断依据能不能用标准是“任意两个相邻元素交换后不会更优”这个论证在纸上写两行就够了。以区间调度为例给出若干区间问最多能选多少个互不重叠的。正确做法是按右端点升序排依次选取左端点不小于上一个选中区间右端点的区间。// 区间调度按右端点升序能选就选 sort(seg.begin(), seg.end(), [](const pairint,int a, const pairint,int b) { return a.second b.second; // 只比右端点 }); int cnt 0, lastEnd -1; // lastEnd 初始值要小于所有左端点 for (auto s : seg) { if (s.first lastEnd) { // 当前区间与已选区间不重叠 cnt; lastEnd s.second; // 更新右边界 } }为什么按右端点而不是左端点按左端点排时第一个区间可能很长选它之后就装不下别的贪心失效按右端点排每次选的都是“结束最早、给后面留空间最多”的那个这个性质可以交换论证证明。lastEnd的初始值要选一个比所有左端点都小的数题目坐标从 0 开始时用 -1 是安全的从 1 开始时用 0 更稳。4.3 二分答案单调性是前提边界收缩是命门二分的两类写法必须分清在有序数组里找某个值和在一个答案区间里找满足条件的最值。基础题单里后者更多模板也更固定。// 求最小的满足 check(x) 为真的 x答案落在 [lo, hi] int lo 0, hi (int)1e9; while (lo hi) { int mid lo (hi - lo) / 2; // 这样写防止 lo hi 溢出 if (check(mid)) hi mid; // mid 可行答案在左半含 mid else lo mid 1; // mid 不可行答案在右半 } // 循环结束时 lo hi即为答案三个细节决定成败。mid用lo (hi - lo) / 2而不是(lo hi) / 2后者在 lo、hi 接近 10^9 时会超出 int 范围变成负数然后数组越界报的是段错误而不是 WA排查起来极其难受。收缩方式上可行时写hi mid保留 mid不可行时写lo mid 1排除 mid两者必须配套写成lo mid且mid取的是左中值就会在只剩两个元素时死循环。check函数的单调性要在纸上确认随着 x 增大判定结果必须从“全假”变成“全真”中间只有一个分界点。如果单调性不成立二分出来的结果是玄学样例能过、数据必挂。写完先手造三组数据对着跑一遍比交上去猜要快。4.4 搜索与递推BFS 求最少步递推求方案数搜索分两种用途求最少步数用广度优先求方案数或可达性用深度优先加记忆化。基础题单里网格最短路是常客。int bfs(vectorvectorint g, int sx, int sy, int tx, int ty) { int n g.size(), m g[0].size(); vectorvectorint dist(n, vectorint(m, -1)); // -1 表示未访问 queuepairint,int q; dist[sx][sy] 0; q.push({sx, sy}); int dx[4] {-1, 1, 0, 0}, dy[4] {0, 0, -1, 1}; while (!q.empty()) { auto [x, y] q.front(); q.pop(); if (x tx y ty) return dist[x][y]; // 首次弹出即最短路 for (int k 0; k 4; k) { int nx x dx[k], ny y dy[k]; if (nx 0 || nx n || ny 0 || ny m) continue; // 越界 if (g[nx][ny] 1 || dist[nx][ny] ! -1) continue; // 障碍/已访问 dist[nx][ny] dist[x][y] 1; q.push({nx, ny}); } } return -1; // 不可达 }关键点是“入队时就标记已访问”不是出队时才标记。出队标记会让同一个格子被重复入队多次10^3 × 10^3 的图上队列能涨到上百万内存和时间一起崩。dist同时兼作访问标记和距离数组省一个数组也省一次判断。递推型题目则要先把状态定义写成人话。比如“走台阶每次一步或两步问走到第 n 级有多少种走法”状态就是“走到第 i 级的方案数”转移是dp[i] dp[i-1] dp[i-2]边界是dp[1] 1, dp[2] 2。写成滚动数组可以压到一个常数空间long long f(int n) { if (n 2) return n; // 边界直接返回避免下面初始化错位 long long a 1, b 2, c 0; // a 对应 dp[i-2]b 对应 dp[i-1] for (int i 3; i n; i) { c a b; // 状态转移 a b; b c; // 滚动注意赋值顺序 } return c; }用long long是因为方案数增长很快n 到 90 左右就超 int 了。如果题目要求对 10^97 取模取模放在c a b之后、赋值之前别在滚动时漏掉。赋值顺序必须先a b再b c或者反过来写临时变量写错就变成两个变量相等样例小的时候还看不出来。4.5 数论小工具筛法、gcd、快速幂三件套数论题在基础题单里通常只考最基础的部分但边界处理很讲究。const int MAXN 1000000; bool isComp[MAXN 1]; // false 表示素数 void sieve(int n) { for (int i 2; (long long)i * i n; i) { if (isComp[i]) continue; // 从 i*i 开始标记比 i*2 少一半重复j 用 long long 防溢出 for (long long j (long long)i * i; j n; j i) isComp[j] true; } // 注意0 和 1 不是素数使用前单独排除 } long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; // 递归到 b 为 0 时 a 即答案 }i * i必须转成long long再比较i 到 46341 时 int 乘法就溢出了溢出后条件恒真循环跑到数组外面去。内层从i*i开始而不是i*2是因为更小的倍数已经被更小的素数筛过了重复标记纯属浪费。gcd的参数用 long long两个 10^9 的数做 lcm 时中间结果会超出 int。进制转换类题目的通用做法是“除基取余、逆序输出”注意 0 要单独输出负数先转正再补负号。快速幂的模板和二分同源把指数按二进制拆开底数不断平方每次乘法后取模。5. 易错点五个把 AC 改写成 WA 的失分点以下五条是基础题单里出现频率最高的失分点每一条都按“错在哪、为什么错、怎么答对”写。上机前扫一遍能省掉大量重复提交。5.1 多组数据忘了清空全局数组和计数器错在哪第一组数据输出正确第二组开始答案偏大或者凭空多出结果。为什么错数组和计数器定义在全局或函数外只在程序启动时初始化一次。多组数据共用同一块内存上一组残留的标记被当成这一组的已有状态。怎么答对把每组数据的输入写成一个函数初始化语句放在函数最前面用memset或者fill清空。更稳的办法是把数组定义在循环体内靠构造函数的默认值保证干净如果数据量大到不能用局部数组就在读入前统一清一次并在纸上记下“哪些数组是跨组共享的、哪些是每组独立的”。5.2 二分写了while (lo hi)又用lo mid错在哪程序卡死超时或者答案差 1。为什么错lo hi的循环条件是给“找某个确切值、命中就返回”的写法配的如果内部收缩写的是lo mid且区间只剩两个元素、mid又恰好等于lo那么lo永远不动循环退不出去。怎么答对两套写法只能用一套。找最值用while (lo hi)配hi mid/lo mid 1找确切值用while (lo hi)配hi mid - 1/lo mid 1且命中时直接返回。写完在纸上用区间长度 1 和 2 各模拟一遍两分钟能发现全部死循环。5.3 int 乘法溢出后再比较错在哪条件判断在数据大时行为反常小数据全对。为什么错两个 10^9 级别的 int 相乘结果超出 32 位范围符号位被改写结果变成负数或小数之后的比较、取模、下标全部错位。怎么答对看到乘法、累加、求 lcm、算面积第一反应是把参与运算的至少一个操作数转成long long写成1LL * a * b。数组下标和循环变量保持 int 不受影响。涉及 10^18 以上量级时换unsigned long long或者自己写高精度别硬撑。5.4 输入方式混用读到的值全是乱的错在哪本地跑样例正确交上去第一组数据就错甚至读到负数。为什么错ios::sync_with_stdio(false)关闭了 C 流和 C 标准库的同步之后再用scanf或printf两套缓冲区各自为政读入位置错乱。怎么答对一份代码只用一套输入输出。全 C 风格就scanf/printf全 C 风格就在 main 开头加那两行加速语句然后只用cin/cout。另外cin 之后要getline中间必须cin.ignore()否则读到的是空行。5.5 浮点输出位数不对、比较直接判等错在哪答案数值正确判题返回错误或者几何题在某个数据点上判定反了。为什么错默认输出是 6 位有效数字而不是 6 位小数大数时连整数部分都会被截断浮点数在二进制下无法精确表示a b在这种误差下几乎永远为假。怎么答对输出统一用printf(%.3f\n, ans)这种显式指定小数位的写法四舍五入的边界加一个 1e-9 的修正量。比较两个浮点数时写fabs(a - b) 1e-8判定大小关系时把 eps 加在不等号一侧。题目如果要求输出整数但中间过程是浮点最后用(int)(ans 0.5)而不是直接截断。6. 上机节奏40 分钟从读题到 AC 的时间分配表题单里的基础题单题时限通常在 1 秒、内存 64MB 到 256MB。真正决定成绩的不是会不会而是会不会在有限时间里把会的题全部拿到手。下面这张表是我自己用过多轮的分配方式适用于一道中等难度的基础题。阶段时间要做的事判断是否继续读题3 分钟抄下数据范围、输入组数、输出格式手算一遍样例样例都算不出回去重读定算法4 分钟用数据范围反推复杂度写下状态或贪心依据复杂度超标换思路写代码12 分钟先写输入输出骨架再填核心逻辑卡在语法上超过 3 分钟换写法自测8 分钟样例 三组自造数据最小、最大、边界自造数据不过先调这个静态检查5 分钟照第 5 章的清单逐条过发现一条改一条提交与善后8 分钟看返回类型WA 查逻辑TLE 查复杂度PE 查格式三次不过就换题自造数据这一步最容易被跳过也最值钱。最小值测边界有没有特判最大值测溢出和超时边界值测等号取没取对。三道题的数据往往能抓出四分之三的错误。静态检查按固定顺序走数组清空、long long、循环边界、输出格式、读入方式。这五项和具体题目无关属于每道题都要过一遍的通用项形成肌肉记忆之后检查一遍不到两分钟。注意连续三次提交同一道题还是错的先离开这道题。人在同一个思路上打转时看十遍代码也看不出问题换一道题做完再回来往往一眼就能发现。有个教训我记了很久早期做这类题单我习惯写完直接交把判题结果当调试工具用一次上机提交二十多次罚时直接把自己送走。后来强迫自己每次提交前走一遍“样例、边界、清空、溢出、格式”这五步提交次数掉到平均一点三次反而做得更快。从那以后我每次上机不管题目多简单都强制走一遍这套检查清单宁可多花两分钟也不花二十分钟找那个漏掉的memset。希望帮到你。本文还有配套的精品资源点击获取