简介杭州电子科技大学在线OJ平台10001099号题目的C/C题解合集按难度递增收录约百道经典编程题适合算法竞赛入门者、刷题练习者及备考复试的上机考生。压缩包共90个文件以源代码为主62个cpp和16个c分别对应各题的主干实现少量Visual C工程辅助文件dsp、dsw、pdb等可用于重建或调试整包约1.1MB下载后即可对照阅读。代码均已调试通过题目场景覆盖基础数学、高精度运算、排序查找、图论、动态规划、搜索回溯等常见考点部分题目还附有不同写法或优化版本如1003的多个版本便于比较不同算法的时间与空间开销。全包已有1839人浏览学习是一份紧凑实用的OJ题目代码参考能帮助读者快速理解题意对应的算法设计并借鉴高效的C/C实现技巧尤其适合在遇到同类题时快速定位思路与代码模板。1. 一个让人直呼“原来AC代码长这样”的OJ题解包1000-1099全收集你是不是也遇到过这种场景刷OJ卡在某道题看讨论区里要么是一句“这题很简单”要么是毫无营养的“同求”翻遍博客和论坛最后在某台旧电脑的角落找到一个压缩包里面整整齐齐摆着从1000到1099所有题目的AC代码。拿到这份代码包时我第一反应是“终于有救了”。它把某个经典高校OJ前一百道题的通过代码全收在一个目录里每题一个文件复制粘贴就能提交。对算法入门者来说这是答案之书对备赛选手来说这是题库地图对想研究OJ判题机制的人而言这又是一套干净的样例数据集。这篇笔记我就按工程视角把它从头拆到尾告诉你这些代码怎么跑、怎么改、怎么避坑。2. 技术栈与工程布局这包代码到底怎么组织2.1 语言与编译环境C/C为主少量Java打开代码包扫一遍文件后缀绝大多数是 .c 和 .cpp少数几题是 .java。C/C 的占比在九成以上这也符合这个OJ前一百题的定位绝大多数题用把 scanf、printf 学到滚瓜烂熟就能过。代码里没有看到 C11 或者 C17 的新特性基本都是 C89 风格到 C99 之间少量用了 STL 的 sort、queue、string。这说明这个OJ的编译器版本比较保守G 4.8 左右就能兼容。我一般看到这种代码包会默认在本地用 gcc 8 以上的环境都能编译过。如果遇到老代码报错多半是 gets 函数被编译器移除了后面避坑章会专门说。Java 那几题是题目强制要求处理大数时用的比如大数加法、大数运算C/C 写起来太痛苦直接用 Java 的 BigInteger 类反而省事。要注意的是OJ 提交 Java 时类名必须是 Main并且不能带 package 声明否则直接编译错误。包里这些 Java 文件都遵守了这条潜规则。还有几个文件是 C 和 C 混合风格的比如在 .c 文件里写了// 注释这在老式编译器的 C89 标准下会报错但现代编译器默认允许所以也能过。读这些代码时要习惯这种不统一的风格。2.2 目录结构按题号命名每题独立文件代码包的目录结构非常直接没有层层嵌套所有代码文件都在根目录下。命名规则是“题号扩展名”比如 1000.c、1001.cpp、1010.java。少部分文件会在题号后面加下划线加小写字母比如 1003_b.cpp一般是对同一题的第二种解法通常是暴力版和优化版并存。我建议你优先读不带后缀的那个文件那通常是最终AC且风格最稳的版本。文件示例语言题号说明1000.cC1000AB 基础多组输入1003.cppC1003最大子段和动态规划1005.cppC1005数列规律循环节1010.cppC1010迷宫搜索DFS剪枝1015.javaJava1015大数/组合类题目每个文件内部都有几行注释注释里一般会写题目链接、核心思路和提交时间。不过这些注释不是规范格式有的写得多有的就一句“水题”属于典型的人工整理痕迹。你在做二次开发时可以把这些注释统一成自己的模板。另外包里没有 readme也没有说明文档文件之间的关联完全靠题号衔接。这种“裸代码”风格反而更适合拿来当练习题集因为不会被别人的思路说明先入为主。2.3 输入输出约定为什么都要用 scanf/printf刷过OJ的人都知道输入输出格式不对代码再对也是WA。这份代码包里几乎所有C/C代码都用了 scanf 和 printf只有极少数用了 cin 和 cout并且还加了ios::sync_with_stdio(false)。原因很简单这个OJ的数据量尤其是1000-1099区间的题目很多是多组输入用 cin 不关同步的话性能差距可能到十倍以上。在基础题阶段频繁的 I/O 操作还没显现但到了后面的搜索和动态规划题输入数据一大scanf/printf 就是求稳的选择。代码包里的输入模式主要有两种一种是读一个数就处理一个数另一种是循环读取直到 EOF 或者遇到结束标志。比如读 a、b 直到文件末尾标准写法是while (scanf(%d%d, a, b) ! EOF)遇到以 0 0 结尾的多组数据则用while (scanf(%d%d, a, b) (a || b))。这些写法在后面的题目中反复出现可以说是这个代码包的主旋律。把这一条看懂了后面读代码基本没有障碍。还有一点值得注意所有输出都以\n结尾不额外输出空格因为OJ的评测是逐字节对比多一点空白就会判WA。3. 核心代码拆解从入门题到剪枝套路这一章挑五道有代表性的题1000、1003、1005、1009、1010分别对应输入输出、动态规划、找规律、贪心、搜索剪枝。这五种题型几乎覆盖了前一百题的大部分套路。每道题我都把AC代码贴出来注释写清楚哪一行在干什么看完你就能明白这类题下次该怎么写。3.1 1000 AB多组输入的标准写法1000题是绝大多数人打开这个OJ的第一道题也是代码包里的第一个文件。题目没有任何技巧就是让程序反复读两个整数输出它们的和直到文件结束。这道题真正的考点是你能不能理解什么叫“多组输入”。#include stdio.h int main() { int a, b; while (scanf(%d %d, a, b) ! EOF) { printf(%d\n, a b); } return 0; }这里 while 循环里的 scanf 每成功返回一次就会把 a 和 b 覆盖为新的值。scanf 的返回值是成功匹配并赋值的参数个数这里是 2当文件读完时返回 EOF即 -1循环退出。如果你写成while (scanf(...))或者for(;;)在本机跑或许能过但在 OJ 上很容易在“读取到文件末尾”的边界上翻车。顺便说一句printf 的\n不能省OJ 测评是逐字节对比输出差一个换行都是 WA。这个代码虽然简单但它的结构是后面所有多组输入题的基础建议你背下来。3.2 1003 Max Sum最大子段和的动态规划1003 题要求在一串整数里找一段连续子序列让它们的和最大并且输出这段子序列的起点和终点下标。这是动态规划里的经典题但代码包里这份写法更接近贪心扫描不建数组边读边更新。核心思想是以当前位置结尾的最大和要么是当前数本身要么是前一个位置的最大和加上当前数。#include stdio.h int main() { int T, n, i, j; scanf(%d, T); for (i 1; i T; i) { scanf(%d, n); int num, sum 0, max -1000000, start 1, end 1, temp 1; for (j 1; j n; j) { scanf(%d, num); sum num; if (sum max) { max sum; start temp; end j; } if (sum 0) { sum 0; temp j 1; } } if (i 1) printf(\n); printf(Case %d:\n%d %d %d\n, i, max, start, end); } return 0; }最关键的是 max 初始化为一个非常小的负数而不是 0因为序列可能全是负数如果 max 初值是 0就会导致答案变成 0 或者选错位置。sum 一旦小于 0 就重置为 0并让临时起点跳到下一个位置这就是“负子序列对后续贡献只会更差”的贪心剪枝。本题输出格式很刁钻相邻两个 Case 之间要空一行但最后一个 Case 后面不能有多余空行所以代码里用if (i 1)来控制换行。这种输出格式陷阱在前一百题里出现频率很高后面避坑章还会提到。3.3 1005 Number Sequence找循环节别无脑模拟1005 题给了一个递推公式 f(1)1, f(2)1, f(n) (A * f(n-1) B * f(n-2)) % 7然后让你输出 f(n)其中 n 最大可以到一亿。如果直接递归或循环绝对超时。正确做法是发现 f(n) 只有模 7 的结果取值在 0 到 6 之间那么两个连续的数可以组合出 49 种状态所以最多 49 项必然进入循环。#include stdio.h int main() { int A, B, n; while (scanf(%d %d %d, A, B, n) (A || B || n)) { int f[50] {0, 1, 1}; for (int i 3; i 50; i) { f[i] (A * f[i-1] B * f[i-2]) % 7; } printf(%d\n, f[n % 48]); } return 0; }这里用了 n % 48 而不是 n % 49是因为 f(0) 被占位实际循环节长度在大部分情况下是 48这是网上流传的标准写法AC 没问题。严格证明循环节可以写但对刷题来说记住这个技巧就够了。要注意读入的结束条件是 A、B、n 同时为 0所以判断条件是(A || B || n)等价于三个数不全为 0。如果你写成(a ! 0 b ! 0 n ! 0)遇到某个数为 0 但其它不为 0 的情况就会提前退出导致错误。这个“结束标志”的坑在 1006、1014 等题目里也会遇到。3.4 1009 FatMouse Trade贪心思想入门1009 题是贪心算法的经典入门题你有 m 磅猫粮每个房间可以用一定比例的猫粮换到 JavaBean每个房间的回报率不一样求最大收益。核心思路是每次优先换“性价比”最高的房间即单位猫粮能换到的 JavaBean 最多的那个房间。#include stdio.h #include stdlib.h typedef struct { double jb, food, rate; } Room; int cmp(const void *a, const void *b) { Room *x (Room *)a; Room *y (Room *)b; if (x-rate y-rate) return 1; if (x-rate y-rate) return -1; return 0; } int main() { int m, n; while (scanf(%d %d, m, n) ! EOF (m ! -1 || n ! -1)) { Room r[1005]; for (int i 0; i n; i) { scanf(%lf %lf, r[i].jb, r[i].food); r[i].rate r[i].jb / r[i].food; } qsort(r, n, sizeof(Room), cmp); double ans 0; for (int i 0; i n m 0; i) { if (m r[i].food) { ans r[i].jb; m - r[i].food; } else { ans m * r[i].rate; m 0; } } printf(%.3lf\n, ans); } return 0; }这个代码的关键是定义了 Room 结构体来存每个房间的 JavaBean 数量、猫粮成本和性价比之后用 qsort 按性价比降序排序。注意 cmp 函数里返回正负号的写法因为 qsort 的排序规则是返回负数代表前小后大这里我们想要的是降序所以当 x-rate y-rate 时返回 1。贪心过程里先尝试把整个房间换完如果剩余的猫粮不够就按比例兑换剩余的部分。这种“部分背包问题”的解法是后面很多贪心题的原型。输出保留三位小数用 %.3lf 就行。3.5 1010 Tempter of the BoneDFS 奇偶剪枝1010 题是一个迷宫的搜索题要求在给定时间 T 恰好到达出口不能早也不能晚。代码包里这份解法用的是 DFS 加剪枝没有用 BFS因为要求“恰好在第 T 步到达”BFS 只能求最短路径不适用于这个场景。#include stdio.h #include stdlib.h char map[10][10]; int N, M, T, si, sj, di, dj, ok; int dx[4] {1, -1, 0, 0}; int dy[4] {0, 0, 1, -1}; void dfs(int x, int y, int t) { if (ok) return; if (t T) return; if (x di y dj t T) { ok 1; return; } // 奇偶剪枝剩余步数和剩余时间必须同奇偶 int dist abs(x - di) abs(y - dj); if (dist T - t || ((dist T - t) 1)) return; map[x][y] X; for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; if (nx 0 nx N ny 0 ny M map[nx][ny] ! X) { dfs(nx, ny, t 1); } } map[x][y] .; // 回溯 } int main() { while (scanf(%d %d %d, N, M, T) (N || M || T)) { int wall 0; ok 0; for (int i 0; i N; i) { scanf(%s, map[i]); for (int j 0; j M; j) { if (map[i][j] S) { si i; sj j; } if (map[i][j] D) { di i; dj j; } if (map[i][j] X) wall; } } if (N * M - wall T) { printf(NO\n); continue; } dfs(si, sj, 0); printf(ok ? YES\n : NO\n); } return 0; }这里的 dfs 参数 t 代表已经走的时间每进入相邻格就加 1。奇偶剪枝的原理是在没有障碍的网格里从 (x,y) 到 (di,dj) 的最短距离是曼哈顿距离 dist如果 dist 大于剩余时间直接不可能又因为每绕一步都会让路径长度增加 2所以剩余时间减剩余步数必须是偶数才能到达。map[x][y] X 是为了防止在递归中绕回原地但 return 之前必须改回 .这就是回溯。主函数里还做了一次粗剪枝如果可走的格子数小于等于 T说明走得再慢也没办法刚好到达直接输出 NO。这一整套写法是前一百题里所有 DFS 题的模板后面遇到类似题直接套。4. 避坑指南OJ提交最常见的五个翻车现场读这包代码的时候我顺带把容易踩的坑都标记了一遍。这些坑不是代码包本身的问题而是所有刷OJ的人都会摔的地方。下面五条按“现象→原因→解决”写都是真实会发生的。4.1 数组开小RE和WA的罪魁现象代码在本机能跑交上去返回 Runtime Error或者偶尔 WA。原因题目给定的最大数据量是 100000你只开了 10000 的数组越界写坏内存。解决养成把数组开大一点的习惯比如int a[100005]而不是a[100000]留出余量同时注意 for 循环里用 in 时下标 a[n] 也要有地方放。这个OJ的前一百题里有多道题会在边界处给你惊喜最稳妥的办法是一律多开 5 到 10 个元素。4.2 多组数据的EOF循环写错现象本地跑样例全对提交后输出比标准答案少一截或者死循环。原因把while (scanf(%d, n) ! EOF)写成了while (scanf(%d, n))当输入结束时 scanf 返回 -1-1 在布尔表达式中为真循环不会停。解决永远用! EOF判断如果遇到以特殊值结束的题目用把结束条件写完整。比如第 1014 题要求读到 0 0 结束就不可以直接用 EOF而要先读入再判断。4.3 输出格式多空行、少空格、大小写现象答案数字全对但 Presentation Error 或 WA。原因题目要求每个 Case 之间空一行末尾不能多空行或者要求输出Case 1:而代码里写成Case 1:后面少个冒号。解决先把输出复制到记事本肉眼检查行尾和空行用 diff 工具对比样例输出多一个空格都算错。代码包里 1003 和 1006 这类题都在格式上带坑我一般会在写完代码后先跑样例再用diff output.txt sample.txt逐字节对比。4.4 递归超时没有剪枝的搜索是灾难现象TLE或者测试数据一大直接卡死。原因DFS 里没有加剪枝把整棵树都遍历了一遍指数级复杂度。解决像 1010 那样加奇偶剪枝和可达性剪枝能用迭代别递归能用 DP 别 DFS。本质上是先估算状态数量再决定要不要优化。前一百题里搜索题不多但每一道都值得用剪枝思维去写哪怕数据量小也把递归边界写清楚不要抱着侥幸心理。4.5 全局变量和局部变量同名现象一份代码在本机AC交上去 WA反复检查逻辑找不到错。原因主函数里定义了 int n全局又有一个 int n局部变量把全局盖住了某个函数间接访问到了错误的值。解决把全局变量统一加前缀比如 g_n、g_ans或者在主函数里避免声明与全局同名的变量。这包代码里偶见这种写法读完你会发现它和正确版本只有一行之隔。我的习惯是全局变量全部用名字首字母大写比如 Ans、Map、Step这样永远不会撞车。5. 二次开发指南把这包题解变成自己的刷题引擎代码包拿到手除了直接交题还能做不少事。我一般会把这包代码当成一个“离线题库”做三件事批量本地评测、统一代码头、按知识点检索。5.1 批量本地评测循环编译跑样例import os import subprocess for i in range(1000, 1100): cpp f{i}.cpp exe fbin/{i} if not os.path.exists(cpp): continue subprocess.run([g, cpp, -o, exe], checkFalse) with open(finput/{i}.txt, r) as f: out subprocess.run([exe], stdinf, capture_outputTrue, textTrue) with open(foutput/{i}.txt, w) as f: f.write(out.stdout)脚本先判断文件是否存在然后编译链接再把预先放好的 input 文件喂给程序把输出写到 output 目录。这样一百题可以一键跑完遇到编译失败或者运行异常就能立刻定位到题号。如果你没有每个题的输入数据也可以自己构造边界数据比如最大 n、全负数、全零。注意checkFalse是必需的否则某个文件编译报错时脚本会直接抛异常中断。5.2 统一代码风格给每个文件加头注释一百个文件直接放进工程很乱我会用脚本在每个文件头部插入一份模板包含题号、时间、思路、复杂度。这样后续检索和复习时扫一眼就知道这题在考什么。这一步也能帮我快速挑出“水题”和“硬骨头”比如注释里写着“规律题”的 1005和写着“DFS”的 1010复习优先级完全不同。加头注释的脚本很简单按行读取原文件在开头插入模板字符串再写回即可。5.3 改造思路做一个标签检索伪OJ如果你想要一份更好用的题库可以把这包代码的文件映射成一张表每一列是题号、标签、难度、代码路径。标签可以从代码内容里猜——出现递归调用写搜索出现 dp 写动态规划出现 while scanf 写模拟。最后写个几十行的 HTML 页面就能形成一个本地浏览器可查的迷你题目索引。再进一步配合你本地写的评测脚本就成了一个可以刷的“伪OJ”。从那以后我每次拿到题解包都强制自己先跑一遍批量编译再按上面的方式打标签。这样做的好处是过段时间重新翻包不会被一百个文件吓到。希望帮到你。本文还有配套的精品资源点击获取