简介面向南信大LEVOJ学习者的2021年部分题目参考答案与解析资料适合作业练习、备赛刷题和算法复习。资源以zip压缩包形式提供整体约12KB内容围绕P1243、P1249、P1119、P1516等题号展开包含参考C语言代码、题目分析与解题思路说明并延伸整理出数据结构与算法学习要点、实践提升路径。题目方向覆盖字符串高效处理、数组与动态规划、图论最短路径与最小生成树、数论与数学逻辑等能够帮助读者在实战中理解不同算法的适用场景与复杂度取舍。已有3139人浏览学习。学习者对照代码和思路可逐步掌握状态转移方程的建立、图算法的合理选用、数学概念到代码的转化等关键环节同时参考文中给出的学习与实践建议定期参与平台竞赛、对比多种解法从而系统提升编程能力和竞赛水平。1. 先说结论一份OJ参考题解值得按四条算法线去拆2021年某高校OJ平台上那份被反复下载的参考题解包文件以P1243.c、P1249.c、P1119.c这样的编号命名第一次看到的人容易把它当成“抄答案”合集。实际拆完以后会发现它覆盖了字符串匹配、动态规划、图论最短路、数论质因数分解四个高频出题方向代码是标准C语言直接面向OJ提交的scanf/printf格式。对刷题量在一两百道、正卡在状态转移方程上的算法入门者来说这包代码能省掉大量“想不出思路”的时间对已经工作、想快速捡回C语言和算法底子的开发者它是一份很好的复盘样本。这份参考答案能解决的核心问题是你缺的不是更多题目而是一批能看懂、能改、能回OJ重新提交验证的C代码范本。适合期末冲刺、算法竞赛入门、以及C语言课程设计前临时抱佛脚的人群。2. 这包代码怎么组织P编号背后的算法地图与选型逻辑2.1 十个文件至少覆盖五个算法方向先把资源里的文件摊开看P开头的数字是OJ平台上的题目编号每个编号对应一道独立题目。从文件名的顺序和常见高校OJ的出题规律来看这十来个文件可以初步归类为字符串处理、动态规划、图论、数论、排序与查找五大方向。我建议拿到压缩包之后第一件事不是急着打开代码而是先建目录、把文件按算法方向归档这一步能让你后续复习时少翻很多次文件夹。mkdir -p src/{string,dp,graph,math,search} mv P1243.c src/string/ mv P1249.c src/dp/ mv P1119.c src/graph/ mv P1516.c src/math/ mv P1141.c src/search/ mv P1328.c src/search/ mv P1620.c src/dp/ mv 1102中华文化.c src/string/归档命令里的花括号展开是Linux shell的常见写法一行创建五个目录。文件移动时如果某个编号对应题目类型判断错了也不用慌后面打开代码看一眼核心函数就能纠正。这里我把1102中华文化.c放进了字符串目录是因为从OJ题库的命名习惯看带文化背景的题目往往本质是字符串处理或编码转换名字只是障眼法。下面这张表格是我拆完代码后整理出的文件与考点对应关系仅供第一次阅读时参考文件名可能涉及的考点典型算法方向P1243.c字符串搜索、模式匹配KMP、Boyer-MooreP1249.c数组操作、最优策略动态规划、背包/LISP1119.c图结构、路径求解Dijkstra、Floyd、最小生成树P1516.c数论、数学归纳质因数分解、模运算P1141.c查找、有序序列二分查找、哈希P1328.c排序、稳定性快排、归并排序P1620.c递归、状态回退回溯、DFS1102中华文化.c字符串、编码字符串处理、位运算这张表不需要背它的意义在于建立“文件编号 → 算法方向”的映射感。以后你在OJ上看到PXXXX编号扫一眼题目描述就能大致猜到出题人想考什么这是刷题老手和新人之间最明显的差距。2.2 为什么字符串匹配优先想到KMP而不是暴力P1243.c这类字符串题最容易翻车的做法是上来就写两层for循环暴力匹配。题目数据量小的时候暴力能过但OJ后台的测试点里往往会塞一组长度10^5以上的文本串暴力匹配的时间复杂度是O(n*m)直接超时。KMP算法的核心价值在于把模式串的匹配过程从“每次失败从头再来”变成“利用已匹配信息跳着走”时间复杂度稳定在O(nm)。常见做法是预处理模式串的next数组。next[i]表示模式串前i个字符组成的子串中最长相等前后缀的长度。匹配时文本串指针不回退只回退模式串指针这样文本串只扫描一遍。Boyer-Moore在工程文本编辑器里通常更快因为它利用“坏字符规则”和“好后缀规则”跳过更多位置但实现细节比KMP复杂不少OJ现场写容易出边界bug。我一般会优先写KMP原因有三第一next数组的构建逻辑在各种教科书里都有标准模板不容易写错第二KMP对中文字符串和二进制串同样适用第三面试和考试里KMP出现的频率远高于Boyer-Moore。P1243.c这份参考代码如果用的不是KMP而是暴力匹配那它的参考价值更多在于“理解题意”而不是“学会高效解法”这一点你得自己分辨。2.3 图论、数论、DP为什么同时出现在一份题解包里高校OJ的题库通常按知识点组织一份学期题解覆盖图论、数论、动态规划再正常不过。P1119.c如果是最短路径题出题人会在题目描述里给出图的点数n、边数m以及是否有负权边。选算法的依据很直接单源正权图用Dijkstra堆优化后复杂度O((nm)log n)多源全点对最短路用FloydO(n^3)但实现极简单有负权边就得Bellman-Ford或SPFA。P1516.c如果是数论题重点观察数据范围。质因数分解用试除法到sqrt(n)就够但n超过10^9时试除法就很吃力了得考虑Pollard-Rho。模运算的核心坑是中间结果溢出C语言里int与int相乘不会自动升为long long必须先强转。动态规划题则相反重点不在算法选择而在状态定义和转移方程怎么写这部分没有固定套路只能靠多做题喂经验。这一章你不需要把所有算法都掌握才能看这份资源。正确的打开方式是先按归档目录定位到当前要学的方向只看那一个子目录下的代码把其他文件留到后面。贪多嚼不烂OJ题解尤其如此。3. 把思路落成C代码KMP、LIS、Dijkstra三个可抄骨架3.1 P1243字符串匹配KMP的C实现与next数组边界很多题解说“用KMP”但贴出来的代码却在每次匹配失败时调用strstr库函数这其实没有吃到KMP的红利。真正的手写KMP需要两个部分构建next数组和匹配扫描。下面这段是从常见AC代码里提炼出的标准骨架你可以直接抄进自己的工程里再改输入部分。#include stdio.h #include string.h #define MAXN 1000005 char text[MAXN], pat[MAXN]; int next[MAXN]; void build_next(const char *p, int *nx) { int len strlen(p); int i 0, j -1; nx[0] -1; while (i len - 1) { if (j -1 || p[i] p[j]) { i; j; nx[i] j; } else { j nx[j]; } } } int kmp_search(const char *t, const char *p) { int n strlen(t), m strlen(p); int i 0, j 0; build_next(p, next); while (i n j m) { if (j -1 || t[i] p[j]) { i; j; } else { j next[j]; } } if (j m) return i - m; return -1; } int main() { while (scanf(%s%s, text, pat) ! EOF) { int pos kmp_search(text, pat); if (pos 0) printf(%d\n, pos 1); else printf(Not Found\n); } return 0; }这段代码的关键在build_next函数nx[0]固定为-1循环里p[i]p[j]时同步后移并记录最长相同前后缀长度不相等时通过nx[j]回退。匹配阶段文本串下标i只增不减这是KMP复杂度O(nm)的前提。main函数里用了while(scanf(...)!EOF)是因为OJ题目常包含多组测试数据漏掉这个循环会导致只跑第一组样例就结束输出对不上。参数方面MAXN要留余量如果题目说文本串长度不超过10^5直接开10^6比较稳妥避免数组越界段错误。位置从0还是从1计数看题目要求我的代码返回的pos是0基下标输出时加了1转成1基。3.2 P1249动态规划最长递增子序列的两种写法P1249.c如果考的是最长递增子序列最直观的做法是O(n^2)的经典DPdp[i]表示以第i个元素结尾的最长递增子序列长度每次向前扫描所有ji如果a[j]a[i]就尝试用dp[j]1更新dp[i]。这个方法的好处是好想、好写、不容易错n在5000以内都可以直接交。#include stdio.h #define MAXN 10005 int a[MAXN], dp[MAXN]; int main() { int n; while (scanf(%d, n) ! EOF) { for (int i 1; i n; i) scanf(%d, a[i]); int ans 0; for (int i 1; i n; i) { dp[i] 1; for (int j 1; j i; j) { if (a[j] a[i] dp[j] 1 dp[i]) { dp[i] dp[j] 1; } } if (dp[i] ans) ans dp[i]; } printf(%d\n, ans); } return 0; }dp[i]初始化为1是必须的因为单个元素本身就是一个长度为1的递增子序列。内层循环遍历前i-1个元素只有满足数值递增关系才尝试转移。这段代码的时间复杂度是O(n^2)当n到10^5级别时必超时那就得换O(nlogn)的二分贪心版本用辅助数组g[k]记录长度为k的递增子序列的最小末尾值配合lower_bound二分查找。两种写法都要会因为OJ题不仅考对不对还考能不能过时间限制。我个人建议先把O(n^2)版本调通再用随机数据比较两个版本的输出是否一致。对拍确认新算法正确后再提交能避免“优化完反而WA”的尴尬局面。3.3 P1119图论Dijkstra的邻接矩阵实现与INF取值图论题如果点数n不超过1000邻接矩阵Dijkstra是最不容易写错的组合。邻接表在稀疏图里更省内存但链式前向星或vector的实现代码量更大考试现场我更推荐矩阵。INF取0x3f3f3f3f而不是INT_MAX是因为INT_MAX做dist[u]g[u][v]加法时可能溢出而0x3f3f3f3f大约10^9两个相加仍在int范围内。#include stdio.h #include string.h #define INF 0x3f3f3f3f #define MAXN 1005 int g[MAXN][MAXN]; int dist[MAXN], vis[MAXN]; int n, m; void dijkstra(int s) { memset(dist, 0x3f, sizeof(dist)); memset(vis, 0, sizeof(vis)); dist[s] 0; for (int k 0; k n; k) { int u -1, min_val INF; for (int i 1; i n; i) { if (!vis[i] dist[i] min_val) { min_val dist[i]; u i; } } if (u -1) break; vis[u] 1; for (int v 1; v n; v) { if (!vis[v] g[u][v] INF dist[u] g[u][v] dist[v]) { dist[v] dist[u] g[u][v]; } } } } int main() { int s, t; memset(g, 0x3f, sizeof(g)); scanf(%d%d%d%d, n, m, s, t); for (int i 0; i m; i) { int u, v, w; scanf(%d%d%d, u, v, w); if (w g[u][v]) g[u][v] w; } dijkstra(s); printf(%d\n, dist[t] INF ? -1 : dist[t]); return 0; }这段代码的循环次数是n轮每轮扫描未访问节点找最小dist再松弛相邻节点总体O(n^2)。main函数里输入了四个数n节点数、m边数、s起点、t终点。重边的处理用if(w g[u][v])保留最小权值这是很多新手容易漏的点。输出时如果dist[t]还是INF说明s无法到达t输出-1。如果你把这份资源里的P1119.c打开后发现写的是SPFA也别急着否定它。SPFA在平均情况下很快但最坏复杂度是指数级部分OJ会有专门卡SPFA的数据。稳妥起见非负权图优先选Dijkstra这个习惯能让你在正式比赛里少丢分。4. 本地跑通却提交失败五个最常见的OJ判题避坑记录4.1 本地对提交WA多组测试数据的读取漏写现象自己在编译器里输入样例输出和预期一模一样一提交就Wrong Answer。原因OJ的测试数据通常包含多个测试用例每个用例之间以文件结束符分隔代码里只处理了一组数据。解决把main里的核心逻辑套进while(scanf(%d, n) ! EOF)或while(~scanf(...))循环中。这个循环结构在KMP和LIS两段代码里都有示例值得形成肌肉记忆。4.2 数组越界段错误MAXN开小了五位现象样例能跑后台一跑就Runtime Error或Segmentation Fault。原因题目给的数据范围是n 10^5你开了int a[100005]但数组下标从0用到n刚好越界一个单位或者题目实际测试点稍微超了题面范围。解决数组长度统一在题目上限基础上加5到10比如10^5就开100005并检查循环里的下标是否从0开始。另一个隐蔽点是多个测试用例之间数组没有清零导致上次运行残留数据影响下次判断。4.3 scanf读到换行被跳过字符与数字混读的残留问题现象先读整数n再读一行字符串字符串开头总多一个换行或空格。原因scanf(%d, n)读完数字后缓冲区里还留着换行符gets或scanf(%s)会先吞掉这个换行。解决读完数字后用getchar()手动吃掉换行或者统一用scanf(%s)读字符串它本身会跳过空白字符。注意gets在C标准里已经废弃OJ的老编译器也许还支持但新环境下不如用fgets再手动去掉尾部换行。4.4 复杂度估错导致的TLEO(n^2)卡死10^5数据现象算法逻辑完全正确本地大数据也能跑但OJ报Time Limit Exceeded。原因题目n为10^5O(n^2)的运算量是10^10远超1秒。解决提交前先估算数据规模下的运算量超过10^7就得换更优算法。LIS的O(nlogn)二分优化、Dijkstra的堆优化、KMP替代暴力匹配都是为这种场景准备的。这类坑最容易出现“看了答案觉得简单自己写还是超时”的情况所以平时练习就要养成先算复杂度的习惯。4.5 全局变量忘清零多组数据之间的脏数据污染现象第一组数据正确第二组数据开始输出错乱。原因全局数组在程序启动时确实自动初始化为0但你在第一组数据处理过程中修改了它们第二组数据进来时没有重新memset。解决每组数据处理前把用到的数组显式重置。dist数组用memset设置成0x3fvis和dp用memset清零g矩阵在初始化时直接按INF填充。养成这个习惯之后多组数据的题基本不会再在这个地方翻车。5. 从抄题解到会做题复杂度分析、测试与代码风格重构5.1 把一份AC代码改成三种写法才算真正吃透很多同学下载题解包后对着答案看一遍觉得“懂了”关上文件自己写又卡住。这是因为阅读代码和编写代码用的是两个认知过程。这里的血泪经验是一道题至少写三遍。第一遍照抄参考代码并跑通理解每行作用第二遍合上文件凭记忆重写卡住的地方就是你还没消化的部分第三遍换一种算法或数据结构重新实现这道题。比如P1249.c用O(n^2)的DP写过一遍后强制自己用二分贪心的O(nlogn)版本再写一次两版代码随机数据对拍输出一致才算通过。这种复写训练对状态转移方程的理解特别有效比连续刷十道新题都值。5.2 用对拍脚本保护每一次重构手写代码最怕“优化完反而WA”。常见做法是写一个bash对拍脚本让暴力版本、优化版本和随机数据生成器配合运行。脚本逻辑很简单循环生成随机测试数据两个程序分别跑diff输出文件一旦不一致立即退出。for i in $(seq 1 100); do ./gen data.in ./brute data.in out1 ./opt data.in out2 if diff -q out1 out2 /dev/null; then echo case $i ok else echo case $i failed break fi donegen、brute、opt三个二进制文件分别对应随机数据生成器、暴力解和优化解。注意gen里要用随机数生成符合题目范围的数据包括边界值比如n1、n最大值不要只生成中间段数据。对拍脚本跑100组不挂再提交OJ就会安心很多。这个技巧不止适用于这份题解以后你自己刷所有OJ题目都用得上。5.3 什么时候该看参考代码什么时候必须自己死磕参考题解的正确打开方式不是“直接看答案”而是“先思考再看答案再不看答案重写”。我一般给自己定一个15分钟的计时拿到题目先读题、画样例、写伪代码15分钟后还没有可落地的思路才翻开题解看开头部分只看“解题思路”不看代码如果看完思路能自己写出来那这道题已经内化了大半。只有思路和代码都被卡住时才看完整参考代码但看完必须合上文件手写复现一遍。这种策略让你既不会在难题上死磕到深夜也不会因为轻易翻答案而丧失思考能力。6. 让这份资源产生复利把题解包改造成个人刷题清单资源到手只是第一步怎么让它持续产生价值才是关键。我建议你按一周循环的方式拆解这个题解包每周挑三个文件每个文件对应一个算法方向周一研究P1243.c的KMP并复写周三研究P1249.c的LIS并做二分优化周五研究P1119.c的Dijkstra并试着手写堆优化。每道题做完之后在一张表格里记录四件事核心考点、时间复杂度、第一次提交是否AC、卡住的点是什么。文件名考点复杂度卡点记录P1243.cKMPO(nm)next数组回退逻辑P1249.cLISO(nlogn)二分边界P1119.cDijkstraO(n^2)重边处理P1516.c质因数分解O(sqrt(n))溢出问题这张表就是你的错题本。研究题解时还可以做一步延伸把AC代码里的关键参数改一改再提交比如把KMP的next构建方式改成优化版不连续回退看看OJ判定结果有什么变化这能帮你理解算法变体的边界。等到这份资源里的所有文件都过过一遍手你会发现自己在面对新的P编号题目时已经不太需要参考答案了。最后说一个习惯从那以后我每次下载任何题解资源都强制自己先归档、再复写、再对拍最后回到OJ重新提交一遍完整流程绝不停留在“看懂了”这个层面。算法这东西看一眼是别人的写一遍才是自己的希望帮到你。本文还有配套的精品资源点击获取