企业官网建设流程全解析

简介：这份资料面向准备北京大学POJ在线评测、ACM算法入门与课程作业练习的学习者，汇集百余道基础与常见题目的C++参考实现，可用于对照思路、排查边界条件并复盘输入输出处理。压缩包共157个文件，其中156个cpp源码文件和1个txt说明文件，整体约59KB，体量轻便，便于按题号查找和本地编译调试。相关题目覆盖枚举、模拟、数论、动态规划、搜索、字符串与基础数据结构等入门至进阶内容，代码可作为算法实现范本，也能帮助读者理解评测平台的常见输入格式与输出要求。目前已有2654人学习下载，适合刚接触POJ、需要刷题参考或希望补齐基础算法短板的读者使用。

1. 一份散装的 OJ 基础题 AC 代码集，比题解文章更接近实战

刷 ACM 风格的基础题，真正卡人的往往不是思路，而是那个怎么也过不去的边界：多组输入忘了读到文件尾、答案明明对却败在行末多了一个空格、大数乘法用 int 一存就溢出。这份资源就是冲着这些场景来的——它不是一篇讲思路的题解文章，而是一批已经 AC 过的 OJ 基础题答案代码，按题号归档，拿到手就能编译、能对样例、能直接提交。适合两类人：刚接触在线评测、想找一份能对着跑的标准答案来核对自己代码的新手；以及想把零散的基础题代码整理成个人模板库、以后比赛前能快速翻查的老手。下面按“它长什么样、怎么跑起来、怎么改”的顺序往下拆。

2. 目录与技术栈：题号即文件名，一份能直接扔进 IDE 的工程结构

2.1 目录树：一道题一个文件夹，题号就是索引

这类答案包最容易踩的坑是“所有 cpp 堆在一个目录里”，几十道题之后完全找不到东西。这份资源的结构是按题号分目录，每题一个文件夹，主程序统一叫main.cpp，方便单独编译，也方便以后往里加样例文件和暴力解。

oj-basic-answers/ ├── 1001-add-a-b/ │ ├── main.cpp │ ├── sample.in │ └── sample.out ├── 1002-big-mul/ │ ├── main.cpp │ ├── sample.in │ └── sample.out ├── 1007-interval/ │ ├── main.cpp │ ├── sample.in │ └── sample.out ├── 1012-knapsack/ │ ├── main.cpp │ └── sample.in ├── 1018-grid-bfs/ │ ├── main.cpp │ └── sample.in └── README.md

目录名用“题号 + 一句话题意”的写法，是有意为之：题号保证唯一，题干关键词保证半年后你还认得出这是哪道题。sample.in/sample.out存的是题目页面上给的样例，作用不是给你提交，而是本地跑完拿来diff一下，确认编译和输入输出都没有问题。

提示：如果题目本身有多组测试数据，sample.in里要把多组数据整段贴进去，包括那个看起来多余的结尾空行，否则本地能过、线上挂了。

2.2 每个源文件的公共骨架：头文件与 IO 加速

打开任意一个main.cpp，前半段几乎长得一样。基础题不需要复杂工程结构，一个文件从#include到main结束，所有逻辑自包含。

#include <bits/stdc++.h> // 基础题图省事，一次带全标准库 using namespace std; int main() { // 关同步 + 解绑，cin/cout 在大量输入时性能能追平 scanf ios::sync_with_stdio(false); cin.tie(nullptr); int a, b; while (cin >> a >> b) { // 读到 EOF 自动退出，天然支持多组输入 cout << a + b << '\n'; // 用 '\n' 而不是 endl，避免反复刷新缓冲区 } return 0; }

这段骨架里有三个值得单独说的点。bits/stdc++.h不是标准头文件，是 GCC 提供的聚合头，线上评测机只要用 g++ 编译就能过，用 MSVC 或者某些严格环境的编译器会报错，本地编译不过时先换成具体头文件试试。ios::sync_with_stdio(false)关掉 C 流和 C++ 流的同步，cin.tie(nullptr)解除cin对cout的绑定，这两行是 IO 密集题能不能过时间限制的分水岭，常见做法是抄模板时顺手就带上。用'\n'不用endl，因为endl每次都会强制刷缓冲区，几十万行输出下来差距很明显。

参数上没什么可调的，唯一的开关是那两行同步设置：如果你在同一个程序里混用了scanf和cin，就绝对不能关同步，否则读入顺序会乱。我的习惯是要么全用cin/cout，要么全用scanf/printf，不混着来。

2.3 编译环境与标准选择

答案包里的代码统一按 C++17 写，编译命令固定成下面这行，写进脚本以后每题都跑一遍：

g++ -std=c++17 -O2 -Wall -Wextra -o main main.cpp

-std=c++17对齐绝大多数在线评测机现在默认或可选的语言标准；-O2打开二级优化，很多时间限制紧的题在本地不加优化跑得慢，加了才接近线上表现；-Wall -Wextra把警告全打开，像“变量未初始化”“有符号和无符号比较”这类警告，往往直接对应线上的 WA 或 RE，本地看到就别忽略。

最后一行那个-fsanitize=address是排查 RE 的后悔药，加上之后数组越界会直接打印出越界位置和调用栈。代价是程序变慢、占用内存变大，所以只在本地调试时开，提交前必须去掉这些调试参数，不然线上要么超时要么编译不过。

3. 核心代码拆解：五类基础题的通用写法

3.1 多组输入：EOF 循环是最高频的失分点

基础题里最典型的输入形态是“不知道有多少组，读到文件结束”。C 风格和 C++ 风格两种写法都对，但要选一种用到底。

// C 风格：scanf 的返回值是成功读入的变量个数，读到文件尾返回 EOF(-1) int n; while (scanf("%d", &n) == 1) { printf("%d\n", n * 2); } // C++ 风格：cin 在流状态失效时布尔值为 false，写法更短 int m; while (cin >> m) { cout << m * 2 << '\n'; }

逻辑上，scanf("%d", &n) == 1的判据是“成功读到了 1 个整数”，比!= EOF更严谨——如果输入里混进了非数字字符，scanf会返回 0 而不是 EOF，用!= EOF判断就会陷入死循环。while (cin >> m)则是利用流对象重载的bool转换，读到 EOF 或格式错误都会退出。参数上要注意，scanf必须传地址&n，漏了&是新手最常见的崩溃来源，而且编译器不一定报错。

还有一种变体是“第一行给组数 T，接下来 T 组”，这种反而简单，cin >> T; while (T--) { ... }就行，别和 EOF 循环搞混。我见过把while (T--)写成while (--T)的，第一组数据直接被吃掉。

3.2 高精度运算：把 int 存不下的数当字符串处理

大数题是基础题里的分水岭，思路不复杂，但实现细节多。以最基础的大数加法为例，核心是倒序存、逐位加、处理进位。

#include <bits/stdc++.h> using namespace std; string addBig(string a, string b) { // 反转后从低位开始对齐，长度不同时短的那边补 '0' reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); if (a.size() < b.size()) swap(a, b); string res; int carry = 0; for (size_t i = 0; i < a.size(); i++) { int da = a[i] - '0'; int db = (i < b.size()) ? b[i] - '0' : 0; int sum = da + db + carry; res.push_back(char('0' + sum % 10)); // 当前位 carry = sum / 10; // 进位留到下一位 } if (carry) res.push_back('1'); // 最高位还有进位，别丢 reverse(res.begin(), res.end()); return res; }

逻辑分三步：反转让字符串下标和数位权重对齐，逐位相加时用i < b.size()判断短的那个数是不是已经取完，最后把残留的进位补成最高位。参数上最容易翻车的是最后那个if (carry)，比如99 + 1，循环走完还留一个进位，漏掉这行结果就变成00。

乘法是同样的套路，内外两层循环模拟竖式，res[i + j]累加，最后统一从低位处理进位：

string mulBig(string a, string b) { if (a == "0" || b == "0") return "0"; vector<int> res(a.size() + b.size(), 0); for (int i = a.size() - 1; i >= 0; i--) for (int j = b.size() - 1; j >= 0; j--) { int mul = (a[i] - '0') * (b[j] - '0'); int p1 = i + j, p2 = i + j + 1; // 乘积落在两个位置 int sum = mul + res[p2]; res[p2] = sum % 10; res[p1] += sum / 10; } // 跳过前导零 string s; for (int v : res) if (!(s.empty() && v == 0)) s.push_back(char('0' + v)); return s.empty() ? "0" : s; }

p1 / p2这个下标分配是乘法实现的核心：i + j + 1是当前乘积的个位落点，i + j承接进位。用vector<int>而不是string存中间结果，是因为中间某一位可能超过 9，先存成整数最后统一进位，比边算边处理进位清晰得多。

3.3 贪心与排序：区间调度为什么按右端点排

区间调度是贪心入门题的标准形态：给一堆区间，选出最多互不重叠的。答案是按右端点升序，能选就选。

struct Interval { int l, r; }; int maxNonOverlap(vector<Interval>& v) { sort(v.begin(), v.end(), [](const Interval& a, const Interval& b) { return a.r < b.r; // 关键：按右端点排序，不是左端点 }); int cnt = 0, lastEnd = INT_MIN; for (auto& it : v) { if (it.l >= lastEnd) { // 与前一个选中区间不重叠 cnt++; lastEnd = it.r; } } return cnt; }

逻辑上，按右端点排序保证了每次选择都让“已占用空间的结束点尽量靠左”，给后面留出最大余量，这是贪心正确性的直接来源。如果按左端点排，遇到一个从很早就开始、跨度极长的区间，会白白占掉名额。参数上要注意it.l >= lastEnd里的等号：题目说“端点可以相接”就带等号，说“不能接触”就去掉等号，这一处等号错了就是 WA on test 2 这种很难受的挂法。

3.4 一维滚动数组的 0-1 背包

0-1 背包的二维写法直观，但基础题的容量往往开得大，必须压成一维。

int knapsack(int W, vector<int>& w, vector<int>& v) { vector<int> dp(W + 1, 0); for (size_t i = 0; i < w.size(); i++) { // 关键：容量必须从大到小遍历，保证每件物品只用一次 for (int j = W; j >= w[i]; j--) { dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } } return dp[W]; }

倒序遍历是这段代码的全部精髓。正序遍历时，dp[j - w[i]]可能刚被本轮更新过，等于同一件物品被拿了两次，那就变成完全背包了。dp数组大小开W + 1是为了下标能直接对应容量，dp[0] = 0是初始状态，其余默认 0 在“求最大价值、可以不装满”的场景下是正确的；如果题目要求“恰好装满”，初始值就要设成负无穷，只在dp[0]处设 0。

3.5 网格 BFS 最短路：方向数组与访问标记

网格类搜索题的模板高度固定，写熟了几乎可以盲打。

int bfs(vector<vector<int>>& grid, int sr, int sc, int er, int ec) { int n = grid.size(), m = grid[0].size(); const int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; vector<vector<int>> dist(n, vector<int>(m, -1)); // -1 表示未访问 queue<pair<int,int>> q; dist[sr][sc] = 0; q.push({sr, sc}); while (!q.empty()) { auto [x, y] = q.front(); q.pop(); if (x == er && y == ec) return dist[x][y]; // 第一次到达即最短 for (auto& d : dir) { int nx = x + d[0], ny = y + d[1]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 越界 if (grid[nx][ny] == 1) continue; // 障碍 if (dist[nx][ny] != -1) continue; // 已访问 dist[nx][ny] = dist[x][y] + 1; q.push({nx, ny}); } } return -1; // 不可达 }

用dist数组同时承担“访问标记”和“距离记录”两个职责，比单开一个visited数组省事，也避免了两处状态不同步。方向数组定义成const int dir[4][2]放在栈上，编译器能完全展开；如果题目是八方向就连通，改成dir[8][2]补上四个对角即可。越界判断要写在访问判断之前，顺序反了虽然结果不错，但多了一次越界下标访问，在开了地址检查的环境里会直接报错。

4. 本地跑通：编译、样例比对与对拍验证

4.1 单题编译与样例比对

进入某一题的目录，编译、喂样例、比对输出，三步就能确认代码是否可用：

cd 1002-big-mul g++ -std=c++17 -O2 -Wall -o main main.cpp ./main < sample.in > my.out diff -w my.out sample.out && echo "样例通过"

<把样例文件喂给标准输入，>把输出重定向到文件，diff -w里的-w表示忽略所有空白字符差异，这一条很重要：很多题目样例输出里有行末空格，手抄进sample.out时对不齐，不加-w会一直报差异。&&保证只有diff返回成功才打印提示。

如果diff输出了具体差异行，先别改代码，回头看一眼输出的换行数量——多一行或少一行空行是最常见的格式问题。

4.2 批量编译脚本：几十道题一次过一遍

题目多了以后一道一道手编不现实，写个脚本扫一遍，重点是区分编译错误和样例不通过。

#!/usr/bin/env bash # 放在答案包根目录，一次性编译并测试所有题目 set -u fail=0 for dir in */ ; do [ -f "$dir/main.cpp" ] || continue echo "==> $dir" if ! g++ -std=c++17 -O2 -Wall -o "$dir/main" "$dir/main.cpp" 2> "$dir/build.log"; then echo " 编译失败，详情见 $dir/build.log" fail=$((fail+1)); continue fi if [ -f "$dir/sample.in" ] && [ -f "$dir/sample.out" ]; then "$dir/main" < "$dir/sample.in" > "$dir/my.out" if diff -wq "$dir/my.out" "$dir/sample.out" > /dev/null; then echo " 样例通过" else echo " 样例不匹配"; fail=$((fail+1)) fi fi done echo "失败数：$fail"

脚本里有几个细节值得说。set -u让未定义变量直接报错退出，避免路径拼接出空串后误删文件；编译错误重定向到各题目录下的build.log，一次跑完能拿到全部错误而不是第一个就中断；diff -wq的-q只关心“是否不同”，输出更干净。参数上如果你习惯用printf，把-w换成-b（忽略空格数量变化）也行，具体看题目对空格的容忍度。

4.3 对拍：用暴力解验证正解

样例过了不代表对，尤其是贪心、DP 这类“样例太弱”的题。对拍是血泪经验里最值钱的一招：写一个必然正确但很慢的暴力解，随机生成小数据，两边的输出比对。

# 对拍脚本：随机造小数据，对比正解 brute 两份输出 import random, subprocess, sys for case in range(500): n = random.randint(1, 8) # 数据规模必须小，暴力才跑得动 arr = [random.randint(-20, 20) for _ in range(n)] data = f"{n}\n" + " ".join(map(str, arr)) + "\n" out1 = subprocess.run(["./main"], input=data, capture_output=True, text=True).stdout out2 = subprocess.run(["./brute"], input=data, capture_output=True, text=True).stdout if out1.split() != out2.split(): # 按 token 比对，忽略空白差异 print(f"第 {case} 组不一致：\n输入：{data}\n正解：{out1}\n暴力：{out2}") sys.exit(1) print("500 组全部一致")

random.randint的范围要故意包含负数、零、边界值，很多 bug 只在负数或者全相等的数据上暴露。out1.split() != out2.split()是把输出按空白切成 token 再比，比逐字符比对宽松，避免格式细节干扰真正的逻辑错误。跑够 500 组还没差异，这道题基本可以放心交了。

5. 避坑与排查：WA、TLE、RE 的五条高频现场

现象：本地样例全过，提交 WA on test 1。原因八成是多组输入没读全，只处理了第一组就退出。题目描述里“多组数据”“输入包含若干组”这种措辞容易被忽略。解决是把cin >> n外面套一层while (cin >> n)，并且把每组之间的空行、初始化清空检查一遍，全局数组记得每组开始前memset。

现象：本地瞬间出结果，提交 TLE。常见原因有三个：cin没关同步、循环里用了endl、以及把O(n²)的暴力当正解交上去了。前两个按 2.2 的骨架改掉，第三个老实换算法。还有一种隐蔽情况是函数传参传了vector的拷贝而不是const&，几万次调用下来开销惊人。解决顺序是先关同步，再查算法复杂度，最后才怀疑评测机。

现象：运行直接 RE，没有任何输出。数组开小了是头号嫌疑，题目说n ≤ 10000你开了int a[1000]；其次是递归层数过深爆栈，网格 DFS 在 1000×1000 上递归必炸。解决是给数组多留 5 到 10 个余量（下标从 1 开始用的话），大规模搜索改成 BFS 或者手写栈。本地复现时加-fsanitize=address，越界位置会直接打出来。

现象：输出看着一模一样，但还是 WA。格式问题。有的题要求“每组数据后输出一个空行”，有的命令“最后一个数字后不能有空格”，还有的用printf("%d ", x)循环完多打了一个空格。解决是严格控制分隔符的位置，常见写法是第一个元素单独输出，后续元素用printf(" %d", x)，这样行末不会残留空格。

现象：大数题答案前几位对、后面全错。整数溢出。int最大约 21 亿，两个 10 万相乘直接爆，long long在累加求和、阶乘题里同样会爆。解决是估算量级后换long long，再往上就得上 3.2 的高精度字符串。另外负数取模在 C++ 里结果符号跟被除数走，题目要求非负余数时需要手动(a % m + m) % m。

6. 二次开发：把这些散文件改造成自己的模板库

答案包直接当模板用，用久了会散：找一道“高精度乘法”要翻半天目录。我一般做三件事把它变成能长期复用的东西。

第一件是按知识点重构目录，而不是按题号。建立math/、dp/、graph/、greedy/、string/五个一级目录，原来的题号目录整体挪进去，同时在根目录维护一份INDEX.md，每条记录写成“知识点 → 文件路径 → 原题号 → 复杂度”。这张表不写长，一行一条，半年后翻起来比任何注释都快。改完之后原来的题号信息没丢，查旧题和新题两条路都通。

第二件是把 4.2 的批量脚本升级成带索引生成的版本。脚本除了编译测试，还顺手扫每个main.cpp的第一行注释，把“知识点标签”抓出来追加到INDEX.md。约定每个文件第一行写// tag: dp,knapsack，这样新增题目时只要写这一行，索引自动更新，不需要手动维护表格。这条约定比任何文档规范都管用，因为它把“维护”这件事的成本降到了写一行注释。

第三件是给模板加可复用性。答案代码是为了 AC 写的，函数都嵌在main里，想直接调用得复制粘贴。我的做法是把 3.2 到 3.5 那几个函数抽到tpl/bigint.hpp、tpl/graph.hpp里，做成头文件，主程序只#include再调用。抽的时候把using namespace std从全局挪进函数内部或者干脆用std::前缀，否则一旦和别人的代码混编就是命名冲突。抽完拿 4.3 的对拍脚本回归一遍，确认重构没改行为。

再补一个容易忽略的点：给每道题记录“失败过的原因”。我会在文件末尾写一行// WA: 多组输入没读EOF / TLE: 用endl，这行注释比代码本身更有价值，下次遇到同类题第一眼就能看到当初在哪翻车。

从那以后我每次整理这类答案包，都强制走一遍“编译脚本 + 对拍 + 索引更新”的完整流程，一步不省。散文件谁都会存，能一键验证、一眼查到知识点的才叫自己的库。希望帮到你。

本文还有配套的精品资源，点击获取