简介南信大2021年LEVOJ在线编程平台的部分题目参考答案面向南信大学生及算法编程爱好者用于刷题复盘、算法巩固与考前冲刺。资源包大小约12KB以C语言源码文件为主文件总数未单列覆盖字符串处理、动态规划、图论最短路、数论、排序与查找等典型题型并附有解题思路和算法要点。已有3137人浏览学习。这份材料不止于代码更展示了从读题、设计状态到编码的完整路径。通过对照各题实现可深入理解KMP、背包模型、Dijkstra、质因数分解、二分查找等经典算法的实际应用还能学习如何用数组、栈、队列、树等基础数据结构组织解题过程体会时间复杂度的优化方法。同时资料中对数学基础与问题分析方法的强调能帮助读者把实际问题抽象为计算模型再选择合适的算法与数据结构落地编码。整体内容贴近课程与校赛难度适合入门到中级水平的读者按需选用也可在LEVOJ日常训练中作为参考手册提升独立编程与竞赛实战能力。1. 2021南信大levoj部分参考答案为什么你需要的其实是解题框架2021年南信大levoj题库里很多题至今还在被反复刷每到期末机考前总有人到处搜部分参考答案。但说实话直接贴一份代码让你背下来换一道题大概率还是WA。真正能让你在levoj上稳定AC的是题目背后的输入输出习惯、边界条件和算法模板的组合。这篇文章就围绕2021年levoj上高频出现的几类题把参考答案拆成可以照着改的解题框架。适合正在刷levoj准备期末上机考试的同学也适合刚接触在线评测、被WA折磨到怀疑人生的新手。读完你会发现与其背答案不如把答案变成自己的板子。2. levoj的判题环境与输入输出模板参考答案能AC的前提2.1 南信大levoj的评测逻辑黑盒测试与多组数据levoj本质上是一个典型的OJ在线评测系统你提交的源码会被编译后在服务器上运行服务器用一组输入文件喂给你的程序再把你的输出和标准输出逐字符比对。它不看你代码风格好不好不看注释多不多只看结果对不对。所以一份参考答案的价值不在于它写了什么而在于它能通过评测机上的全部测试点。评测结果常见的有AC通过、WA答案错误、TLE超时、MLE内存超限、RE运行时错误、CE编译错误。我见过不少新手第一次提交就卡在CE上——比如Java类名写了别的名字或者C头文件在旧标准下编译不过。这些不是算法问题而是对评测环境不了解。levoj的判题机对C通常使用较新的标准C11或更高Java类名必须叫MainPython则要注意递归深度限制。知道这些才能让参考答案真正落地。另一个核心规则是多组数据。levoj的题不会只跑一组测试数据而是把多组输入放在同一个文件里你的程序要循环读到文件末尾EOF每读一组算一组直到没有输入为止。很多新人在本地写代码时只测了一组数据一提交就WA就是因为程序根本没有处理后续的输入。下面这几套模板就是为这个场景准备的。2.2 三套通用输入输出模板Python/C/Java无论题目是什么先把输入输出的骨架搭好真正的算法逻辑在骨架里填。这是我刷levoj的习惯也是整理参考答案时的第一步。Python模板如下import sys def solve(data): # data 是按空格切分后的字符串列表 # 在这里写具体的计算逻辑 a, b map(int, data) return str(a b) def main(): for line in sys.stdin: line line.strip() if not line: continue # 跳过空行防止解析出错 parts line.split() print(solve(parts)) if __name__ __main__: main()这段模板做了三件事用sys.stdin逐行读取避免一次读入全部数据导致内存浪费用strip()去掉行尾的换行符因为line.split()对空白字符不敏感但有些场景需要干净字符串跳过空行levoj的测试数据偶尔在末尾多一个空行不跳过可能会导致多输出一次结果。solve函数独立出来方便在本地对拍时直接调用。C模板则更依赖cin 自带的分词能力#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int a, b; while (cin a b) { // while 读到 EOF 自动退出 cout a b \n; } return 0; }while (cin a b)是C处理多组数据的标准写法遇到文件结束符自动终止。ios::sync_with_stdio(false)和cin.tie(nullptr)这两行是用来解除C标准IO与C标准IO的同步、取消cin与cout的绑定可以显著提升读写速度特别是数据量大的题少了这两行可能直接TLE。注意这里输出用的是\n而不是endl因为endl会额外刷新缓冲区频繁刷新也是性能杀手。Java的模板同样要处理多组输入而且类名是硬性要求import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); while (sc.hasNextInt()) { int a sc.nextInt(); int b sc.nextInt(); System.out.println(a b); } sc.close(); } }Java的Scanner.hasNextInt()在读到EOF时返回false循环自然结束。这里必须把类名写成Main提交后编译器的入口才能找到它写成别的名字levoj会直接给你一个CE连评测的机会都没有。sc.close()在竞技编程里可以省略但写上是个好习惯。2.3 数据范围决定算法先看n再动手参考答案能不能AC除了结果正确还要在时间和内存限制内跑完。levoj的题目一般会给出数据范围这是选择算法的第一依据。我通常先看n的量级再决定不能做什么。给出一张我自己的对照表数据范围能接受的复杂度常见算法选择n ≤ 1000O(n²)冒泡排序、朴素动态规划、双重循环枚举n ≤ 100000O(n log n)sort排序、二分、线段树、贪心n ≤ 1000000O(n)前缀和、双指针、单调队列n ≤ 10^18O(log n)快速幂、矩阵快速幂、数论公式比如判断一个数是不是素数n只有10时for i in range(2, n)谁都会写但n到10^12用这种写法在levoj上必然TLE需要换成sqrt(n)范围内的试除。同样是排序n100时冒泡可以n100000时你必须用sort。参考答案背后的算法选型本质上是和数据范围的一场交易。3. 四个高频题型的参考思路与代码照着改就能跑3.1 多组整数求和EOF读入的三种写法2021年levoj的基础题里最不缺的就是多组整数求和。这类题就是考察你有没有掌握EOF读入。前面模板已经展示前两种写法。第三种是哨兵终止写法也就是题目明确说以0 0作为结束标志import sys while True: line sys.stdin.readline() if not line: break # 读到文件末尾也退出 a, b map(int, line.split()) if a 0 and b 0: break # 0 0 是结束标志不是待处理的数据 print(a b)注意这里的顺序先判断not line再判断是否为0 0两者不能颠倒。因为当读到EOF时line是空字符串直接split()会报错而如果先判断0 0但它是字符串不能直接和0比较。这种边读边判断的写法在C里对应while (cin a b (a || b))但C里要小心a || b为假时循环退出0 0不会被处理。很多参考答案就是用这个特性实现的但新手容易犯的错误是把0 0也当成一组正常输入多输出一行。3.2 素数判断与埃筛从单点查询到区间查询素数题在levoj的python基础和C语言题库里反复出现。单点素数判断的标准参考写法import math def is_prime(n): if n 2: return False if n 2: return True if n % 2 0: return False limit int(math.sqrt(n)) 1 for i in range(3, limit, 2): if n % i 0: return False return True这个函数的核心是limit int(math.sqrt(n)) 1。如果n有一个大于sqrt(n)的因子d那么n/d一定小于sqrt(n)所以只需要检查到sqrt(n)即可。先排除偶数步长设为2又把循环次数砍了一半。对单个数来说这是最实用的写法。如果是区间素数查询比如问[2, n]内有多少个素数每次都用is_prime一个个判断复杂度O(n√n)在n100000时就会明显变慢。这时候应该用埃拉托色尼筛def sieve(n): is_prime [True] * (n 1) is_prime[0] is_prime[1] False for i in range(2, int(n ** 0.5) 1): if is_prime[i]: for j in range(i * i, n 1, i): is_prime[j] False return is_prime注意内层循环从i * i开始而不是从i * 2开始。因为小于i*i的合数已经被更小的质因子标记过了从i*i开始能省掉大量重复标记。is_prime返回的是一个布尔列表下标对应数字本身所以数组长度是n1。用n ** 0.5求根号不需要导入math但要注意n是整数时结果可能带浮点误差转成int后加1更稳妥。3.3 自定义排序把排名规则翻译成比较器levoj的排序题从不会直接让你排数字而是给你一个结构体比如学生信息学号、成绩要求按成绩降序、成绩相同时按学号升序。这种题的参考答案核心是把排序规则翻译成代码。Python用sorted加key函数最简洁import sys students [] for line in sys.stdin: parts line.split() if not parts: continue sid parts[0] score int(parts[1]) students.append((sid, score)) # 先按成绩降序再按学号升序 students.sort(keylambda x: (-x[1], x[0])) for sid, score in students: print(sid, score)这里key返回一个元组元组比较时先比较第一个元素相等时再比较第二个。成绩取负数实现降序学号是字符串正序就是字典序升序。这个技巧是Python刷题必须掌握的比写复杂cmp函数省事得多。C则需要自定义比较器这对刚学C语言的同学是个坎#include bits/stdc.h using namespace std; struct Student { string id; int score; }; bool cmp(const Student a, const Student b) { if (a.score ! b.score) return a.score b.score; // 成绩降序 return a.id b.id; // 学号升序 } int main() { int n; cin n; vectorStudent stu(n); for (int i 0; i n; i) { cin stu[i].id stu[i].score; } sort(stu.begin(), stu.end(), cmp); for (auto s : stu) { cout s.id s.score \n; } return 0; }cmp必须满足严格弱序如果a和b等价那么cmp(a,b)和cmp(b,a)都得返回false。如果你写成return a.score b.score当两个成绩相等时cmp(a,b)和cmp(b,a)都为true这违反了排序要求轻则结果乱序重则程序崩掉。写比较器时只在确定一个排在另一个前面时返回true其余情况返回false。3.4 最长上升子序列动态规划的朴素与优化两版动态规划题在2021年的levoj里属于中等难度最长上升子序列LIS是其中很有代表性的一道。朴素版本的参考做法def lis(nums): n len(nums) if n 0: return 0 dp [1] * n for i in range(n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp)dp[i]表示以nums[i]结尾的最长上升子序列长度。初始化全部为1因为每个元素自己单独构成一个长度为1的子序列。状态转移时枚举i之前的每一个j只要nums[j] nums[i]就可以尝试把nums[i]接到nums[j]后面。复杂度O(n²)能应付n1000的数据。如果n到10000以上O(n²)就会TLE。这时改用贪心加二分维护一个tails数组import bisect def lis_fast(nums): tails [] for x in nums: pos bisect.bisect_left(tails, x) if pos len(tails): tails.append(x) else: tails[pos] x return len(tails)tails数组的长度就是LIS的长度但tails本身并不是LIS它只是到目前为止长度为k的上升子序列末尾元素的最小值。用bisect_left而非bisect_right是为了让重复元素不会替代已有元素从而保证是严格上升而不是非递减。如果题目要求非递减才改用bisect_right。这个区别是levoj上LIS题目最容易翻车的地方。4. 参考答案怎么抄才不翻车改造与自测方法4.1 先跑通再改一个用例一个用例地验证从网上或学长那里拿到参考答案最关键的一步不是直接提交而是先在本地跑通。levoj每道题都会给示例输入和示例输出把示例输入存成input.txt运行程序python3 solution.py input.txt output.txt diff expected.txt output.txt如果diff没有输出说明示例通过。但这只代表你有了一个看起来对的版本不代表能AC。接下来要自己构造边界用例最小值、最大值、空输入、只有一个元素、全部相同元素、逆序排列。比如LIS题nums [1]应该返回1nums [5,4,3,2,1]应该返回1nums [1,2,3,4,5]应该返回5。把这些数据挨个塞进去哪个不对就改哪个。这条流程能解决70%的WA问题。4.2 把递归改成迭代Python深度限制与栈溢出levoj上有些搜索题参考答案用递归写得很漂亮但一跑大数据就崩。原因是Python默认递归深度限制在1000左右而递归调用栈会继续消耗内存即使你sys.setrecursionlimit(100000)底层C栈也可能溢出。C里递归深度达到几十万同样会爆栈。所以我会优先把递归改成迭代。以计算斐波那契数列为例递归写法在n40时就开始肉眼可见地卡def fib_rec(n): if n 1: return n return fib_rec(n - 1) fib_rec(n - 2)改成迭代后不但快还不会爆递归栈def fib_iter(n): if n 1: return n a, b 0, 1 for _ in range(2, n 1): a, b b, a b return b这个思路适用于所有递推关系明确的递归先找状态转移方程然后用循环从底向上推。如果题目确实需要深度优先搜索而递归深度又压不住优先考虑用显式栈模拟或者换成BFS。在levoj上求最少步数最短路径这类题BFS往往本来就是正解。4.3 用随机数据对拍验证参考答案的正确性如果样例和边界测试都过了但提交还是WA很可能是你理解错了题意或者参考答案本身有隐藏瑕疵。这时候用对拍法产生大量随机数据拿一个慢但逻辑简单的暴力程序当标准答案和你要验证的程序对比输出。先写一个数据生成器gen.pyimport random n random.randint(1, 10) # 小规模数据 print(n) for _ in range(n): print(random.randint(0, 100))再写一个暴力程序brute.py用最直白的方式求解保证正确。然后跑对拍脚本for i in $(seq 1 1000); do python3 gen.py in.txt python3 brute.py in.txt out1.txt python3 fast.py in.txt out2.txt if ! diff -q out1.txt out2.txt /dev/null; then echo Wrong on test $i break fi doneseq 1 1000循环1000次每次生成新数据分别跑暴力和待验证程序比较输出。第一次diff有差异就停下然后把in.txt保留下来观察。注意生成器要覆盖边界n取1、取最大值、取0如果合法数值取0、取最大值。对拍是我在levoj题上犯错时的一颗后悔药比对着屏幕干瞪眼高效得多。5. 在levoj上提交避坑5条让WA变AC的血泪经验5.1 输出格式行尾空格、空行错位新手最常遇到的现象是本地输出和示例输出肉眼看起来一模一样提交后却WA。原因是levoj的判题机是逐字符比对输出的行尾多一个空格、两行之间少一个空行都会被判定为错误。比如print(a, b)在Python里输出两个变量时中间有空格多数题是认可的但如果你用print(a, b, end )多打了一个行尾空格或者用print(res)后还额外print()多输出一个空行就会出问题。解决方式是在本地用diff比对时别只看内容也要看空白。用cat -A output.txt查看每行末尾有没有多余的$表示换行前的空格。5.2 scanf与换行符吞掉\n的经典事故C/C里最常见的翻车点先读一个数字n再用getline或gets读字符串结果字符串读出来是空的。原因是cin n读到数值后就停在换行符前换行符还留在输入流里下一次getline直接把这个换行符读走了。解决办法是在读完整数后先消费掉换行符int n; cin n; cin.ignore(); // 吞掉残留的换行符 string line; getline(cin, line);cin.ignore()默认读走一个字符刚好把换行符处理掉。如果模板里用了getchar()效果类似。这个坑在2021年levoj的字符串处理题中反复出现遇到WA不妨怀疑一下是不是输入流里残了东西。5.3 数组开多大边界下标与段错误C语言在levoj上做数组题时经常出现本地运行没问题提交就RE的诡异现象。最常见的原因是数组越界。题目说n ≤ 100000你开了int a[100000]以为够用但如果你从下标1开始存储最后一个元素就到了a[100000]这已经越界了因为数组合法的下标范围是0~99999。解决习惯一律开a[100005]多开几个单位当安全垫。动态数组则用vectorint a(n 1)。越界可能不会立刻崩溃但它可能悄悄破坏别的变量导致结果随机出错这种玄学问题最难排查。5.4 浮点数精度1e-6与%.6f涉及浮点数计算的题输出保留两位小数你用了printf(%.2f, ans)但WA了。这不是格式错是浮点误差。比如计算0.3 - 0.1在计算机里不等于0.2而是0.19999999999999998。四舍五入到两位小数时可能输出0.19而不是0.20。解决方法是输出前加一个极小量比如printf(%.2f\n, ans 1e-9)如果题目要求判断两个浮点数是否相等不要用要用fabs(a - b) 1e-8。这些都是浮点数判定的老规矩levoj的数据里专门准备了卡误差的测试点。5.5 多组输入的终止条件0 0不是输入是哨兵很多题写成输入包含多组数每组两个整数a、b以0 0结束。新手看到0 0把它当作最后一组要计算的数据结果多输出一行WA。记住0 0是停止信号不是待处理数据。判断顺序应该是先读取再判断是否为哨兵是就退出循环。Python写法见3.1节C可以写成while (cin a b !(a 0 b 0)) { cout a b \n; }这里!(a 0 b 0)等价于a ! 0 || b ! 0一旦是0 0循环条件为false直接退出。这样0 0就不会被处理也不会多输出。6. 把部分参考答案变成自己的板子一个可复用的算法模板库当你照着上面的方法刷了几十道levoj题、整理完一批参考答案后我建议你做一个自己的模板库。不是把代码复制粘贴堆在一起而是按场景分类每份模板前面写清楚适用数据范围、时间复杂度、需要注意的边界条件。比如我会建一个templates/目录里面有int_io.cpp、string_io.py、prime_sieve.py、lis.py、sort_struct.cpp等等。每份模板的开头注释写上这个模板解决什么问题、输入是什么、输出格式是什么、复杂度多少、已知的坑是什么。这样做的另一个好处是机考时如果允许本地带代码你可以快速翻阅即使不允许你也能通过模板库反推出思路。我习惯每次AC一道题后把这道题里和模板不同的地方单独记下来比如这题要用bisect_right而不是bisect_left这题要输出的是方案数而不是长度。这些差异就是踩坑记录比一份完美的参考答案更值钱。最后说一个我自己的教训刚刷OJ那会儿我拿到了前辈的答案没跑本地测试直接提交结果WA了三次才发现是把哨兵数据也计算了。后来我养成了任何代码先过本地样例再构造三个边界用例最后才提交的习惯。这个习惯让我在levoj上的AC率从50%提到了90%左右。希望帮到你也祝你早日把这些参考答案变成真正属于自己的东西。本文还有配套的精品资源点击获取
