Skip to content

Latest commit

 

History

History

OnlineJudge

Online Judge系统(简称OJ)是一个在线的判题系统。用户能够在线提交程序多种程序(如C、C++)源码,系统对源码进行编译和运行,并通过预先设计的测试数据来检验程序源码的正确性。

一个用户提交的程序在Online Judge系统下运行时将受到比较严格的限制,包含运行时间限制,内存使用限制和安全限制等。用户程序运行的结果将被Online Judge系统捕捉并保存,然后再转交给一个裁判程序。

最后系统返回给用户使用的内存、执行时间以及一个状态:

  • 通过(Accepted, AC)
  • 答案错误(Wrong Answer, WA)
  • 超时(Time Limit Exceed, TLE)
  • 超过输出限制(Output Limit Exceed, OLE)
  • 超内存(Memory Limit Exceed, MLE)
  • 执行时错误(Runtime Error, RE)
  • 格式错误(Presentation Error, PE)
  • 无法编译(Compile Error, CE)

在这些 OJ 平台上做题,有着许多编程技巧上的套路(在实际生产环境中,有些方法甚至是要尽量避免的, LeetCode 提供的方式更接近于实际生产)。

OJ 常识

给定问题规模 n 和限制时间,其实也就变相告诉我们时间复杂度的要求,一般来说:

  • n <= 8 , n! 的算法可以
  • n <= 20 , 2^n 的算法可以
  • n <= 300, 至多用 n^3 的算法

OJ 编程技巧

把较大的数组 main 函数外,作为全局变量,这样可以防止栈溢出,因为一般栈的大小有限制。

如果能够预估栈,队列的上限,则不要使用stack, queue,使用数组来模拟,这样速度最快。(一般题目会限定问题规模,比如 N<100000)。

输入数据一般放在全局变量,在运行中不要修改这些变量。

判断一个数是否是奇数时,用 x % 2 != 0,不要用 x % 2 != 1,因为 x 可能是负数。

使用 vector 时,最好用 reserve 预先分配好空间,不要一点一点添加内容,这样它的性能就会跟固定大小的数组相当;

有时候 int 可能会溢出,可以用 long long,值类型表示值介于 -2^63 ( -9,223,372,036,854,775,808) 到2^63 - 1(+9,223,372,036,854,775,807 )之间的整数。

数组定义 int a[10]={0}; 可以对其全部元素赋值为0(初始化列表值不够时,后面全部补充0);还要注意全局变量,静态变量自动初始化为0;

判断两个浮点数误差的时候,使用fabs(a-b) < eps,一般的eps为1e-9。如果有可能,尽量避免浮点运算,做整数的转换。

更多阅读

ACM 入门指南
acm-cheat-sheet