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 技术规范摘抄

将现有的技术规范简单整理后做了份简明，方便理解的版本。

请仔细阅读并理解这部分内容后，再阅读下面的部分。不清楚这部分的内容导致的盲目提问可能会给您带来不必要的尴尬。

对于一道题目，选手只应该提交一个扩展名为 .cpp 的源文件，且其大小不应超过 100 KB，不应使用自己编写的头文件。（2022 年起全部 NOI 系列赛均只能使用 C++ 语言）
选手程序应正常结束，main 函数的返回值为 0。
选手程序不应执行如下违规操作：
- 试图访问网络
- 使用 fork、exec、system 或其它线程/进程生成函数
- 打开或创建题目规定的输入/输出文件之外的其它文件和目录
- 运行其它程序
- 改变文件系统的访问权限
- 读写文件系统的管理信息
- 使用除读写规定的输入/输出文件之外的其它系统调用
- 捕获和处理鼠标和键盘的输入消息
- 读写计算机的输入/输出端口
在不违反 3 的前提下，选手可以自由使用以下划线开头的宏和函数。
禁止使用内嵌汇编。
禁止更改评测时使用的编译选项。

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 等）。
- 推荐在程序最后用 endl 刷新缓冲区（原因见后文）。
fclose()：没有必要。程序结束时的清理工作包括关闭输入输出。
- 如果关闭了流同步，在没有刷新缓冲区（std::endl 等）的情况下应用 fclose()，可能会导致程序没有输出！
fread()：可以使用。
__gcd()，__builtin_clz() 等一部分下划线开头函数：可以使用（因为没有被禁止的操作）。
- 标准库函数 gcd() 在 C++17 标准中被加入。
gets()：因为存在缓冲区溢出的问题，已经于 C++11 中被弃用，C++14 中被废除。可以使用 fgets() 替代。
itoa()：不是标准库中的函数。是否能使用取决于本机能否正常编译。
在代码中手动开启 -O2 等优化选项：不可以。评测时只能按照 PDF 首页给出的编译选项编译程序，擅自更改编译选项属于违例。
指令集：不可以。理由同上。
exit(0)：与 main() 函数最后 return 0; 效果一致，因此可以使用。
- 标准规定，即使 main() 函数最后不显式写 return 0;，不影响程序正常退出时返回零值。
pb_ds：可以使用（有人发邮件询问过）。
无序关联式容器：C++11 起可以直接使用，C++98/03 时它们在 std::tr1 命名空间下（是否能在比赛中使用 std::tr1 命名空间尚不清楚）。需要注意它们的最坏复杂度是线性的。
基于范围的 for 循环：C++11 起可以使用。
auto 类型说明符：C++11 起可以使用。
std::tuple：C++11 起可以使用。
std::array：C++11 起可以使用。
多线程：不能使用。
register：C++11 起被弃用，C++17 起被移除。因此 C++11 后使用它不会造成任何优化效果。
列表初始化：C++11 起可以使用。需要注意的是 Windows 下部分编译器在使用 C++11 以前标准编译使用列表初始化的程序时，只给出警告而无错误。更推荐的做法是使用构造函数。
随机函数：没有限制。但 random_shuffle 已经于 C++14 起被弃用，C++17 起被移除。C++11 以后可以使用 shuffle 函数替代。另外有关随机化造成的评测结果波动引发的申诉，按规定将不被接受。
- 需要注意，Windows 环境下的 rand() 返回 16 位整数（ $\sim 2^{15}-1$ ），Linux 环境下的 rand() 返回 32 位整数（ $\sim 2^{31}-1$ ）。

4 比赛系统的使用

考虑到有不少选手不熟悉 Linux 系统，还有不少地方仍然使用 Windows 作为比赛环境，因此特开辟一个板块，讲解 Linux 与 Windows 的相关使用技巧。

有关 Linux 和 Windows 下命令行使用的相关技巧，OI Wiki 讲述得非常详细，这里主要是介绍命令行使用以外的一些注意事项。

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）。

4.2 查看样例文件

一般情况下，考场下发的样例文件是 Linux 格式的（换行为 \n），而 Windows 下的换行为 \r\n，因此如果用记事本打开的话，因为无法正确识别换行的原因，样例会无法正常显示（可能表现为无换行，换行符被黑矩形代替等）。

使用 VS Code 等高级编辑器可以有效解决这一问题（还能实现换行格式的转换）。当然如果没有提供 VS Code 的话，也可以用系统自带的写字板。

当然这只是解决了显示问题，如果你尝试在写字板打开文件后，将输入直接复制到命令行，你可能会发现还是不能正常读入。正确的方法是在代码中添加重定向/文件流，或者在命令行中使用管道。

5 代码编写疑难解答

5.1 数组越界的检查

C++ 的原生数组并无任何数组越界的检查机制，越界访问属于未定义行为，可能会导致信息的意外修改，访问被保护的内存导致程序非零返回值终止等结果。

数组越界如果不引发程序 RE，将会给调试带来非常大的麻烦。如果能在运行时检查此类错误，将会有效减少 FST 的发生。

好消息是，std::array 和 std::vector 都提供了实用的越界检查功能，使用 at(pos) 成员函数，与直接使用下标运算符（[pos]）相比，会先进行越界检查，如果发现越界则直接终止程序。

不可避免地，使用越界检查功能会对程序效率有一定影响。详细情况大家可以自己跑一个 benchmark 观察效果（~~因为作者懒得跑~~）。

5.2 标识符未导入 / 标识符冲突的解决方案

（该部分内容参考了 LCA 写的如何在不提供 NOIlinux 2.0 环境的考点避免编译错误，在此表示感谢！）

由于环境差异，部分编译器存在头文件自动补齐的情况，因此会出现本机正常编译而在评测环境下编译错误的情况。同样的原因，一些标识符冲突也不一定能在本机编译下发现。

先讲下如何避免标识符冲突。只需要将所有代码均包裹在一个命名空间（namespace）即可。

#include <bits/stdc++.h>
using namespace std;
namespace solve {
  // 定义其他变量，函数和结构体类型
  void main() {
  }
}

int main() {
  solve::main();
  return 0;
}

依据“就近原则”，查找一个标识符时，namespace 中定义的标识符较 std 中定义的标识符更先被找到，从而避免了标识符冲突。

解决了标识符冲突后，就可以放心大胆地使用万能头文件了。如果你不能记清楚所有的头文件的话，万能头文件确实是个不错的选择。

需要注意的是，即使不使用 using namespace std; 导入整个命名空间，而是只使用 using std::xxx; 导入部分需要的标识符，也不能完全避免标识符冲突。这是因为一些继承自 C 的头文件（文件名一般是 c 加原头文件名，并去掉 .h），为兼容需要，其中标识符不需要加 std:: 前缀仍然能访问。

文章版权归作者所有，未经允许请勿转载。

THE END

技术教程
# noi