简介西工大在线编程比赛NOJ的116道赛题与解答汇编成一个Word文档适合备战校内竞赛、需要夯实算法与数据结构功底的读者。资源包为1个doc文件约303KB覆盖基础算法、数学计算、字符串处理、链表操作、排序及图论等常见题型每道题附参考代码可作刷题复盘和考前速查。已有224人学习目录与预览中的‘大数乘法/除法’‘插入排序’‘二分查找’‘创建职工链表’等体现了典型考点从入门练习到进阶思维均有涉及。Word版代码复制后可能存在格式异常需自行调整。整体来看这份题解集兼顾题目列表与代码演示既便于按题号检索也适合对照OJ环境反复练习有助于提升实际编程与调试能力。 “西工大noj 116题及答案word版.doc”——看到这个文件名估计不少在西工大上过程序设计通识课的同学都懂。NOJ是西工大的在线判题系统Online Judge课程平时作业、实验、甚至机试都少不了它。这份文档在各届学生之间流传有人拿它当作业答案有人当考前速背。作为一个从WA一路打到AC的老学长我更想说的是116道题真正值钱的不是最后那几行代码而是你亲手把它们写出来的过程。这篇博文我就结合自己刷NOJ的实际经历把这116题的题型分布、解题思路、常见报错状态、整理方法一次说清楚希望能让准备开始刷题的同学少走一点弯路。1. 先搞清楚NOJ和这116题到底是什么1.1 NOJ是什么为什么大家都在找NOJ全称Northwestern Polytechnical University Online Judge是西北工业大学自己维护的一套在线评测系统。简单说你把写好的C/C程序提交上去系统会自动编译运行用事先准备好的标准输入去测试你的程序再拿你程序的输出和标准答案做逐字符比对全对就给Accepted但凡差一个空格、多一个换行就会得到一个Wrong Answer或者Presentation Error。这种模式对刚学编程的同学来说是第一次真正体验到“程序是跑给机器看的不是写给老师看的”。老师改作业还可能看你写得认真给点印象分OJ系统完全没这个选项对就对错就错。所以很多人学C语言、学数据结构一大半时间都耗在了NOJ上。网上流传的“116题及答案word版”本质就是前人对这套题库的完整解答我当年也动过直接下载的心现在回头看真正靠把它啃完过关的人代码能力该落下还是落下。1.2 116题大致覆盖的知识点范围我按自己刷题的记忆和题库的常见编排方式粗过了一遍这116道题基本是围绕C语言和简单数据结构设计的分布大致是下面这样顺序结构题输入输出、四则运算、温度转换、求圆面积等约10道属于送分题但用来熟悉OJ的提交格式很合适。选择结构题判断闰年、成绩分档、三个数排序等练习if/else和switch约15道。循环结构题水仙花数、完数、九九乘法表、素数判断等约20道从这里开始才有真正的算法思想。数组与字符串冒泡排序、选择排序、矩阵转置、字符串逆序、字符统计约25道是题库的大头。函数与递归斐波那契、汉诺塔、最大公约数递归写法、函数传参约15道。结构体、指针、链表学生信息管理、链表建立与遍历约15道偏向综合应用。进制转换、高精度运算、递推与简单数学题剩余部分属于进阶内容。这些题型和大多数教材的章节是严格对应的。如果你只想要一份“答案”按这个清单去对号入座就行但如果你想真正把这个学期学扎实我建议把它当成一份刷题清单从易到难一路打过去。NOJ的难度梯度设置得比较友好前面的题基本一遍AC做到数组和字符串开始卡到链表和递归的时候彻底破防这几乎是所有人的心路历程。破防不可怕可怕的是破防之后直接掏出那份word文档复制粘贴——粘贴完了一学期期末机试照样不会写。2. 刷题的正确打开方式把题目变成能力2.1 先读懂题再谈算法很多同学刷NOJ第一步就错了。拿到题目看了一遍输入输出样例感觉“好像明白了”于是直接打开IDE写代码。写完一提交WA回头再看题才发现“输入的n可能是0到10的9次方不是题目例子里那么小”。这个过程浪费的时间最多。我自己读题有个习惯把三样东西圈出来。第一是数据范围第二是输入终止条件第三是输出格式。数据范围直接决定算法选型n不超过1000冒泡排序随便写n到了10的5次方就得想归并或者调用排序函数。输入终止条件决定循环怎么起止很多题写的是“输入到EOF”或者“以0结尾”搞错这个基本白做。输出格式决定printf里怎么拼空格和换行NOJ这类系统会逐字符比对输出比标准答案多一个空格都是错。2.2 本地能跑通不等于提交能通过NOJ和本地运行最大的区别在环境。本地用的可能是VS Code、Dev-COJ服务器上用的是GCC还会开比较严格的编译选项两种环境对同一段代码的宽容度完全不同。最典型的坑就是我大一踩过的两个一是有人喜欢在代码里写system(pause)用来防止本地控制台闪退忘了注释就直接提交了。在OJ上这个函数会让程序等待按键等于卡死在那里最后判一个Runtime Error或者超时。二是混用C和C的IO流scanf和cin混着写在某些编译环境下会出诡异问题轻则输出乱序重则编译报错。我自己现在写NOJ一律只用scanf/printf不用cin/cout省去一堆同步问题。所以从刷第一道题开始就要养成一个习惯每次提交前自己检查一遍代码里有没有本地调试遗留物。不要总觉得“我本地跑过了”就稳了OJ的判题环境才是最严格的那个“考官”。2.3 推荐一个稳的代码模板如果你还在用Dev-C或者VS Code建议在本地留一个通用模板每道题都从模板开始写。这样不是为了省事是为了避免低级错误#include stdio.h int main() { // 输入处理 // 计算逻辑 // 输出结果 return 0; }这里有一个必须养成的认知很多NOJ题目的输入是多组数据没有结束标志你必须用while (scanf(%d, n) ! EOF)或者while (scanf(%d, n) 1)来读取否则程序处理完一组就退出肯定WA。另外数组一律开得比题目上限大一点题目说n不超过1000你就开1005别卡着1000开避免循环边界处出现越界访问这种问题在本地偶尔跑不出来在OJ上就是Runtime Error。3. 三道典型题的全过程拆解3.1 入门题AB问题所有OJ的第一道题基本都是AB。不要觉得这道题简单就没价值它的核心价值在于让你搞明白“提交代码到在线判题到返回结果”的完整流程同时验证本地工具链是不是配好了。#include stdio.h int main() { int a, b; scanf(%d %d, a, b); printf(%d\n, a b); return 0; }注意几个细节scanf的格式串里两个%d之间写不写空格都能正确读入但建议和题目给的输入格式保持一致printf输出之后一定要带\n有些同学计算结果对了但是没换行在NOJ上会被判Presentation Error。这道题如果WA大概率不是你加法没学好而是哪一行多了分号、变量名敲错、或者把main写成了mian。这种错误谁都会犯关键是学会看编译报错信息别一报错就懵。3.2 经典题素数判断素数判断是循环结构里的必考题能演变出很多变体判断单个素数、统计区间内素数个数、分解质因数。核心解法其实不难#include stdio.h #include math.h int is_prime(int n) { if (n 1) return 0; if (n 2) return 1; if (n % 2 0) return 0; for (int i 3; i sqrt(n); i 2) { if (n % i 0) return 0; } return 1; } int main() { int n; scanf(%d, n); if (is_prime(n)) printf(Yes\n); else printf(No\n); return 0; }重点说说为什么只判断到sqrt(n)就足够如果n存在一个大于sqrt(n)的因子那它必然配一个小于sqrt(n)的因子只要小的那个不存在大的那个也就不可能存在。所以判断到平方根就完全覆盖了所有可能性。这个优化在n很小的时候看不出差别n到了100万、1000万量级直接就把O(n)降成了O(√n)是实打实的效率提升。另外注意要#include math.h并且有些本地环境需要手动加链接库否则sqrt用不了。这也是一个常见的本地能编译、一提交就Compile Error的坑。3.3 递归必考题斐波那契数列斐波那契数列是函数与递归章节的常客NOJ里甚至可能出两遍一遍要求循环实现一遍要求递归实现。最简单的递归写法是这样#include stdio.h int fib(int n) { if (n 1 || n 2) return 1; return fib(n - 1) fib(n - 2); } int main() { int n; scanf(%d, n); printf(%d\n, fib(n)); return 0; }这版代码逻辑完全正确却藏着一个非常大的性能坑递归计算fib(50)函数调用的次数是按指数增长的跑完能等到你怀疑人生。所以如果题目要求的n比较大这个写法提交上去基本就是TLE超时没商量。这时候要换思路用循环递推维护两个变量或者用一个数组做记忆化把已经算过的fib(i)存下来。我个人建议在学递归这一章就养成“先写递归公式再想想能不能用循环递推实现”的习惯这对后面学动态规划特别有帮助——很多动态规划题本质就是“递归思路 空间换时间”。4. 判题系统返回状态每一种都对应一种病4.1 常见状态与排查方向NOJ和一众OJ系统一样提交后会返回一个状态码。新手最需要认识的就是这张表状态含义最可能的原因Accepted (AC)通过恭喜这题过了Compile Error (CE)编译错误语法错误、头文件缺失、main拼写错误Wrong Answer (WA)答案错误算法逻辑有误、数据范围没考虑、多组输入没处理Presentation Error (PE)格式错误输出和标准答案有出入多空格少换行Time Limit Exceeded (TLE)运行超时算法太慢、死循环、递归过深爆栈Runtime Error (RE)运行错误数组越界、除零、未初始化变量、残留system(pause)Memory Limit Exceeded (MLE)内存超限数组开得过大比如开了不会用到的int[10000000]4.2 我踩过的几个典型坑我印象最深的一次WA是处理多组输入时用了全局变量存结果却忘记在每组数据开始前清零。第一组数据算对了第二组数据的结果被上一组残留值污染输出全错。这类问题自测很难发现因为本地测试时你往往只跑一组数据跑不出这个bug。后来我养成一个习惯题目如果有样例输入一定把样例全跑一遍如果没给多组样例就自己造几组边界数据试试比如n取0、取最大值、取负值。另一个大坑是浮点精度。有的题目要求输出保留两位小数你算出来的结果是2.675printf(%.2f)输出却可能是2.67原因在于浮点数在计算机里是二进制近似存储2.675在二进制里并不是精确值。解决办法是不要用浮点数做精确比较或者用整数运算来替代比如先乘以100四舍五入再输出。这个坑非常隐蔽很多人刷到AC率接近95%就再也上不去了往往就是被这类精度问题卡的。5. 整理一份真正属于自己的“116题文档”5.1 为什么不要直接抄别人那份答案说实话网上流传的那份“116题及答案word版”我也看过质量参差不齐有些注释确实写得不错有些也就是帖子搬运的个别题目的写法还不一定是最优解。更重要的是作业可以抄期末考试和机试没法抄。NOJ这种系统很多课程是计入平时成绩的老师从后台能看到每个学生的提交时间、错误次数、调试间隔一个人是不是在短时间内从零提交变成连续AC基本一目了然。我完全理解想找答案的心情但更推荐的做法是先自己做一遍再打开别人的代码对照重点看差异在哪里。如果你能注意到“他这里用指针访问数组比我用下标访问效率高在哪里”说明你已经在真正理解程序了。到了这个阶段那份word文档才有它的真正价值——作为对照和复盘材料而不是替你写作业的工具。5.2 我的文档组织方法我自己当年也整理了一份类似的word文档但不是单纯抄答案而是每道题都记录了四部分题目大意、我的思路含时间复杂度分析、最终通过的代码、提交中踩过的坑。文件名也按“编号_知识点_题目名”的规则来起比如“011_循环_水仙花数”“045_数组_选择排序”。这样期末复习的时候不用从第一题重新刷直接按知识点找到自己薄弱的部分一天就能过完整套重点题。再分享一个小技巧把每次WA的原因记在代码注释里一行就够。比如“这里第3个样例WA因为没有处理n0的情况”。这些备注看着小积少成多之后就成了个人专属的错题本。后来我去参加面试手写算法题时最怀念的反而不是什么高端竞赛经验而是大一在NOJ上一次又一次WA和AC之间折腾时攒下来的那些细节。那才是刷题真正留给你的东西。本文还有配套的精品资源点击获取 西工大NOJ 116题刷题指南：从WA到AC的C语言编程实战经验
简介西工大在线编程比赛NOJ的116道赛题与解答汇编成一个Word文档适合备战校内竞赛、需要夯实算法与数据结构功底的读者。资源包为1个doc文件约303KB覆盖基础算法、数学计算、字符串处理、链表操作、排序及图论等常见题型每道题附参考代码可作刷题复盘和考前速查。已有224人学习目录与预览中的‘大数乘法/除法’‘插入排序’‘二分查找’‘创建职工链表’等体现了典型考点从入门练习到进阶思维均有涉及。Word版代码复制后可能存在格式异常需自行调整。整体来看这份题解集兼顾题目列表与代码演示既便于按题号检索也适合对照OJ环境反复练习有助于提升实际编程与调试能力。 “西工大noj 116题及答案word版.doc”——看到这个文件名估计不少在西工大上过程序设计通识课的同学都懂。NOJ是西工大的在线判题系统Online Judge课程平时作业、实验、甚至机试都少不了它。这份文档在各届学生之间流传有人拿它当作业答案有人当考前速背。作为一个从WA一路打到AC的老学长我更想说的是116道题真正值钱的不是最后那几行代码而是你亲手把它们写出来的过程。这篇博文我就结合自己刷NOJ的实际经历把这116题的题型分布、解题思路、常见报错状态、整理方法一次说清楚希望能让准备开始刷题的同学少走一点弯路。1. 先搞清楚NOJ和这116题到底是什么1.1 NOJ是什么为什么大家都在找NOJ全称Northwestern Polytechnical University Online Judge是西北工业大学自己维护的一套在线评测系统。简单说你把写好的C/C程序提交上去系统会自动编译运行用事先准备好的标准输入去测试你的程序再拿你程序的输出和标准答案做逐字符比对全对就给Accepted但凡差一个空格、多一个换行就会得到一个Wrong Answer或者Presentation Error。这种模式对刚学编程的同学来说是第一次真正体验到“程序是跑给机器看的不是写给老师看的”。老师改作业还可能看你写得认真给点印象分OJ系统完全没这个选项对就对错就错。所以很多人学C语言、学数据结构一大半时间都耗在了NOJ上。网上流传的“116题及答案word版”本质就是前人对这套题库的完整解答我当年也动过直接下载的心现在回头看真正靠把它啃完过关的人代码能力该落下还是落下。1.2 116题大致覆盖的知识点范围我按自己刷题的记忆和题库的常见编排方式粗过了一遍这116道题基本是围绕C语言和简单数据结构设计的分布大致是下面这样顺序结构题输入输出、四则运算、温度转换、求圆面积等约10道属于送分题但用来熟悉OJ的提交格式很合适。选择结构题判断闰年、成绩分档、三个数排序等练习if/else和switch约15道。循环结构题水仙花数、完数、九九乘法表、素数判断等约20道从这里开始才有真正的算法思想。数组与字符串冒泡排序、选择排序、矩阵转置、字符串逆序、字符统计约25道是题库的大头。函数与递归斐波那契、汉诺塔、最大公约数递归写法、函数传参约15道。结构体、指针、链表学生信息管理、链表建立与遍历约15道偏向综合应用。进制转换、高精度运算、递推与简单数学题剩余部分属于进阶内容。这些题型和大多数教材的章节是严格对应的。如果你只想要一份“答案”按这个清单去对号入座就行但如果你想真正把这个学期学扎实我建议把它当成一份刷题清单从易到难一路打过去。NOJ的难度梯度设置得比较友好前面的题基本一遍AC做到数组和字符串开始卡到链表和递归的时候彻底破防这几乎是所有人的心路历程。破防不可怕可怕的是破防之后直接掏出那份word文档复制粘贴——粘贴完了一学期期末机试照样不会写。2. 刷题的正确打开方式把题目变成能力2.1 先读懂题再谈算法很多同学刷NOJ第一步就错了。拿到题目看了一遍输入输出样例感觉“好像明白了”于是直接打开IDE写代码。写完一提交WA回头再看题才发现“输入的n可能是0到10的9次方不是题目例子里那么小”。这个过程浪费的时间最多。我自己读题有个习惯把三样东西圈出来。第一是数据范围第二是输入终止条件第三是输出格式。数据范围直接决定算法选型n不超过1000冒泡排序随便写n到了10的5次方就得想归并或者调用排序函数。输入终止条件决定循环怎么起止很多题写的是“输入到EOF”或者“以0结尾”搞错这个基本白做。输出格式决定printf里怎么拼空格和换行NOJ这类系统会逐字符比对输出比标准答案多一个空格都是错。2.2 本地能跑通不等于提交能通过NOJ和本地运行最大的区别在环境。本地用的可能是VS Code、Dev-COJ服务器上用的是GCC还会开比较严格的编译选项两种环境对同一段代码的宽容度完全不同。最典型的坑就是我大一踩过的两个一是有人喜欢在代码里写system(pause)用来防止本地控制台闪退忘了注释就直接提交了。在OJ上这个函数会让程序等待按键等于卡死在那里最后判一个Runtime Error或者超时。二是混用C和C的IO流scanf和cin混着写在某些编译环境下会出诡异问题轻则输出乱序重则编译报错。我自己现在写NOJ一律只用scanf/printf不用cin/cout省去一堆同步问题。所以从刷第一道题开始就要养成一个习惯每次提交前自己检查一遍代码里有没有本地调试遗留物。不要总觉得“我本地跑过了”就稳了OJ的判题环境才是最严格的那个“考官”。2.3 推荐一个稳的代码模板如果你还在用Dev-C或者VS Code建议在本地留一个通用模板每道题都从模板开始写。这样不是为了省事是为了避免低级错误#include stdio.h int main() { // 输入处理 // 计算逻辑 // 输出结果 return 0; }这里有一个必须养成的认知很多NOJ题目的输入是多组数据没有结束标志你必须用while (scanf(%d, n) ! EOF)或者while (scanf(%d, n) 1)来读取否则程序处理完一组就退出肯定WA。另外数组一律开得比题目上限大一点题目说n不超过1000你就开1005别卡着1000开避免循环边界处出现越界访问这种问题在本地偶尔跑不出来在OJ上就是Runtime Error。3. 三道典型题的全过程拆解3.1 入门题AB问题所有OJ的第一道题基本都是AB。不要觉得这道题简单就没价值它的核心价值在于让你搞明白“提交代码到在线判题到返回结果”的完整流程同时验证本地工具链是不是配好了。#include stdio.h int main() { int a, b; scanf(%d %d, a, b); printf(%d\n, a b); return 0; }注意几个细节scanf的格式串里两个%d之间写不写空格都能正确读入但建议和题目给的输入格式保持一致printf输出之后一定要带\n有些同学计算结果对了但是没换行在NOJ上会被判Presentation Error。这道题如果WA大概率不是你加法没学好而是哪一行多了分号、变量名敲错、或者把main写成了mian。这种错误谁都会犯关键是学会看编译报错信息别一报错就懵。3.2 经典题素数判断素数判断是循环结构里的必考题能演变出很多变体判断单个素数、统计区间内素数个数、分解质因数。核心解法其实不难#include stdio.h #include math.h int is_prime(int n) { if (n 1) return 0; if (n 2) return 1; if (n % 2 0) return 0; for (int i 3; i sqrt(n); i 2) { if (n % i 0) return 0; } return 1; } int main() { int n; scanf(%d, n); if (is_prime(n)) printf(Yes\n); else printf(No\n); return 0; }重点说说为什么只判断到sqrt(n)就足够如果n存在一个大于sqrt(n)的因子那它必然配一个小于sqrt(n)的因子只要小的那个不存在大的那个也就不可能存在。所以判断到平方根就完全覆盖了所有可能性。这个优化在n很小的时候看不出差别n到了100万、1000万量级直接就把O(n)降成了O(√n)是实打实的效率提升。另外注意要#include math.h并且有些本地环境需要手动加链接库否则sqrt用不了。这也是一个常见的本地能编译、一提交就Compile Error的坑。3.3 递归必考题斐波那契数列斐波那契数列是函数与递归章节的常客NOJ里甚至可能出两遍一遍要求循环实现一遍要求递归实现。最简单的递归写法是这样#include stdio.h int fib(int n) { if (n 1 || n 2) return 1; return fib(n - 1) fib(n - 2); } int main() { int n; scanf(%d, n); printf(%d\n, fib(n)); return 0; }这版代码逻辑完全正确却藏着一个非常大的性能坑递归计算fib(50)函数调用的次数是按指数增长的跑完能等到你怀疑人生。所以如果题目要求的n比较大这个写法提交上去基本就是TLE超时没商量。这时候要换思路用循环递推维护两个变量或者用一个数组做记忆化把已经算过的fib(i)存下来。我个人建议在学递归这一章就养成“先写递归公式再想想能不能用循环递推实现”的习惯这对后面学动态规划特别有帮助——很多动态规划题本质就是“递归思路 空间换时间”。4. 判题系统返回状态每一种都对应一种病4.1 常见状态与排查方向NOJ和一众OJ系统一样提交后会返回一个状态码。新手最需要认识的就是这张表状态含义最可能的原因Accepted (AC)通过恭喜这题过了Compile Error (CE)编译错误语法错误、头文件缺失、main拼写错误Wrong Answer (WA)答案错误算法逻辑有误、数据范围没考虑、多组输入没处理Presentation Error (PE)格式错误输出和标准答案有出入多空格少换行Time Limit Exceeded (TLE)运行超时算法太慢、死循环、递归过深爆栈Runtime Error (RE)运行错误数组越界、除零、未初始化变量、残留system(pause)Memory Limit Exceeded (MLE)内存超限数组开得过大比如开了不会用到的int[10000000]4.2 我踩过的几个典型坑我印象最深的一次WA是处理多组输入时用了全局变量存结果却忘记在每组数据开始前清零。第一组数据算对了第二组数据的结果被上一组残留值污染输出全错。这类问题自测很难发现因为本地测试时你往往只跑一组数据跑不出这个bug。后来我养成一个习惯题目如果有样例输入一定把样例全跑一遍如果没给多组样例就自己造几组边界数据试试比如n取0、取最大值、取负值。另一个大坑是浮点精度。有的题目要求输出保留两位小数你算出来的结果是2.675printf(%.2f)输出却可能是2.67原因在于浮点数在计算机里是二进制近似存储2.675在二进制里并不是精确值。解决办法是不要用浮点数做精确比较或者用整数运算来替代比如先乘以100四舍五入再输出。这个坑非常隐蔽很多人刷到AC率接近95%就再也上不去了往往就是被这类精度问题卡的。5. 整理一份真正属于自己的“116题文档”5.1 为什么不要直接抄别人那份答案说实话网上流传的那份“116题及答案word版”我也看过质量参差不齐有些注释确实写得不错有些也就是帖子搬运的个别题目的写法还不一定是最优解。更重要的是作业可以抄期末考试和机试没法抄。NOJ这种系统很多课程是计入平时成绩的老师从后台能看到每个学生的提交时间、错误次数、调试间隔一个人是不是在短时间内从零提交变成连续AC基本一目了然。我完全理解想找答案的心情但更推荐的做法是先自己做一遍再打开别人的代码对照重点看差异在哪里。如果你能注意到“他这里用指针访问数组比我用下标访问效率高在哪里”说明你已经在真正理解程序了。到了这个阶段那份word文档才有它的真正价值——作为对照和复盘材料而不是替你写作业的工具。5.2 我的文档组织方法我自己当年也整理了一份类似的word文档但不是单纯抄答案而是每道题都记录了四部分题目大意、我的思路含时间复杂度分析、最终通过的代码、提交中踩过的坑。文件名也按“编号_知识点_题目名”的规则来起比如“011_循环_水仙花数”“045_数组_选择排序”。这样期末复习的时候不用从第一题重新刷直接按知识点找到自己薄弱的部分一天就能过完整套重点题。再分享一个小技巧把每次WA的原因记在代码注释里一行就够。比如“这里第3个样例WA因为没有处理n0的情况”。这些备注看着小积少成多之后就成了个人专属的错题本。后来我去参加面试手写算法题时最怀念的反而不是什么高端竞赛经验而是大一在NOJ上一次又一次WA和AC之间折腾时攒下来的那些细节。那才是刷题真正留给你的东西。本文还有配套的精品资源点击获取