数据结构OJ使用说明（供校内课堂学生使用）¶

清华大学计算机系 · 数据结构教学团队

目录¶

  1. 注册OJ并加入课堂
  2. 完成作业
  3. 提交代码
  4. 查看测试详情
  5. 标记最终版本
  6. 题组选做
  7. 提交状态自查
  8. 得分组成
  • 附：FAQ
  • 附：OJ 使用技巧
  • 附：输入输出技巧
  • 附：一些常见逻辑错误
  • 附：Visual Studio msvc 与 GNU gcc 的差异

注册OJ并加入课堂¶

OJ，全称Online Judge， 是编程作业的在线评测系统。

需要点击右上角这个按钮注册：

OJ 注册按钮

请在邮箱查收验证码，如果没收到验证码，可能需要检查一下垃圾邮件。

加入课堂需要邀请码，在网络学堂课程作业评语里，是助教手动发放的。

网络学堂中的课堂邀请码

加入课堂后如图所示：

加入课堂后的页面

完成作业¶

课堂作业页面

点击进入课堂，有若干次编程作业，并在左边显示作业截止时间。作业标题的背景，绿色表示尚未截止，红色表示即将在一周内截止，灰色表示已经截止。

每次作业有若干道题目，各题目在本次作业中占的权重在题目标题后的括号内。

  • 点击 Text 可以查看题目描述。
  • 50% Judge
    • 五成测，测前 50% 的测试点，不限次数。
  • 90% Judge
    • 九成测，测前 90% 的测试点 。
    • 有次数限制（图中“0 / 10”为共 10 次，已用 0 次） 。
  • 全集测 （Judge)
    • 作业截止后，会统一重新进行全集测，黑盒成绩使用全集测结果。将五成测还是九成测标记为最终版本不影响得分。
    • 截止一段时间后，同学们可自行全集测，如与黑盒成绩有较大差异，可提出复议。
    • 某些LAB只有一个Judge按钮，说明它始终开放全集测。
  • 诚信守则（Honor Code）
    • Honor Code 要记录，你在写程序的哪些模块时，做过哪些交流。与他人交流需具体到姓名（网络论坛上的交流可填写用户名），参考网络资料需具体到链接，以便教学团队了解交流程度和参考的内容。在作业纪律方面有违自己所做承诺者，将按Honor Code中所约定的方式受到处罚。
    • 注意在标记最终版本前，Honor Code 只会作为草稿暂存，不会视为签署。
  • 报告（Report）
    • 提交要求详见网络学堂《编程作业白盒指引》。
    • 为节约服务器资源，报告中不要包含过大的内容（例如高分辨率图片、不必要的数据文件等），过大的报告可能无法成功上传。

提交代码¶

  • 每次提交的文件不要超过 200 KB。代码如果含有多个文件，可以将所有代码置于顶层目录直接打包（.zip、.tar、.tar.gz 等格式）提交，目录和文件名不能有空格、中文、特殊字符。
  • 每次提交可以写一个 comment，便于检索。

提交代码页面

查看测试详情¶

  • 点击蓝色带下划线的提交时间，可以查看测试详情。
    • 对评测结果的解释： https://dsa.cs.tsinghua.edu.cn/oj/static/submission_result_explanation.html。
    • 显示的分数是通过的测试点占所有测试点的比例，因此“五成测”最高 50 分，“九成测”最高 90 分。

测试详情入口

标记最终版本¶

  • 作业截止前需要标记最终版本，在多次提交中选择一份代码最终计分。
    • 具体做法是在提交记录中点击对勾。
    • 标记最终版本时需同时签署 Honor Code。

标记最终版本

题组选做¶

有的作业只允许选做若干道。例如，下图中超过5道则无法标记最终版本，从而无法得分。如果没有此提示，则没有此限制，但你还是要满足分组选做限制。

作业选做题数限制

有的作业中，题目被分组，同一组里的题目只允许选做 1 道，如下图所示。超过 1 道则无法标记最终版本，从而无法得分。如果没有显示 Group，则该题没有此限制。

题目分组选做限制

每题得分与总评成绩的具体对应方式详见网络学堂 Syllabus 和《编程作业指引》。

建议根据题目难度、自己的时间和能力选做题目。

提交状态自查¶

  • 可根据题目显示的背景色，自查是否提交并标记了应做的题目。
  • 选做题：灰色-黄色-绿色 （无最终版本-无报告-完成）。
  • 必做题：红色-黄色-绿色。
  • 注：即便为背景为绿色，也强烈建议在提交前再次检查 。

题目提交状态

得分组成¶

  • 点击 Open the Score Sheet 查看每题的提交状态和得分。
  • 白盒评分为 N/A 代表评阅尚未完成，请耐心等待，完成后会在网络学堂发布公告。
  • 每题得分与总评成绩的具体对应方式详见网络学堂 Syllabus 和《编程作业指引》
  • 最后一列的Comment是助教给出的白盒评语，通常涉及白盒扣分的具体理由，可在最终成绩发布后查看，不断改进。

成绩表入口

成绩表详情

附：FAQ¶

  1. OJ 上需要提交哪些文件？

只需要提交源代码文件( *.cpp / *.c / *.h )，其余文件尽量不要一同打包。传统题型（PA）报告只需要提交 *.txt / .md 单文件，拓展题型（LAB）报告要求详见各题要求。

  1. OJ 上的编译环境与本地有何不同，需要注意哪些问题？

我们建议使用类Unix命令行和g++编译器在本地运行调试程序。

OJ 使用的是 64 位 Linux 系统 Ubuntu 18.04；C 语言编译器版本是 64 位 gcc-7，编译选项 -std=c11 -O2 -D_OJ_ ；C++ 语言编译器版本是 64 位 g++-7，编译选项 -std=c++14 -O2 -D_OJ_ 。

它与 Visual Studio 中的 MSVC 编译器有一些小区别，例如：main 函数的返回值必须为 int，默认不会包含任何头文件等等。如果遇到了本地编译成功 OJ 编译失败的例子，可以借助搜索引擎，根据提示进一步修改源程序。 主要区别在“ 附：Visual Studio msvc 与 GNU gcc 的差异 ”中列出。

  1. OJ 上是否禁止使用某些库？

OJ的一部分题目开放了全部STL的使用（详见每道题目单独的说明），另一部分题目中，移除了大部分 STL 头文件，例如 vector、map、algorithm。

原则上，只要你的作业能够通过编译，就没有任何问题。不过不包括手动把这些头文件与你的作业其他代码一同打包提交上来，也禁止使用别人写的模板库。

我们确认以下库可以正常使用：用于输入输出的 cstdio、iostream、iomanip，泛型编程 functional、type_traits、initializer_list，数学运算 cmath，内存分配与异常处理 new、stdexcept，平台相关的类型和常量 cstdint、climits，对 C 标准库的直接封装 cstdlib、cstring、cassert、cstdarg，上述库依赖的库 string、tuple、utility 等。 例如标准库 cstdlib 中的 std::qsort 函数是允许使用的。

如果不确定某个头文件是否可以使用，不妨先交一个只 include 该头文件的代码试一下。

  1. 输入输出应该采用哪些函数？

请使用 scanf 和 printf 来代替 cin 和 cout，某些情况下后者效率远远远远低于前者。更高效的读入是用 fread，然后手动解析文本。

  1. Runtime Error 是怎么回事？

Runtime Error 是指程序在运行过程中出现了问题，通常是内存访问的问题，比如数组下标越界。一般这些问题在小规模测试的时候不会发现，而在 OJ 上大规模数据测试时候就容易暴露出来，所以请自行构造一些数据来调试程序。如果希望知道 OJ 返回错误代码的含义，可以参考 http://dsa.cs.tsinghua.edu.cn/oj/static/submission_result_explanation.html 。常见的有 6：断言或异常；8：整数除以 0 错；11：内存访问错误。

  1. 有什么快速定位越界和野指针的方法吗？

Visual Studio 2019 已推出运行时地址检查功能，可在项目“属性 -> C/C++ -> 启用地址擦除系统（实验性）”开启。地址检查有助于及时发现隐蔽的越界。

gcc 和 clang 编译器提供了更强大的运行时检查功能，不仅可以检查地址越界（编译选项 -fsanitize=address ），还可以检查整数溢出(编译选项 -ftrapv )等。

  1. 我的运行结果是 Time Limit Exceeded，时间 ≥ 2200 ms，是不是只要再做一些常数级优化就不会超时了？

当超过题目规定的时限，OJ 会杀死进程。显示用时 ≥ 2200 ms，说明程序运行时间超过时限（2 s），并不说明程序只花 2200 ms 就能运行完。因此，不一定是把程序运行速度优化 200 ms 就能解决的。

附：OJ 使用技巧¶

  1. OJ 首页上有本OJ使用说明（OJ handbook），和已归档的编程作业说明（PA handbook）。前者供清华校内学生参考，后者供MOOC学生参考。
  2. 在黑盒测试结果页面，有解释评测结果的含义的链接 http://dsa.cs.tsinghua.edu.cn/oj/static/submission_result_explanation.html 。
  3. Runtime Error 的 signal 同样反映了某种信息，可以查阅相关资料了解各个 signal 的意义。参考 http://dsa.cs.tsinghua.edu.cn/oj/static/unix_signal.html 。
  4. 几种主要的读入数据方法，大多数情况下性能是 fread > getchar > scanf > cin 的顺序。
  5. OJ 上的编译器采用的是 gcc（g++），对于 Linux 和 Mac 用户可以无缝衔接，而如果使用 Windows 的同学希望能够在本地编译与 OJ 编译之间较快衔接的话，可以考虑使用 MinGW。
  6. 评测所依赖的输出流是 stdout，而使用 stderr 的输出不会被纳入最终评测——但如果你使用 stderr 进行调试却没有在提交中移除，这将显著地拖累你程序的性能。
  7. 程序输出应与标准答案一致，请留意多余的空格、制表符、回车和换行。行末空格和文末换行一般不会影响评分。
  8. Windows 和 Linux 上换行符有 "\r\n" 跟 "\n" 的差别，你的程序最好有一定鲁棒性，能处理两种情况。
  9. Linux 文件系统区分大小写，因此 #include "foo.h" 不能与 Foo.h 对应。
  10. 常用的调试工具包括 gdb、MSVC debugger、室友、小黄鸭、大语言模型。
  11. 如果不确定某一特性是否为 OJ 所支持，不妨动手试一试。

附：输入输出技巧¶

  1. 判断输入结束

有些编程作业题并未指明测试数据的组数，此时需要自己判断输入结束。其实，根据题意正确处理输入数据也是同学们在这门课中需要练习的编程能力之一。

处理输入的方法很简单，使用 C++ 风格的 cin，可以这样写

int a, b, c;
while (cin >> a >> b >> c)
{ /* blablabla */ }

如果使用 C 风格的 scanf() 函数，则可根据其返回值做出判断，具体地可以这样写：

int a, b, c;
while (scanf("%d%d%d", &a, &b, &c) != EOF)
{ /* blablabla */ }

当格式输入流读到文件末尾时会返回 EOF，于是 while 退出。

  1. 过滤空白字符

有些题目是这样的输入格式：

E 6
M
E 2
M

即字母、数字混输。如果用 getchar 或 scanf 的 %c 参数，会受到行末空白符（比如空格、换行等）的困扰。cin 到字符串、scanf 的 %s 参数都会自动过滤空白符。使用标准库的功能来过滤空白符，会使程序逻辑更清晰。示例代码：

char buf[8];
int x;
while (scanf("%s", buf) != EOF) {
 switch (buf[0]) {
 case 'E':
   scanf("%d", &x);
   /* balabala */
 }
}
  1. 重定向

为便于反复测试及再现运行过程，可采用输出、输入重定向的方法。

你只需事先将输入数据存成文件，运行时系统会自动从中获取输入。其效果完全等同于你从（作为默认输入流的）键盘逐项输入。 类似地，你也可以指定另一文件，并使运行的结果自动存入其中。其效果完全等同于从（作为默认输出流的）屏幕截取输出结果。

重定向的好处很多：可以避免手工输入的出错，忠实可靠地重复测试；可以实现大规模数据的输入；可以完整精确地记录程序的输出，以便事后的对比分析；可以省去默认输入、输出流占用的大量时间，更加准确地测量程序的执行效率。

方法一：修改源文件，指定重定向的输入、输出文件 例如，若希望从文件 input.txt 中获取输入，将输出保存到文件 output.txt 中，则可在主程序开头增加如下语句：

  #ifndef _OJ_
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
  #endif

注意：如果用 C++ 风格的 cin / cout 的话，还要在前面引用头文件的部分加入 #include <cstdio> 。 OJ 在编译程序的时候会定义名为 _OJ_ 的宏，所以上面这段语句会在 OJ 运行的时候被跳过。

方法二：在 IDE 中通过设置命令行，重定向输入、输出文件

以 Visual Studio 为例，可打开对应工程的“属性页”，在“配置属性”下的“调试”页，设置“命令行参数”。

输入参数不多时，可直接键入。例如 ADD 一题，键入“100 200”即可。

若其中包含特殊字符，则需以'^'引导，或者使用一对半角括号消除歧义。

若输入参数多，且不止一行，则可将其存成一个文件。比如，可在“命令行参数”中键入:

< D:\test\input.txt （注意起始字符"<"不能省略）

为将程序的输出保存至指定文件，可在“命令行参数”中继续键入：

> D:\result\output.txt （同样地，起始字符">"也不能省略）

若不希望覆盖文件原有的内容，只需用">>"替换以上的">"，即可将每次运行的输出追加至 D:\result\output.txt。

输入、输出的重定向可同时采用并生效。比如可在“命令行参数”中键入：

< D:\test\input.txt >> D:\result\output.txt

重定向文件的具体路径与文件名可自行选择，但若包含空格，则需使用一对半角引号消除歧义，比如：

< "D:\my test\input.txt" >> "D:\my result\output.txt"

  1. 帮助资料

关于输入输出的进一步问题，可以自己查阅相关手册或资料。

也可参考标准手册，以上输入输出方法都是 C / C++ 标准输入输出，在 manual 中都有详细介绍。

cin：http://www.cplusplus.com/reference/iostream/cin/

scanf：http://linux.die.net/man/3/scanf

对比：http://www.byvoid.com/blog/fast-readfile/

附：一些常见逻辑错误¶

  1. swtich 里忘记加 break，导致多个 case 后的语句都被执行。
  2. int *a = new int[n] 误写成 int *a = new int(n) 。前者申请了 n 个 int 的空间；而后者只申请了一个 int 的空间，并初始化为 n。
  3. 用 scanf 输入 long long 类型变量时，对应的格式串误用成 %d ，应为 %lld 。
  4. 在函数里开了很大的数组，导致运行时栈溢出。错误示例：
 int main() {
   int a[10000000];
   return 0;
 }

可以使用动态内存分配，避免栈溢出，例如：

 int main() {
   int *a = new int[10000000];
   delete[] a;
   return 0;
 }
  1. 计算溢出。错误示例：
 int a = 1000000, b = 1000000;
 long long c = a * b;

程序会先在 int 范围内计算a * b，再把溢出后的结果赋值给 c。正确写法是c = (long long)a * (long long)b。

  1. 使用有副作用的表达式时，表达式求值顺序影响结果

例如 a[i] = b[i++]，求值顺序可能相当于 a[i] = b[i]; i++，也可能相当于 tmp = b[i]; i++; a[i] = tmp。

  1. 有返回值的函数漏 return 语句。

行为是不确定的，有的编译器会恰巧返回你想要返回的变量，而一般不会。

  1. 指针引用了临时对象

使用指针时需要注意对象的生存期。在函数体内（或语句块内）定义的对象，出函数体时会析构，之后其值可能会被复写或重复利用；new、malloc 分配的内存不会被自动释放。

  1. strcpy / memcpy 的源地址和目标地址有重叠。
  2. 留意编译器给出的 warning，有可能对应着一个 bug。

附：Visual Studio msvc 与 GNU gcc 的差异¶

  1. msvc 可能会自动 include 一些头文件，gcc 编译提示函数找不到。
  2. 使用 scanf 等函数会警告 not safe(warning 4996) ，msvc 推荐使用 scanf_s ，但是这个不属于 C / C++ 标准，gcc 没有。
  3. gcc 也没有 itoa（数字转换为字符串的函数）。
  4. gcc 上，模板类继承模板类，two phase name lookup，调用父类函数会提示找不到，需要用 this-> 调用。
  5. gcc 禁止 void main。main 函数必须 return 0，如果返回值非 0，也会被认为是运行时错误，不得分。
  6. http://dsa.cs.tsinghua.edu.cn/oj/static/submission_result_explanation.html 列出了一些常见编译错误的解决方法。

数据结构编程作业说明