清华电子系数算 OJ 通关指北

写在基石前面

下面这段话来自于 NJU 计算机系统概论 PA 文档，值得一读。

基础设施 - 提高项目开发的效率
在PA中, 基础设施是指支撑项目开发的各种工具和手段. 原则上基础设施并不属于课本知识的范畴, 但是作为一个有一定规模的项目, 基础设施的好坏会影响到项目的推进, 甚至决定项目的成败, 这是你在程序设计课上体会不到的.

事实上, 你已经体会过基础设施给你带来的便利了. 我们的框架代码已经提供了Makefile来对NEMU进行一键编译. 假设我们并没有提供一键编译的功能, 你需要通过手动键入gcc命令的方式来编译源文件: 假设你手动输入一条gcc命令需要10秒的时间(你还需要输入很多编译选项, 能用10秒输入完已经是非常快的了), 而NEMU工程下有30个源文件, 为了编译出NEMU的可执行文件, 你需要花费多少时间? 然而你还需要在开发NEMU的过程中不断进行编译, 假设你需要编译500次NEMU才能完成PA, 一学期下来, 你仅仅花在键入编译命令上的时间有多少?

有的项目即使使用工具也需要花费较多时间来构建. 例如硬件开发平台vivado/quartus一般需要花费半小时到一小时不等的时间来生成比特文件, 也就是说, 你编写完代码之后, 可能需要等待一小时之后才能验证你的代码是否正确. 这是因为, 这个过程不像编译程序这么简单, 其中需要处理很多算法上的NPC问题. 为了生成一个质量还不错的比特文件, 硬件开发工具需要付出比gcc更大的代价来解决这些NPC问题. 这时候基础设施的作用就更加重要了, 如果能有工具可以帮助你一次进行多个方面的验证, 就会帮助你节省下来无数个”一小时”.

Google内部的开发团队非常重视基础设施的建设, 他们把可以让一个项目得益的工具称为Adder, 把可以让多个项目得益的工具称为Multiplier. 顾名思义, 这些工具可以成倍提高项目开发的效率. 在学术界, 不少科研工作的目标也是提高开发效率, 例如bug自动检测和修复, 自动化验证, 易于开发的编程模型等等. 在PA中, 基础设施也会体现在不同的方面, 我们会在将来对其它方面进行讨论.

你将来肯定会参与比PA更大的项目, 如何提高项目开发的效率也是一个很重要的问题. 希望在完成PA的过程中, 你能够对基础设施有新的认识: 有代码的地方, 就有基础设施. 随着知识的积累, 将来的你或许也会投入到这些未知的领域当中, 为全世界的开发者作出自己的贡献.

面对数算OJ如同黑盒一般的测试，“基础设施”的重要性更是不言而喻，而电子系程设课程很难说给你搭下了足够的基础。为了高效的解决挑战OJ时所遇到的各种问题，你还需要补充下面的一些知识

基石

调试

利用工具
机器永远比人效率高，机器永远比人准确，比起瞪眼盯着自己写的低质量的代码半天看不出来个所以然，不如交给机器分步运行程序，自己则坐在一旁观察程序运行状态的变化来 Debug。

使用现代调试工具几乎是你想要通过OJ所必须要掌握的技能。程设课上所使用的 Visual Studio 自带调试工具，不过笔者对其了解不够深入。
笔者一般使用 vscode 插件，配合 gdb 调试工具进行调试。vscode 的可视化界面做的不错，但是亦有一些缺点（需要手动查看全局变量，而且条件断点在哪里设置不太好找）。
另外，如果你会使用 g++ 或者 clang++ 之类的编译器进行手动编译，或者改 vscode 的配置文件来添加编译选项，那么我强烈推荐在编译选项中加入 -fsanitize=address 和 -g，这样如果程序出现了数组越界，访问空指针等非法操作，程序会自动中断并且反馈信息（会反馈的时候出现问题时程序执行到的位置），这有利于解决 RE 相关的错误
使用assert
在程序中使用 assert 宏来对程序的运行状况作出限定，能够更早的将问题暴露出来（譬如在访问 a[n] 前用 assert 检测 n 是否超出了数组范围，或者进行空指针检查，这样能比较好的追踪非法访问内存所产生的问题）

随机样例生成和 DiffTest

学会写python
python 是一种非常易用易学的编程语言，在这里你不用总是关心数组越界，int 溢出等问题，也不用被 c 和 c++ 里面一些不易用的东西困扰。用这样的一门语言写一些临时的小工具是相当好用的（比如后文将会提到的随机样例生成器）。
自己造样例
OJ 平台上所用的测试数据是不公开的，而自己手造样例仅仅在数据范围很小的时候可行（而且经常很烦人）。为了使用量大且复杂的数据对代码在本地进行测试（同时使用测试工具追踪 WA 或者 RE），自己手捏一个随机样例生成器相当重要。你还可以将生成器进行调教调整以生成不同特征的样例，进行针对性的测试

DiffTest
DiffTest，中文叫差分测试，俗称对拍，说白了就是找个“能保证结果是对的”程序，和我们自己写的程序的输出做对比，以此来发现问题所在。这点可以和随机样例测试结合起来，因为手算随机大样例的结果往往是不可行的。此外，有的时候程序仅在少数情况下结果出错，就更需要我们进行输出结果的对比，获得使得程序出错的样例，再使用调试工具进行进一步的检查。

STL 标准模板库

C++ 提供了很多好用的数据结构和函数的模板，你可以在笔者后几个 OJ 的代码中找到他们的影子。
标准模板库帮你解决了很多问题，比如数组的排序可以使用 algorithm 头文件中的 std::sort() 函数来解决（可以搭配 lambda function）。
当然 STL 的用法太多了，有的时候也不一定适用于题目（可能带来额外的开销，这在内存寸土寸金的电子系 OJ 中不见得是一件好事），需要具体问题具体分析

增加代码的可读性

别随便命名
总有人喜欢用 abcd 或者中文拼音对变量或者函数命名，但是这种不能一眼看懂的命名往往会导致致命性的效率下降（总有一天你会忘记自己命名的 abcd 代指的是什么，或者是想要和别人讨论自己的代码）
在这里笔者推荐两种常见的命名方法：

驼峰命名法

对于函数，类等的命名，每个单词首字母大写
譬如 GetVal, PriorityQueue
对于变量的命名，第一个单词首字母小写，后面的单词首字母大写
譬如 playerBlood，matrixIndex

下划线命名法

每个单词中间用下划线分割开来
比如 player_blood，get_val

善用宏和函数
假如你要求两个数的最大值，你第一时间想到的可能是

int max_num = a < b ? b : a;

那假如你要重复使用最大值的功能呢？

int max_num = a < b ? b : a;
max_num = c < h ? h : c;
max_num = d < i ? i : d;
max_num = e < j ? j : e;
max_num = f < k ? k : f;
max_num = g < l ? l : g;

你可能已经发现了，如果你要重复多次求不同的数对的最大值，写这样的一条表达式是一件非常痛苦的事情，而且这样的代码可读性很差
有的人这个时候可能想到使用函数

int max(int a,int b)
{
    return a < b ? b : a;
}

int main()
{
    max_num = max(a,b);
    max_num = max(c,h);
    max_num = max(d,i);
    max_num = max(e,j);
    max_num = max(f,k);
    max_num = max(g,l);
}

这样写起来简单，而且 max 函数的作用一目了然
对于求最大值这样比较简单的操作还可以使用宏替换
（使用宏的时候尽量全大写，并且使用下划线分割单词）
（一定要注意使用宏的规范性，避免遇到一些难以调试的问题）
（如果用的不好，甚至建议就不要使用宏替换了）

#define MAX(a,b) ((a) < (b) ? (b) : (a))
int main()
{
    max_num = MAX(a,b);
    max_num = MAX(c,h);
    max_num = MAX(d,i);
    max_num = MAX(e,j);
    max_num = MAX(f,k);
    max_num = MAX(g,l);
}

常用的常数也可以使用宏替换
嫌 long long 之类的太长了也可以用宏替换或者 typedef

#define VEC_SIZE 81*114514
#define uint32 unsigned int
typedef long long int64;
vector<int> stu_id(VEC_SIZE);
vector<uint32> stu_score(VEC_SIZE);
int64 stu_num;

开拓你的眼界

为了解决故意加大难度的OJ，你可能需要使用各种阴间技巧或者课上没有教的算法。这些算法你可能可以在OI WIKI中找到。
尽量使用高效的搜索引擎（百度实在是太垃圾了）
具体代码方面的问题可以在 runoob 和 stackoverflow 中搜索答案

学海无涯，不要被眼前的课程局限了眼界，而应该利用好目前网络上信息共享的优势，学习更加先进的，自己更感兴趣的，更为实用的只知识