跳到主要内容

OI 冷知识

备注

说是冷知识... 不过讲的挺杂的，这里也算得上杂项。

缩写​

初看这些缩写可能难以快速反应过来，但是写多了程序便会习惯：

缩写全名说明
ansanswer即答案。常见于变量名。
iindex即序列数。常见于 for 循环中，衍生出了 j、k 等缩写，但都是同一意思。

时间复杂度 & 空间复杂度​

时间复杂度 (Time Complexity) 是衡量一个算法的快慢，一定要考虑数据规模的大小。 所谓数据规模，一般指输入的数字个数、输入中给出的图的点数与边数等等。 一般来说，数据规模越大，算法的用时就越长。 而在算法竞赛中，我们衡量一个算法的效率时，最重要的不是看它在某个数据规模下的用时，而是看它的用时随数据规模而增长的趋势。

类似地，空间复杂度 (Space Complexity) 是用来衡量算法所使用的空间随输入规模变化的趋势。

一般地，由于诸多因素，我们都使用符号 O(...)O(...) 来表示复杂度。 当然这是不准确的，详见 oi-wiki 对渐进符号的解释。

评判结果​

在我们写完程序后，我们可以将代码提交至在线评判平台。

在线评判平台 (Online Judge System，又称 OJ) 常见的有 力扣 (国际版的是 LeetCode，不过国内也进不去)、 洛谷 等， 大多数评判平台同时也是题库提供方，我们可以在上面找到许多题目。

同样地，评判结果也大多以缩写的形式告诉我们，见表：

缩写全名说明
ACAccepted选手程序被接受。
CECompile Error选手程序无法正常编译。如果思路没问题的话，一般是哪些写漏或者写错了。
WAWrong Answer选手程序正常结束，但是选手程序的输出与测试点输出不符。
PEPresentation Error选手程序正常结束，但是格式不符合要求。
RERuntime Error选手程序非正常结束 (选手程序结束时的返回值不为零，一般是 int main() 方法结尾返回了非 0 的值，如 return 1;。)。
TLETime Limit Exceeded选手程序运行的时间超过了给定的时间限制。
MLEMemory Limit Exceeded选手程序占用的最大空间超过了给定的空间限制。
OLEOutput Limit Exceeded选手程序输出的内容的量超过了最大限制。

小技巧​

竞赛佬必备​

时间紧，任务重，直接通用头文件吧！

#include <bits/stdc++.h>

更好的重复循环​

为什么重复做某件事情还要 for 写长长一坨？直接 #define 一下就舒服了：

#define repeat(n) for (size_t _ = 0; _ < n; _++)

具体用法：

#include <iostream>
#define repeat(n) for (size_t _ = 0; _ < n; _++)
using namespace std;

int main() {
    repeat (10) {
        cout << "Hello! " << endl;
    }
    return 0;
}

更好的数据类型​

你绝对能够用得上的 typedef ！

typedef long long l_long;
typedef long double l_double;
typedef signed char s_char;
typedef unsigned char u_char;
typedef unsigned short u_short;
typedef unsigned int u_int;
typedef unsigned long u_long;
typedef unsigned long long ul_long;