NOI 系列赛常见技术问题整理

今天起，全新的 NOI Linux 2 正式替代了旧版 NOI Linux，成为 NOI 系列赛的官方比赛环境。 每年比赛开始前，都有不少人在讨论区提问比赛技术问题，常常存在重复提问，回答不准确的情况，因此我通过搜索，找出大家关心的问题，将问题与解答整理于此，以供参考。 欢迎补充，也欢迎捉虫。 ## 0 免责声明 - 本文信息来源于 NOI 官网公布的正在实施的技术规范，一些选手的实践经验，向 NOI 技术委员会询问得到的回复等，并进行了一定整理和加工，以供各位参赛选手参考。 - 本文**不应**被视为对 NOI 官网公布的技术规范的官方解读，官方规范的最终解释权归属 NOI 科学委员会，虽然作者在编写本文时已经尽到最大努力进行查证与测试，但**不保证**本文的内容完全准确。对于规范中未作出明确规定，不确定性较大的内容，将会用*斜体*进行标注。 ## 1 系统配置情况 NOI Linux 2.0 是基于 Ubuntu 20.04 LTS 定制而成的系统，为 **64 位** 系统。 系统内自带 g++ 编译器，版本 9.3.0（编译时如果未指明语言标准，默认采用 **C++14 标准**），另外有 Python 2.7 和 3.8，虽然 Python 并非竞赛语言，但可以使用 Python 编写一些辅助性程序（如数据生成器，对拍器等）。 评测时，程序使用的内存大小 **按声明的内存空间计算**。开过大的全局数组会导致所有测试点 MLE 而获得零分。 IDE 有 Code::Blocks，Geany。 编辑器有 VS Code（安装了 C++ 扩展，但组件不完整，另外无简体中文翻译包），Vim，Emacs，gedit，Sublime Text 3 等。 ## 2 NOI 技术规范摘抄 将现有的技术规范简单整理后做了份简明，方便理解的版本。后文提到的不少内容都可以在该规范中找到对应的要点。 请仔细阅读并理解这部分内容后，再阅读下面的部分。不清楚这部分的内容导致的盲目提问可能会给您带来不必要的尴尬。 1. 对于一道题目，选手只应该提交一个扩展名为 `.cpp` 的源文件，且其大小不应超过 100 KB，不应使用自己编写的头文件。（2022 年起全部 NOI 系列赛均只能使用 C++ 语言） 2. 选手程序应正常结束，`main` 函数的返回值为 0。 3. 选手程序不应执行如下违规操作： - 试图访问网络 - 使用 fork、exec、system 或其它线程/进程生成函数 - 打开或创建题目规定的输入/输出文件之外的其它文件和目录 - 运行其它程序 - 改变文件系统的访问权限 - 读写文件系统的管理信息 - 使用除读写规定的输入/输出文件之外的其它系统调用 - 捕获和处理鼠标和键盘的输入消息 - 读写计算机的输入/输出端口 4. 在不违反 3 的前提下，选手可以自由使用以下划线开头的宏和函数。 5. 禁止使用内嵌汇编。 6. 禁止更改评测时使用的编译选项。 ## 3 我能在代码中使用...吗？ - `bits/stdc++.h`：可以使用。 - 需要注意这样会将所有头文件引入，会增大标识符冲突的风险。如何解决这一问题见后文。 - `#define int long long`：**不推荐**。一方面，标准指出，不能对关键字进行 `#define` 操作，否则行为未定义；另一方面，从语义上说，`int` 在标准中代表 32 位整数类型，将其强行赋予 `long long` 的含义会造成认识上的混淆（例如，使用 `scanf` 和 `printf` 的时候可能搞错使用 `%d` 还是 `%lld`）。 - 如果觉得 `long long` 太长的话，可以用 `using` 语句或 `typedef` 语句给其赋予一个较短的别名，例如 `using i64 = long long`，`typedef long long i64` 等。 - `__int128`：现在的系统是 64 位系统，因此可以使用。需要注意的是 `__int128` 并不能直接使用 cin/cout，scanf/printf 进行输入输出，需要手写输入输出函数（类似于快读快输）。~~另外使用 `__int128` 真的就能完全避开高精度吗？~~ - `ios::sync_with_stdio(false)`：可以使用。但需要注意： - 关闭流同步后不应混用 C 风格 IO（`scanf/printf/getchar/putchar` 等）和 C++ 风格 IO（`cin/cout` 等）。 - **推荐**在程序最后刷新缓冲区（原因见后文）。 - `fclose()`：没有必要。程序结束时的清理工作包括关闭输入输出。 - 如果关闭了流同步，在没有刷新缓冲区（`std::endl` 等）的情况下应用 `fclose()`，可能会导致程序没有输出！ - `fread()`：可以使用。 - `__gcd()`，`__builtin_clz()` 等一部分下划线开头函数：可以使用（因为没有被禁止的操作）。 - 标准库函数 `gcd()` 在 C++17 标准中被加入。 - `gets()`：因为存在缓冲区溢出的问题，已经于 C++11 中被弃用，C++14 中被废除。可以使用 `fgets()` 替代。 - `itoa()`：不是标准库中的函数。是否能使用取决于 NOI Linux 环境下能否正常编译。 - 在代码中手动开启 `-O2` 等优化选项：不可以。评测时只能按照 PDF 首页给出的编译选项编译程序，擅自更改编译选项属于违例。 - 指令集：不可以。理由同上。 - `exit(0)`：与 `main()` 函数最后 `return 0;` 效果一致，因此可以使用。 - 标准规定，即使 `main()` 函数最后不显式写 `return 0;`，不影响程序正常退出时返回零值。 - `pb_ds`：*可以使用*（有人发邮件询问过）。 - 无序关联式容器：C++11 起可以直接使用。需要注意它们的最坏复杂度是线性的。 - 基于范围的 `for` 循环：C++11 起可以使用。 - `auto` 类型说明符：C++11 起可以使用。 - `std::tuple`：C++11 起可以使用。 - `std::array`：C++11 起可以使用。 - 结构化绑定：C++17 起可以使用。是否能使用取决于 NOI Linux 下环境下能否正常编译。 - 多线程：不能使用。 - `register`：C++11 起被弃用，C++17 起被移除。因此 C++11 后使用它不会造成任何优化效果。 - 列表初始化：C++11 起可以使用。需要注意的是 Windows 下部分编译器在使用 C++11 以前标准编译使用列表初始化的程序时，只给出警告而无错误。更推荐的做法是使用构造函数。 - 随机函数：没有限制。但 `random_shuffle` 已经于 C++14 起被弃用，C++17 起被移除。C++11 以后可以使用 `shuffle` 函数替代。另外有关随机化造成的评测结果波动引发的申诉，按规定将不被接受。 - 需要注意，Windows 环境下的 `rand()` 返回 16 位整数（$0 \sim 2^{15}-1$），Linux 环境下的 `rand()` 返回 32 位整数（$0 \sim 2^{31}-1$）。 ## 4 比赛系统的使用 考虑到有不少选手不熟悉 Linux 系统，还有不少地方仍然使用 Windows 作为比赛环境，因此特开辟一个板块，讲解 Linux 与 Windows 的相关使用技巧。 有关 Linux 和 Windows 下命令行使用的相关技巧，[OI Wiki](https://oi-wiki.org/tools/cmd/) 讲述得非常详细，这里主要是介绍命令行使用以外的一些注意事项。 ### 4.1 更改栈空间 一般来说，评测时的栈空间限制等于内存限制。但系统默认的栈空间往往较小，有时会出现官方评测时正常运行，而本地测试时爆栈的情况。这时候就需要对栈空间进行更改。 在 Linux 系统下，由 `ulimit` 对程序使用的资源进行限制。 在终端下输入 `ulimit -s <num>` 可以将栈空间更改为 `num` KiB（如 `ulimit -s 262144` 可以将栈空间改为 256 MiB），`ulimit -s unlimited` 可以将栈空间改为无限制。`ulimit -a` 可以查看各项资源的限制情况。 `ulimit` 还能对 CPU 时间（`-t`），内存（`-v`）等资源进行限制，调整限制的方法与调整栈空间限制的方法相似。 需要注意的是，`ulimit` 对包括栈空间在内的资源限制的配置仅在 **当前终端** 下有效。 对于 Windows 系统，栈空间在程序编译时确定，准确来说，由连接器来处理栈空间的大小问题。在编译时添加如下参数 `-Wl,--stack=<num>` 可以将栈大小改为 `num` Byte（如 `-Wl,--stack=268435456` 将栈空间确定为 256 MiB）。 如果使用 Dev-C++ 编写代码的话，点击“工具”一栏下的“编译选项”，在弹出的编译选项设置对话框中选择“编译器”一栏，在“在连接器命令行加入如下命令”下的文本框添加上述编译参数（添加时记得和已有的编译参数之间用一个空格隔开），就能在编译时实现同样的效果了。 ### 4.2 Windows 下查看样例文件 一般情况下，考场下发的样例文件是 Linux 格式的（换行为 `\n`），而 Windows 下的换行为 `\r\n`，因此如果在 Windows 下用记事本打开样例文件，因为无法正确识别换行的原因，样例会无法正常显示（可能表现为无换行，换行符被黑矩形字符代替等）。 使用 VS Code 等高级编辑器可以有效解决这一问题（还能实现换行格式的转换）。当然如果没有提供 VS Code 的话，也可以用系统自带的写字板。 当然这只是解决了显示问题，如果你尝试在写字板打开文件后，将输入直接复制到命令行，你可能会发现还是不能正常读入。正确的方法是在代码中添加重定向/文件流，或者在命令行中使用管道。 ## 5 代码编写疑难解答 ### 5.1 数组越界的检测 C++ 的原生数组并无任何数组越界的检查机制，越界访问属于未定义行为，可能会导致信息的意外修改，访问被保护的内存导致程序非零返回值终止等结果。 数组越界如果不引发程序 RE，将会给调试带来非常大的麻烦。如果能在运行时检查此类错误，将会有效减少 FST 的发生。 好消息是，`std::array` 和 `std::vector` 都提供了实用的越界检查功能，使用 `at(pos)` 成员函数，与直接使用下标运算符（`[pos]`）相比，会先进行越界检查，如果发现越界则直接终止程序。 不可避免地，使用越界检查功能会对程序效率有一定影响，这一点也请注意。 关于原生数组的运行时越界检测，在下一节“未定义行为的检测”会详细提到。 ### 5.2 未定义行为的检测 （关于未定义行为的定义与示例，可以参考 [[洛谷日报#265]关于 C++ 未定义行为的一些事](https://www.luogu.com.cn/blog/StudyingFather/undefined-behavior)） 在编译时打开全部警告（添加参数 `-Wall`）可以捕捉一部分未定义行为，不过由于该过程在编译时进行，并不是所有的未定义行为都能被检测出来。 如果使用 Linux 系统，且编译器版本较高（NOI Linux 2.0 可以使用！），可以使用 Sanitizer 实现运行时未定义行为及内存错误的检测。 在编译时加入参数 `-fsanitize=undefined` 即可开启 Undefined Behavior Sanitizer。其会在运行时检测代码中是否出现数组越界，带符号整数溢出等未定义行为，如果有，则会输出错误信息。 需要注意的是，`std::vector` 的越界并不会被 Undefined Behavior Sanitizer 检测到，需要用前文提到的 `at` 成员函数来检测。 例如，下面是一个带符号整数溢出的程序： ```cpp #include <iostream> using namespace std; int main() { int x = 2147483647; x++; cout << x << endl; return 0; } ``` 运行后会得到如下输出： ```plain a.cpp:5:4: runtime error: signed integer overflow: 2147483647 + 1 cannot be represented in type 'int' ``` 对于习惯使用指针的选手，Address Sanitizer 提供了一系列内存错误检测的手段，可以检测出解引用无效指针，空间重复释放等问题。在编译时使用 `-fsanitize=address` 即可开启 Address Sanitizer。 下面是一个解引用无效指针的程序。 ```cpp #include <iostream> using namespace std; int main() { int *ptr = (int*)0x12345678; cout << *ptr << endl; return 0; } ``` 运行后得到的输出如下： ```plain AddressSanitizer:DEADLYSIGNAL ================================================================= ==2613==ERROR: AddressSanitizer: SEGV on unknown address 0x000012345678 (pc 0x55fbd6ca12d8 bp 0x7ffc42bc00a0 sp 0x7ffc42bc0090 T0) ==2613==The signal is caused by a READ memory access. #0 0x55fbd6ca12d7 in main /home/friend/a.cpp:5 #1 0x7fa1d8c380b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2) #2 0x55fbd6ca11cd in _start (/home/friend/a+0x11cd) AddressSanitizer can not provide additional info. ``` Sanitizer 的使用会带来额外的时间开销，因此在测试程序运行效率时请不要使用 `-fsanitize` 系列选项。 ### 5.3 标识符未导入 / 标识符冲突的解决方案 （该部分内容参考了 LCA 写的 [如何在不提供 NOIlinux 2.0 环境的考点避免编译错误](https://loj.ac/d/3422)，在此表示感谢！） 由于运行环境差异，在本机正常编译的情况下，评测环境可能会出现找不到标识符或标识符冲突的问题。 一般来说，万能头文件 `bits/stdc++.h` 包含了 C++ 标准库的全部头文件，只需要在代码中包含该头文件，再加上 `using namespace std;`，就能避免标识符未定义的问题。然而，这么做之后，就会将标准库的全部标识符都导入到文件中，增大了标识符冲突的风险。 为解决标识符冲突问题，只需要将所有代码均包裹在一个命名空间（`namespace`）即可。 ```cpp #include <bits/stdc++.h> using namespace std; namespace solve { // 定义其他变量，函数和结构体类型 void main() { } } int main() { solve::main(); return 0; } ``` 依据“就近原则”，在 `solve` 命名空间中查找一个标识符时，`solve` 命名空间中定义的标识符较 `std` 中定义的标识符更先被找到，从而避免了标识符冲突。 解决了标识符冲突后，就可以放心大胆地使用万能头文件了。如果你不能记清楚所有的头文件的话，万能头文件确实是个不错的选择。 需要注意的是，即使不使用 `using namespace std;` 导入整个 `std` 命名空间，而是只使用 `using std::xxx;` 导入部分需要的标识符，也不能完全避免标识符冲突。这是因为一些继承自 C 的头文件（文件名一般是 `c` 加原头文件名，并去掉 `.h`），为兼容需要，其中标识符不需要加 `std::` 前缀仍然能访问。 ## 参见 - [[洛谷日报#86]OIer 必知的编程技巧](https://www.luogu.com.cn/blog/StudyingFather/some-coding-tips-for-oiers)（2018 年的文章，部分内容可能已经过时） - [[洛谷日报#265]关于 C++ 未定义行为的一些事](https://www.luogu.com.cn/blog/StudyingFather/undefined-behavior) - [命令行 - OI Wiki](https://oi-wiki.org/tools/cmd/)