简介：面向南信大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题库的命名习惯看，带文化背景的题目往往本质是字符串处理或编码转换，名字只是障眼法。

下面这张表格是我拆完代码后整理出的文件与考点对应关系，仅供第一次阅读时参考：

这张表不需要背，它的意义在于建立“文件编号 → 算法方向”的映射感。以后你在OJ上看到PXXXX编号，扫一眼题目描述就能大致猜到出题人想考什么，这是刷题老手和新人之间最明显的差距。

2.2 为什么字符串匹配优先想到KMP而不是暴力

P1243.c这类字符串题，最容易翻车的做法是上来就写两层for循环暴力匹配。题目数据量小的时候暴力能过，但OJ后台的测试点里往往会塞一组长度10^5以上的文本串，暴力匹配的时间复杂度是O(n*m)，直接超时。KMP算法的核心价值在于把模式串的匹配过程从“每次失败从头再来”变成“利用已匹配信息跳着走”，时间复杂度稳定在O(n+m)。

常见做法是预处理模式串的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((n+m)log n)；多源全点对最短路用Floyd，O(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(n+m)的前提。main函数里用了while(scanf(...)!=EOF)是因为OJ题目常包含多组测试数据，漏掉这个循环会导致只跑第一组样例就结束，输出对不上。

参数方面，MAXN要留余量，如果题目说文本串长度不超过10^5，直接开10^6比较稳妥，避免数组越界段错误。位置从0还是从1计数看题目要求，我的代码返回的pos是0基下标，输出时加了1转成1基。

3.2 P1249动态规划：最长递增子序列的两种写法

P1249.c如果考的是最长递增子序列，最直观的做法是O(n^2)的经典DP：dp[i]表示以第i个元素结尾的最长递增子序列长度，每次向前扫描所有j<i，如果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 复杂度估错导致的TLE：O(n^2)卡死10^5数据

现象：算法逻辑完全正确，本地大数据也能跑，但OJ报Time Limit Exceeded。原因：题目n为10^5，O(n^2)的运算量是10^10，远超1秒。解决：提交前先估算数据规模下的运算量，超过10^7就得换更优算法。LIS的O(nlogn)二分优化、Dijkstra的堆优化、KMP替代暴力匹配，都是为这种场景准备的。这类坑最容易出现“看了答案觉得简单，自己写还是超时”的情况，所以平时练习就要养成先算复杂度的习惯。

4.5 全局变量忘清零：多组数据之间的脏数据污染

现象：第一组数据正确，第二组数据开始输出错乱。原因：全局数组在程序启动时确实自动初始化为0，但你在第一组数据处理过程中修改了它们，第二组数据进来时没有重新memset。解决：每组数据处理前，把用到的数组显式重置。dist数组用memset设置成0x3f，vis和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 done

gen、brute、opt三个二进制文件分别对应随机数据生成器、暴力解和优化解。注意gen里要用随机数生成符合题目范围的数据，包括边界值，比如n=1、n=最大值，不要只生成中间段数据。对拍脚本跑100组不挂，再提交OJ就会安心很多。这个技巧不止适用于这份题解，以后你自己刷所有OJ题目都用得上。

5.3 什么时候该看参考代码，什么时候必须自己死磕

参考题解的正确打开方式不是“直接看答案”，而是“先思考，再看答案，再不看答案重写”。我一般给自己定一个15分钟的计时：拿到题目先读题、画样例、写伪代码；15分钟后还没有可落地的思路，才翻开题解看开头部分，只看“解题思路”不看代码；如果看完思路能自己写出来，那这道题已经内化了大半。只有思路和代码都被卡住时才看完整参考代码，但看完必须合上文件手写复现一遍。这种策略让你既不会在难题上死磕到深夜，也不会因为轻易翻答案而丧失思考能力。

6. 让这份资源产生复利：把题解包改造成个人刷题清单

资源到手只是第一步，怎么让它持续产生价值才是关键。我建议你按一周循环的方式拆解这个题解包：每周挑三个文件，每个文件对应一个算法方向，周一研究P1243.c的KMP并复写，周三研究P1249.c的LIS并做二分优化，周五研究P1119.c的Dijkstra并试着手写堆优化。每道题做完之后，在一张表格里记录四件事：核心考点、时间复杂度、第一次提交是否AC、卡住的点是什么。

这张表就是你的错题本。研究题解时还可以做一步延伸：把AC代码里的关键参数改一改再提交，比如把KMP的next构建方式改成优化版（不连续回退），看看OJ判定结果有什么变化，这能帮你理解算法变体的边界。等到这份资源里的所有文件都过过一遍手，你会发现自己在面对新的P编号题目时，已经不太需要参考答案了。

最后说一个习惯：从那以后，我每次下载任何题解资源，都强制自己先归档、再复写、再对拍，最后回到OJ重新提交一遍完整流程，绝不停留在“看懂了”这个层面。算法这东西，看一眼是别人的，写一遍才是自己的，希望帮到你。

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