简介2021南信大lev o j部分参考答案是一份面向南信大编程竞赛平台LEVOJ用户的算法题解集合。集合中收录了2021年平台部分典型题目的解题思路与参考实现覆盖字符串处理、动态规划、图论最短路与最小生成树、数论等算法方向同时结合题目总结了数组、链表、树、图、栈、队列等数据结构的运用并给出排序、查找、递归、回溯等常用算法的时间复杂度分析与适用场景说明。资源包以zip格式打包约12KB下载后即可直接阅读。目前已有3139人学习浏览适合需要备考算法竞赛、强化编程能力或系统复习数据结构与算法的在校学生和自学者。通过学习这些参考答案读者不仅能对照题目验证自己的解法还能借鉴其中的思考方式与代码风格掌握将实际问题抽象为计算机模型的方法对提升竞赛成绩和日常编程能力均有帮助。1. 别人给的参考答案为什么你复制过去还是判错如果你正在搜“2021年某高校LEV OJ部分参考答案”大概率是两种情况要么OJ作业卡在某个测试点过不去要么期末复习想快速过一遍往年题。网上流传的参考答案大多是别人提交过的代码直接复制过去能一次AC的其实不多——有的本地能过提交就WA有的输入输出约定不对有的甚至编译都过不了。参考答案只是一段代码而判题系统真正检查的是完整的“读入-计算-输出”流程题目的隐藏约定、运行环境、边界数据才是能不能过AC的关键。这里按2021年前后这批OJ题目常见的考法把判题规则、高频题型、易错点和验证手段拆开讲目标是让你不仅能看懂参考答案还能自己写出能AC的版本。适合刚学C/C、被OJ格式折磨到崩溃的学习者也适合想稳定AC效率的同学。2. 看懂LEV OJ的黑匣子判题规则与本地复现方法2.1 判题系统到底在看什么编译、运行、比对输出很多同学第一次交题看到WA就以为是算法错了其实是没搞懂OJ的判题流程。判题系统拿到你提交的源码后依次做三件事在隔离环境里编译源码、用一组预置好的输入数据运行编译产物、再把程序输出和标准答案逐字符比对。全程不会看你代码风格也不会关心中间变量只看最终落到stdout上的内容。所以经常出现“参考答案缩进乱七八糟也能AC你抄规范了反而WA”的现象原因就在输出格式或运行环境这些看不见的地方。本地调试常见做法是先把编译命令固定下来。下面这组命令是我平时用的gcc -O2 -Wall -o main main.c -lm g -O2 -Wall -o main main.cpp参数说明-O2表示开优化OJ判题时一般也会开优化本地用-O0调试出来的性能和数据行为可能和OJ不一致-Wall用来提示警告能提前发现未初始化变量、比较类型不匹配这类低级问题-lm是链接数学库只要用了sqrt、pow这类函数就必须加C里一般不需要但加上不亏。如果你的OJ提供的是比较新的编译器标准而本地默认标准较旧C11的lambda、auto等语法可能本地编译失败这时候可以加-stdc11或-stdc17再编译。除了编译你还要提前看题目的时间和内存限制。OJ常见的时间限制是1秒内存从几十MB到256MB都有。粗略估算1e7的运算量在C/C里大约0.1秒级别但Python会慢几十倍1e9的运算量不管什么语言都在超时边缘必须换思路。很多人代码逻辑没错却因为用了两层循环嵌套在n1e5的数据上跑稳稳吃TLE。这里补一张判题返回状态表方便你对照返回状态含义常见原因AC答案正确无WA答案错误算法错、边界错、输出格式错PE输出格式错误多余空格、缺换行TLE运行超时复杂度过高、死循环、IO过慢MLE内存超限大数组过多、递归栈过深RE运行时错误数组越界、除零、栈溢出CE编译错误语法错、缺头文件、语言标准不符2.2 输入输出的三个隐性约定EOF、T组、行末空格第一类最容易踩的是EOF和T组的区别。这类题的题干通常有两套说法如果写“输入包含多组测试数据每组一行”那一般是读到文件结束就停标准写法是while(scanf(...) ! EOF)如果写“第一行为正整数T接下来是T组数据”那要先读T再循环。二者写反会有完全不同的表现该读T的你写成EOF循环第一次scanf读到T就结束了后面的数据全没读该读EOF的你写成T循环本地测试一组能过数据一多就只处理了第一组。第二类约定是分隔符。scanf读数字时自动跳过空格和换行所以输入是“1 2\n3 4\n”还是“1\n2\n3\n4\n”都没关系只要变量个数对。但如果题目要求读的是字符串换行和空格就会变成敏感内容读的时候要明确读的是“空格分隔的单词”还是“整行文本”。最常见的错误是想用scanf(%s)读含空格的整行结果只读到第一个单词。第三类约定是输出。OJ对比输出时空格、换行都是字符多一个空格或少一个都会影响结果。常见注意事项包括行末不要有多余空格、每组输出之后要不要空行、输出保留几位小数。题目样例里看不到的地方往往就是隐藏测试点。2.3 用本地命令把OJ流程跑一遍重定向与diff对比理解了规则之后我建议你在本地搭一个最小化的“伪OJ”流程用重定向代替手动输入用diff代替人工比对。这样做的好处是每次改完代码可以一键回归不会出现“忘了刚才哪里改过”的情况。gcc -O2 -Wall -o main main.c -lm printf 1 2\n3 4\n input.txt ./main input.txt output.txt printf 3\n7\n expected.txt if diff -u expected.txt output.txt; then echo test passed else echo test failed fi逐个说明printf把测试输入写进input.txt./main input.txt output.txt把程序标准输入指向input.txt标准输出写入output.txt这一步和OJ运行方式是等价的diff -u expected.txt output.txt比较预期输出与实际输出退出码为0表示完全一致非0则会打印差异行。echo只是做个反馈。如果程序会死循环可以用timeout限制运行时间timeout 2 ./main input.txt output.txttimeout 2表示最多运行2秒超出就干掉进程。想看程序单次运行的耗时加timetime ./main input.txt output.txt这两条命令组合起来就能在本地模拟出TLE和超时效果。把这些写进一个test.sh以后每次写题先跑一遍比一遍遍手敲input快得多尤其应付多组输入的题目时脚本能同时覆盖多组样例。这里要注意本地diff和OJ比对仍然有差异OJ可能包含超大边界数据本地测过了也只是第一关。3. 从参考答案里真正值得抄的四类高频题的解法套路3.1 AB和多组输入题EOF的写法与返回值含义直接看代码#include cstdio int main() { int a, b; while (scanf(%d %d, a, b) ! EOF) { printf(%d\n, a b); } return 0; }这段代码是“多组数据直到EOF”的标准骨架。scanf的返回值是成功匹配的输入项个数在只读两个整数的情况下成功一次返回2读到文件末尾返回EOF在C标准库中通常是-1。条件写成! EOF比写成 2更稳因为当输入里混入非数字字符时匹配失败会让scanf返回0而不是EOF写2会导致死循环写!EOF则至少会在文件结束时退出。有些同学会写成while(!feof(stdin))这是一个非常经典的错误。feof()只有在已经试图读取文件末尾之后才会返回真也就是说循环体可能多执行一次最后一次打印还没有数据可读的输出造成WA或格式错。记住一句话文件结束是靠“读入动作失败”判断的不是靠预判。如果题目第一行给出测试组数T就把循环改成这样int T; scanf(%d, T); while (T--) { scanf(%d %d, a, b); printf(%d\n, a b); }while(T--)在T为0时退出简洁但有个坑如果循环内部还要用T的值就不能这么写。这两种结构在2021年前后的OJ基础题里重复率极高抄参考答案时先看头两行属于哪种再决定抄哪段。3.2 排序与去重sort、比较器与输出控制排序题比AB多一些输出细节。看代码#include algorithm #include cstdio #include vector using namespace std; int main() { int n; while (scanf(%d, n) ! EOF) { vectorint a(n); for (int i 0; i n; i) { scanf(%d, a[i]); } sort(a.begin(), a.end()); for (int i 0; i n; i) { printf(%d%c, a[i], i n - 1 ? \n : ); } } return 0; }sort是C标准库的排序函数时间复杂度O(n log n)默认升序。这里注意两点sort不稳定如果题目要求相同关键字保持原顺序要用stable_sort如果排序对象是结构体需要第三个参数传比较器。C11以后推荐写lambda可以少写一个外部函数sort(users.begin(), users.end(), [](const User a, const User b) { if (a.score ! b.score) return a.score b.score; return a.name b.name; });lambda里定义了两个User的排序规则先按score降序分数相同再按name升序。比较器必须满足严格弱序不能出现“自己和自己比较返回true”的情况否则sort可能崩溃或产生随机结果。输出部分用printf(%d%c, a[i], i n - 1 ? \n : )把数字和分隔符放在一条语句里处理每个数后面跟一个字符最后一个数后输出换行其余输出空格这样不会产生行末多余空格。如果题目还要去重在sort之后配合uniquea.erase(unique(a.begin(), a.end()), a.end());unique把重复元素移到末尾并返回新结尾erase把后面多余元素删掉。注意unique只对连续重复段生效因此必须先sort再用。排序题最容易丢分点不是排序本身而是输出的边界空格和比较器的稳定性这两点记住就能少踩很多坑。3.3 模拟题把中文描述翻译成状态机模拟题在2021年前后的题库里占了不少比例特征是题目描述很长本质是“按规则一步步改变状态”。很多参考答案很长很杂其实骨架只有“读入指令-更新状态-输出结果”。这里给一个通用框架用Python写最直观# 多组测试用例的通用模拟框架 while True: try: n int(input()) except EOFError: break state 0 for _ in range(n): parts input().split() op parts[0] if op set: state int(parts[1]) elif op add: state int(parts[1]) elif op mul: state * int(parts[1]) elif op print: print(state) print(---) # 如果题目要求每组输出后空行改成 print()while True配合except EOFError是Python处理“多组数据直到EOF”的标准写法等价于C的scanf ! EOF。state就是状态变量set/add/mul对应不同操作。print(---)这一行不要照抄它只是示例分隔符具体要不要、要什么要按题目要求来。如果遇到n1e5甚至更大的模拟题Python可能跑不动建议改用C。C版的大体结构是用scanf或cin循环读操作码操作码是字符串时用if/else或switch分支state用一个long long而不是int因为模拟过程中数值可能累加得很大。模拟题最需要重视的是题目里的边界指令比如乘以0、负数、超范围输入、没有print操作。把题干中所有可能改变state的条件列一遍写程序前先在注释里列出状态转移规则这是我常用的预防翻车方式。3.4 基础DP状态定义、转移方程与边界处理DP题代码短思路才是参考答案的核心。以最常见的最大子段和为例#include cstdio #include algorithm using namespace std; int main() { int n; while (scanf(%d, n) ! EOF n) { int cur 0, ans -0x3f3f3f3f, x; for (int i 0; i n; i) { scanf(%d, x); cur max(x, cur x); ans max(ans, cur); } printf(%d\n, ans); } return 0; }这个解法的关键在cur的含义以当前读到的数字为结尾的子段和的最大值。每读一个新数xcur要么从x重新开始要么把x接到之前的最大子段后面所以转移方程是cur max(x, cur x)。ans负责记录遍历过程中cur出现过的最大值是全局答案。边界处理有两个地方ans初始化取一个极小值比如-0x3f3f3f3f约-10.7亿而不是0这样当所有数都是负数时答案能正确输出最大的那个负数while条件里的 n是当n为0时结束循环这个按题目约定来有些题n为0没有意义。时间复杂度O(n)空间O(1)比先枚举左端点再枚举右端点的O(n^2)写法稳得多。很多DP题不是裸的最大子段和而是变体限制子段长度、二维网格走法、背包问题。抄参考答案时如果只抄代码换个题目就失效正确做法是抄状态定义和转移方程再对照代码理解每个数组下标的意义。DP边界错了往往不是段错误而是答案差一点点这种WA最让人头疼只能在思路上严谨。4. 避坑指南LEV OJ提交里最容易翻车的5个细节4.1 输出格式错误差一个空格就是Presentation Error现象运行结果和题目样例肉眼看起来完全一样提交后返回PE甚至WA。原因是OJ逐字符比对输出空格、换行都是字符你多打了一个空格比对就不一致。原因细分成三种行末多空格、每行结尾没有换行、在多组测试数据之间多打了一个空行。很多人本地看到输出“长得像”就提交其实用diff一比就能发现差异。解决的方法是统一用一个循环控制分隔符for (int i 0; i n; i) { if (i) printf( ); printf(%d, a[i]); } printf(\n);这段代码的思路是第一个数字前不打空格之后的每个数字前打一个空格最后统一补换行。这样无论n是1还是100行末都不会残留空格。另一种常见写法是printf(%d%c, a[i], i n - 1 ? \n : )效果相同。提交前如果题目要求每组输出后空一行还要注意最后一组后面是否也要求空行一般规则是“组间空一行最后不多空”可以在输出时判断是不是最后一组。4.2 int溢出小数据对大数据WA的经典原因现象样例、小数据全部正确一旦输入中出现1e9或者1e5规模的大数答案就开始乱跳甚至出现负数。原因是int类型是32位有符号整数最大值约21.47亿2^31-1。当两个大数据相加、累加、连乘时一旦超过这个上限就会溢出结果变成未定义行为或截断后的值。本地调试时数据小看不出来OJ隐藏测试点专门放大数据。解决思路是先估算上限。如果题目给的范围是a、b在[1, 1e9]内ab最多2e9勉强在int边缘但最好不要赌如果是三个数相加或累加和轻松超过。直接用long long是常见做法long long sum 0; scanf(%lld, sum); printf(%lld\n, sum);long long至少64位上限约9.22e18覆盖绝大多数题目的整数范围。还需要注意两个细节一是scanf和printf的格式串要写%lld写%d读long long会读错位二是做乘法时要写成1LL * a * b进行类型提升否则两个int相乘仍按int计算中途就已经溢出了。如果题目要求输出对某个数取模则每步累加后都取模避免中间结果爆炸。4.3 段错误数组越界与局部大数组的坑现象代码在本地运行正常提交后返回RE或者Segmentation Fault相同输入却看不到任何输出。原因一数组越界。比如题目下标从1开始你定义了int a[n]却访问a[n]越界一个位置或者循环里用n访问了a[n]。C/C对数组越界不做检查本地侥幸没崩OJ上附近内存布局不同立刻就段错误。原因二把超大数组定义在main函数栈上。栈空间通常只有8MB左右一个100万int数组占4MB可能勉强但如果数组更大或者还有递归调用栈不够就直接崩。解决大数组提到全局动态分配用vector。全局数组示例#include cstdio int a[1000005]; // 全局数组放在数据段不占栈空间 int main() { int n; scanf(%d, n); for (int i 1; i n; i) scanf(%d, a[i]); return 0; }100万int约4MB内存一般OJ能接受但如果题目内存限制很紧或者数组更大就用vector a(n1)动态申请。写代码时养成习惯所有数组访问前先判断下标是否在合法范围尤其循环变量边界是in还是in差一个等于符号就是灾难。4.4 超时不止是算法问题输入流和循环退出的优化现象提交返回TLE但你确认算法是正确版本本地跑样例也很快。原因分两类算法复杂度过高或者输入输出流太慢。前者需要换思想后者往往被忽视。C里cin默认和C标准IO同步性能比scanf慢不少在数据量大的题目里光是读输入就可能拖到超时。常见做法是关掉同步#include iostream using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; while (cin n) { // 业务逻辑 } return 0; }ios::sync_with_stdio(false)关闭cin/cout与stdio的同步cin.tie(nullptr)让cin不依赖cout的缓冲刷新减少了频繁刷新的开销。需要注意一旦关闭同步就不要混用printf和cout否则输出顺序可能错乱。第二个常见TLE原因是循环退出条件错误比如应该读EOF的题写成了while(cinn)但前面没有读到EOF条件或者使用while(!feof(stdin))造成多读一次。第三个原因是穷举导致复杂度过高典型是n1e5的两层循环数据范围一放大就超时。经验判断1e7以内的单层循环可以接受O(n^2)遇到n1e5就完全不行要优先想前缀和、双指针、二分或者哈希优化。4.5 本地AC提交WAfreopen、endl与未初始化变量现象本地运行结果正确甚至多测试几次都对提交LEV OJ后返回WA有时还伴随RE。原因本地调试时用了freopen(input.txt, r, stdin)把标准输入重定向到了文件提交前忘了删。OJ代码里freopen会尝试打开不存在的input.txt如果OJ环境里没有这个文件轻则读不到数据重则直接RE。另一个容易忽略的是endlendl在输出时会强行刷新缓冲区如果输出量大会显著拖慢速度应当改成\n。还有未初始化变量int x; 没有赋值就用本地栈内存恰好是0OJ上可能是随机值结果完全不一样。解决提交前把freopen注释或删掉调试文件操作可以用条件编译包起来#ifdef LOCAL freopen(input.txt, r, stdin); #endif本地编译命令加-DLOCAL提交时不加这段代码就不会进入OJ的编译产物。同时养成提交前检查三件事一查有没有freopen或fopen二查所有变量是否初始化三查是否用了非标准头文件比如bits/stdc.h很多OJ支持但为了兼容最好显式包含需要的标准头。这三步能做到就能消灭一大类“玄学WA”。5. 把“部分参考答案”变成属于自己的AC答案验证闭环5.1 手工构造边界用例从空输入到最大数据量参考答案一般只带一组样例OJ测试点远不止样例。所以拿到任何题目先手工构造几类边界用例再跑程序。习惯做法是列一张用例表用例类型构造方法要检查的点最小规模n1或只有一条操作循环边界是否处理最大规模数据范围上限是否超时、溢出重复数据全部相同数字排序是否稳定、去重是否正确逆序数据从大到小输入升序排序是否写反空行/空组输入没有数据EOF循环是否提前或延迟退出每一条用例都要先手工算出期望输出再运行程序对比。这个过程看起来慢但比起提交后WA再盲改效率高得多。比如排序题用n1测行末空格用n0测EOF循环用最大值测溢出三个用例一跑大部分坑都会现形。5.2 用对拍脚本让程序自己找反例手工用例能覆盖常见问题但覆盖不了所有逻辑组合。更省力的是对拍写一个暴力但肯定正确的程序brute再拿自己要提交的solve喂同样的随机数据让脚本自动比对两组输出。bash循环版for i in $(seq 1 1000); do python3 gen.py input.txt ./solve input.txt out_solve.txt ./brute input.txt out_brute.txt if ! diff -q out_solve.txt out_brute.txt /dev/null; then echo failed at case $i break fi donediff -q只报告文件是否相同。一旦发现反例脚本会打印具体的case编号并停止此时input.txt里保存的就是一个能让优化程序翻车的输入直接拿它调试。gen.py负责生成随机数据配合前面的边界用例效果最好。一个最小生成器长这样import random n random.randint(1, 10) print(n) for _ in range(n): print(random.randint(-1000, 1000))先把随机数据范围设小一点方便手工复现和调试跑通之后再把范围扩大到题目上限用来查溢出和超时。对拍不是万能的随机数据不一定覆盖到所有隐藏条件所以它要和手工边界用例配合使用。5.3 分值策略先用暴力拿稳部分分再优化AC如果一道优化题想了半小时没有头绪我一般会先把暴力写法交一版。OJ题目往往按数据点给分暴力至少能拿到小数据点的分数比超时强交一个空窗口强。常见顺序是先读题确认输入输出格式写暴力版本提交确认基础分到手再用对拍把优化版本和暴力版本比对确认无误后再提交优化版。这个策略特别适合期末复习目标是尽量拿分而不是纠结一道题横竖AC不了。需要说明的是暴力版本不丢人它是对拍里的标尺也是理解题目的第一步。很多优化解法都是先从暴力过程里发现重复计算才想到前缀和、DP或双指针。参考答案的意义正在于此告诉你这条路能走但最终需要通过自己的验证闭环把它变成确定能AC的答案。6. 从60分到90分建立你自己的错题答案库6.1 按知识点维度重排题库而不是按题号刷按题号或题目顺序刷题很容易被某个一直过不了的题卡住然后一整晚都在和同一道题较劲。常见做法是拿到2021年这批题后先按知识点分成几组输入输出、排序、字符串处理、模拟、递推与DP、简单数据结构。每组选十几道题集中做做完一组再换下一组。这样做的好处是同类题型的套路会在短时间内重叠多次形成“肌肉记忆”而且你很快会发现不同题号背后的考点是高度重复的答案模板可以互相迁移。6.2 给每道WA题写三行病历我自己的习惯是每次提交返回WA、RE、TLE后不急着改代码先在错题本里按“现象-原因-解决”写三行。比如“现象n50000时TLE原因用了两层循环解决改前缀和把查询变成O(1)”。写病历的过程其实就是强制自己定位错误而不是盲目改一个变量再试一次。坚持几周后你会发现高频错误就那么几类看一眼错误提示就能直接想起上次的解法。这个错题本比任何“参考答案”都更值钱因为它是针对你自己弱点的定制答案。6.3 主动重写已经AC的题理解复杂度差距AC只是第一步。隔一周之后重写同一道题换一种解法能用前缀和的就不要用两层循环能用迭代的就不要用递归能把状态压缩的就不要开多余数组。重写时注意比较两种写法的时间差距逐步建立“看到数据范围就能判断该用什么复杂度”的能力。我的教训是曾经一次交OJ前忘了删调试用的freopen连续WA了三次才想明白自从那以后每次提交都先grep一遍freopen和endl再跑一次上面说的本地diff流程。判题规则的细节、边界用例的习惯、错题复盘的速度这些才是从“看懂参考答案”到“稳定AC”之间真正要补的距离。希望这些经验能帮到你。本文还有配套的精品资源点击获取