西北工业大学NOJ平台题解（C/C++语言版）总结

发表于 更新于

文章内容简介

如题，西北工业大学的NOJ题目除了几道题我还没办法完成以外，其他的题目我都已经AC了，在完成题目的过程中，我发现一些很有意思的题目，学到了一些很有意思的知识，当然也踩到了很多题目的坑，发现了一些题目的错误，现将个人经验写作博客，供大家参考。

以下我会给出我的所有题解代码，代码部分为C语言，部分为C++语言，其中C++语言写题主要是为了使用STL以引用一些常见的数据结构，所以为了照顾只使用C语言的答题者，我会给出STL常用数据结构的C语言实现方式。我的代码在必要的位置会有注释，帮助大家理解。

同时，正如各位所见，有些题目的描述存在模糊的问题，甚至有错误，接下来我也会将这些错误尽数列出，防止各位踩坑。

上述内容由我个人总结（当然也要感谢各位指导我的老师和同学），不是官方题解，难免存在错误，若你在阅读过程中发现任何错误或有质疑意见，亦或者是想向我提问，在博客下方评论区评论或在Gitee仓库发表Issue来向我反映，个人将感激不尽。

总览

注：只想下载代码的点击这里跳转到下载区。

题目列表

由于NOJ平台每10题存在乱序现象，故基于我的个人情况给出题目列表，第n题对应题解文件中noj-n.c或noj-n.cpp。

博客不提供题面信息，一道一道题目截图工作量太大，且个人博客流量包并不多，请谅解。

下题中，加粗的题目表示这是我推荐做的题目；
标注未完成的题目是我因为某些原因没做完的题目；
标注需要注意的题目是我认为这道题有一些需要注意的地方的题目；
标注描述模糊的题目是我认为这道题描述有令人误解的地方的题目；
标注出现错误的题目是我认为这道题的题干或测试点存在错误的题目；

有下划线标记的题目，代表我已经写了有关于它们的解析，欢迎各位阅读交流。

1-10题

  1. Hello World
  2. A+B
  3. 数据类型大小及范围
  4. 平均值
  5. 进制转换
  6. 浮点数输出
  7. 动态宽度输出
  8. 计算地球上两点之间的距离
  9. 风寒指数
  10. 颜色模型转换 （需要注意）

11-20题

  1. 乘数模
  2. 方阵
  3. 对称数 （出现错误）
  4. 倍数和 （出现错误）
  5. 幂数模
  6. 组合数
  7. 分数的加减乘除法
  8. 比率
  9. 操作数
  10. 级数和 （需要注意）

21-30题

  1. 余数和
  2. 好数字
  3. 竖式乘法
  4. 毕达哥拉斯三元组
  5. 方案数
  6. 最大数字
  7. 阶乘倍数
  8. 俄罗斯农夫乘法
  9. 查找数列
  10. 倒水

31-40题

  1. 可变参数累加
  2. 冰雹序列
  3. 素数
  4. 佩尔数
  5. 可变参数平均
  6. 基思数
  7. 二进制表示
  8. 运动会
  9. 哈沙德数
  10. 光线追踪

41-50题

  1. 蒙特卡罗方法求积分 （出现错误）
  2. 回文数之和
  3. 航空旅行
  4. 飞机起飞速度 （未完成）
  5. 完美矩阵 （出现错误）
  6. 货运优化
  7. 素数筛选法
  8. 稀疏矩阵 （描述模糊）
  9. 波士顿房价预测
  10. 行列式值

51-60题

  1. Atol转换
  2. 分离字符串
  3. 字符串切片
  4. 字符串后缀
  5. 元宇宙A+B
  6. Kids A+B
  7. 字符串替换 （未完成）
  8. 前后缀移除
  9. 大小写交换
  10. 删除前后缀

61-70题

  1. 有效表达式
  2. 三元搜索
  3. 循环排序
  4. GPS通讯协议 （未完成）
  5. Arduino显示
  6. 加密字串
  7. PID控制
  8. 时钟A-B
  9. DNA双螺旋结构
  10. 长安 （描述模糊）

71-80题

  1. 火箭发射模拟 （出现错误）
  2. 水下声学定位 （需要注意）
  3. 原子计数
  4. 中位数
  5. 卫星定位
  6. 热能计算 （出现错误）
  7. 成绩单
  8. 几何约束
  9. 晶体结构
  10. 日出日落时间 （未完成）

81-90题

  1. 三角形
  2. 和字符串 （未完成）
  3. 游乐园
  4. 危险的组合
  5. 汤包
  6. 打字机
  7. 子数组最大和
  8. 上楼梯
  9. 绝对差
  10. 挑选

91-100题

  1. 气体扩散
  2. 平方根
  3. 圆周率
  4. 机场翻牌显示
  5. 空中交通管制
  6. 阿克曼函数
  7. 重复元素
  8. 零钞
  9. 左右操作
  10. 马赫数

推荐做的题目

(11-20) 乘数模&幂数模

涉及知识点：循环取余和快速幂算法，大数处理

(11-20) 组合数

涉及知识点：动态规划

(21-30) 方案数

涉及知识点：双指针

(21-30) 阶乘倍数

涉及知识点：最大公约数，质因数分解

(21-30) 俄罗斯农夫乘法

涉及知识点：位运算

(21-30) 倒水

涉及知识点：广度优先搜索

(31-40) 素数

涉及知识点：Eratosthenes筛法
推荐做完这道题再做素数筛选法，Euler筛法是Eratosthenes筛法的优化

(31-40) 二进制表示

涉及知识点：递归&分治

(31-40) 运动会

涉及知识点：Euler函数，互质

(31-40) 光线追踪

涉及知识点：递归&迭代

(41-50) 货运优化

涉及知识点：贪心

(41-50) 素数筛选法

涉及知识点：Euler筛法

(51-60) Atol转换

涉及知识点：状态机

(61-70) 长安

涉及知识点：排列组合
推荐做完这道题再做有效表达式这道题

(61-70) 有效表达式

涉及知识点：Catalan数列，排列组合

(71-80) 原子计数

涉及知识点：哈希表

(71-80) 几何约束

因为我是搞游戏开发的，所以我推荐这道题，这道题可以用游戏算法中一种非常常见的碰撞判定方法：SAT投影轴算法解决。

(81-90)

这一整套题都很有意思，都写写试试，里面的算法很实用。（其实里面的题目你可以在其它的刷题网站如LeetCode找到原题）

需要注意的题目

(1-10) 颜色模型转换

题目中，R G B的值属于[0, 1]而非[0, 255]，计算时需注意。

(11-20) 级数和

如果某一项小数有后缀0，则应当消除之，例如9.10应当输出为9.1

(71-80) 水下声学定位

1
2
3
4
// 我压根不知道我的算法为什么过不了，先复制一个别人的算法在这里，之后我再解释为什么它是成立的
// 参考对象：https://blog.csdn.net/annesede/article/details/133761873
double angle = (4 * area) / (pow(lenBC, 2) + pow(lenDA, 2) - pow(lenAB, 2) - pow(lenCD, 2));
return atan(angle) * 180.0 / acos(-1);

我在此复制了其他人关于夹角的计算方法，有无大佬帮忙解释这为什么成立？谢谢。

描述模糊的题目

(41-50) 稀疏矩阵

这道题的题目条件给的很模糊（大致满足是什么鬼），完美矩阵满足非0元素个数占比小于0.05或个数等于行或列满足一个即可。

1
2
3
4
if ((double)nonZeroCnt / (double)totalNumCnt <= 0.05 ||
nonZeroCnt == column || nonZeroCnt == row) {
    printf("Yes");
}

(61-70) 长安

这道题目说明不够清楚，动点一开始实际上处于(1, 1)的位置而非(0, 0)

1
2
3
4
5
6
7
8
9
10
// 尤其注意！起始点坐标为(1, 1)而非(0, 0)，出的什么破题，这都不说清楚
long long getPathCnt() {
    long long result = 0;
    result += getFactorial(pointBY + pointBX - 2) / getFactorial(pointBY - 1) / getFactorial(pointBX - 1);
    if (pointPY <= pointBY && pointPX <= pointBX) {
        result -= getFactorial(pointPY + pointPX - 2) / getFactorial(pointPY - 1) / getFactorial(pointPX - 1) *
        getFactorial(pointBY - pointPY + pointBX - pointPX) / getFactorial(pointBY - pointPY) / getFactorial(pointBX - pointPX);
    }
    return result;
}

从上文可以看出我其实有点生气了（

出现错误的题目

(11-20) 倍数和

题目中存在越界的测试用例，使用int类型储存结果并输出可以得到正确答案，而long long类型储存结果会WA。

(11-20) 对称数

一个数旋转一周肯定还是自己啊，这道题的实际意思是把一个数旋转180度，即半周，题目描述有错。

(41-50) 蒙特卡罗方法求积分

题目中描述“样本数量为N”，但实际上测试用例的样本量为N-1，只有取N-1个样本才能够AC。

1
2
3
4
5
6
7
8
9
10
11
12
// 请注意，取样本的循环次数为(times - 1)
for (int i = 1; i < times; i++) {
    double randResult = (double)rand() / RAND_MAX;
    double curr = left + (right - left) * randResult;
    switch (type) {
        case 1: currResult += function1(curr); break;
        case 2: currResult += function2(curr); break;
        case 3: currResult += function3(curr); break;
        case 4: currResult += function4(curr); break;
        case 5: currResult += function5(curr); break;
    }
}

(41-50) 完美矩阵

题目中漏给了条件，满足基本题意的子矩阵还必须是方阵，这也能够解释为什么第二个示例中的完美矩阵只有两个。

1
2
3
4
5
6
7
8
9
10
// 用三个循环嵌套来遍历所有*方阵*
int result = 0;
for (int leftEdge = 0; leftEdge < column; leftEdge++) {
    for (int upEdge = 0; upEdge < row; upEdge++) {
        for (int width = 1; (leftEdge + width < column) &&
        (upEdge + width < row); width++) {
            result += isPerfectMatrix(leftEdge, upEdge, leftEdge + width, upEdge + width);
        }
    }
}

(71-80) 火箭发射模拟

题目中关于加速的的计算公式为accelerate = thrust / massTotal - gravity，但是测试用例的结果基于accelerate = thrust / massTotal得到，即测试用例漏掉了重力。

1
2
3
4
5
6
7
8
while (currTime < totalTime) {
    double accelerate = thrust / massTotal - gravity;
    // 可是按道理应该是这样的，结果却是把gravity去掉才能AC？
    velocity += accelerate * TIMESTEP;
    result += velocity * TIMESTEP;
    massTotal -= fuelDecrease * TIMESTEP;
    currTime += TIMESTEP;
}

没有重力的火箭只在蕾米莉亚·斯卡雷特一行人登月的时候我才见过，这里是幻想乡？

(71-80) 热能计算

请看测试用例：0.30%和0.70%实际上对应两方面热能占比为30%和70%，所以这道题输出的并非百分数，只是在结果的小数后方加上了百分号而已。

未完成的题目

41-50题

  • 飞机起飞速度（图表不知道怎么看，也不想看）

51-60题

  • 字符串替换（因为不明原因WA）

61-70题

  • GPS通讯协议（题目描述过于复杂，不想写）

71-80题

  • 日出日落时间（题目中NOAA算法下载链接失效）

81-90题

  • 和字符串（读不懂题，不知道有没有人能解释一下给我听~）

代码题解区

代码下载

点击此处在我的博客直接下载

点击此处跳转到Gitee下载

题解列表

  1. 西北工业大学NOJ平台：(61-70)长安&有效表达式题解
  2. 西北工业大学NOJ平台：质数与分解质因数专题（共4篇题解）
  3. 西北工业大学NOJ平台：大数处理专题（共2篇题解）
  4. 西北工业大学NOJ平台：行列式值

我之后会针对一些很有意思的题目写题解，之后博文的链接会放在这里

C语言实现C++的STL与Algorithm库功能

之后更新，Coming Soon。

说明

所有代码若存在引用其它代码/代码片段情况，均已在注释中表明，后面我会整理一份引用清单，感谢其它开源老哥的支持。

禁止将从此处下载的代码用作非学习用途，例如倒卖商用等，感谢您的支持。

祝读者编程能力++，学业进步！