前言
在我刚入门 ICPC 时，听着群里大佬们的聊天，完全听不懂啥意思，随着在圈内混的时间变长，慢慢的也就知道大佬口中的那些不明觉厉的缩写是啥了，这篇文章主要是记录一下入坑以来了解到的一些 ICPC 相关的术语。
0. ICPC 与 OI
ICPC 国际大学生程序设计竞赛：国际大学生程序设计竞赛「International Collegiate Programming Contest，ICPC」是由国际计算机协会「ACM」主办的，一项旨在展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力的年度竞赛。（不过前些年ACM协会跑路了，现在的赞助是「jetbrain」）。该比赛一般一年一个赛季，分为分为区域赛「Regional Contest」和总决赛「World Final」，竞赛群中说的xx站比赛，一般就是指区域赛，而群里都在膜的 WF 选手，就是总决赛选手。
OI 信息学奥赛：青少年信息学奥林匹克竞赛是在广大青少年中普及计算机教育，推广计算机应用的一项学科性竞赛活动。全国从 1984 年开始举办全国性竞赛。区分国际级比赛「International Olympiad in Informatics，IOI」与国家级比赛「National Olympiad in Informatics，NOI」。
大学的 ICPC 与高中的 OI 区别：
- ICPC 要求程序完全正确，且得分与程序的错误提交次数、正确提交时间有关（罚时永远的痛）；OI 设置分级得分，通过部分样例可拿到部分得分（所谓的骗分）
- ICPC 要求每队只能使用 1 台电脑，在 5 个小时内使用 C/C++、Java 和 Python 中的一种编写程序解决 7 到 13 个问题；OI 一般是 3 到 4 小时上机编程解题的形式，不限编程语言，竞赛题量相对较少
- ICPC 按队参与，每队 3 人，同时队员之前协作能力；OI 为单人参赛。
总的来说，ICPC 除了考验个人能力之外，还要考虑团队的默契和协作能力。
1. 常见的术语
列举一些常见的术语，不仅在比赛中，常见的 OJ 系统都会采用这些术语：
| 简写 | 全称 | 中文称谓 |
|---|---|---|
| OJ | Online Judge | 在线判题系统 |
| AK | All Kill | 所有题目都过了 |
| AC | Accepted | 通过该题 |
| WA | Wrong Answer | 答案错误 |
| RE | Runting Error | 程序运行时错误 |
| TLE | Time Limit Error | 程序运行超时 |
| MLE | Memory Limit Error | 程序运行超出内存要求 |
| OLE | Output Limit Error | 程序输出过多 |
| PE | Presentation Error | 输出格式错误 |
| CE | Compilation Error | 程序编译错误 |
| RF | Restricted Function | 程序尝试调用禁止的库函数 |
| IE | Internal Error | 测评系统内部错误 |
- 提交之后到出结果前的状态：
Pending程序正在准备；Submitted或Received程序已经被提交；Queuing程序正在排队等待评测；Compiling程序正在被编译；Judging或Running程序正在被评测 - RE可能是浮点数溢出、死递归、除0、下标越界、局部数组过大等情况造成
- PE 一般是多输出了空行或空格导致，多数 OJ 是不会有PE的，如果格式错误直接就是 WA ，所以要注意输出格式
- OLE 一般由于无限循环导致输出过多
- ICPC 题目运行内存一般的限制在 256Kb，512Kb，或 1Mb
2. 时间复杂度
在一般的线下竞赛中，测评姬在 1s 内能进行 $5 × 10^8$ 次计算，在这个限制下，不同时间复杂度的算法能解决的问题规模如下（此处是较为保险的数据，比赛时具体情况要具体分析）：
| 时间复杂度 | 数量级 n |
|---|---|
| O(N) | n < $10^8$ |
| O(NlogN) | n <= $10^6$ |
| O(N$\sqrt{N}$) | n < $10^5$ |
| O($n^2$) | n < 5000 |
| O($n^3$) | n < 300 |
| O($2^n$) | n < 25 |
| O(N!) | n < 11 |
版权属于：PCsky
本文链接：http://www.hyouka.club/index.php/archives/174/
转载时须注明出处及本声明