ACM算法竞赛入门——算法竞赛赛制、题目形式、常见评测状态

xcx：学完C++基础语法之后，已经迫不及待的打比赛了，算法竞赛到底是什么？

shy：别着急，今天我们来好好讲一讲算法竞赛赛制，题目形式和评测状态。

一、算法竞赛赛制

1. ACM赛制

ACM只有正确和错误两种结果，即使部分测试点通过仍显示答案错误。ACM赛制必须通过所有的测试点才算通过，虽然可以看到程序的运行结果，但无法了解题目具体测试点的情况。题目可以不限次数提交，直到所有测试点均通过为止，但是提交错误一次往往会有20分钟的罚时。ACM赛制可以看到实时的排行榜，可以根据排行榜上选手提交题目次数和通过率来安排自己的做题顺序（当然榜一神犇当我没说）。

排名方式计算：

先看通过题数，通过题数越多，排名越靠前，通过题数相同的情况下按照罚时升序排序（具体罚时计算方式如下）。

罚时计算：

ACM竞赛中的罚时是一种为解题时间和错误尝试次数而设立的惩罚机制，目的是鼓励参赛者尽快解决问题并避免不断尝试错误的情况。罚时是在解决问题的基础上计算的，由两部分组成：解题用时和错误尝试次数的罚时。

1. 解题用时： 对于每道题目，参赛队伍解决问题的用时是从比赛开始到解决问题的时间。这个用时单位通常是分钟。
2. 错误尝试罚时： 对于每道题目，如果参赛队伍在正确解答之前提交了错误的尝试，则会受到一定的罚时。通常，每次错误尝试会被罚时20分钟。这意味着，如果一个队伍在正确解答问题之前提交了k次错误尝试，那么该问题的罚时为20*k分钟。

最终，队伍的总罚时是所有解题用时和错误尝试罚时的总和。如果有多支队伍解决了相同数量的问题，总罚时越低的队伍排名越高。

举例说明：

假设队伍A在比赛开始30分钟时正确解答了问题1，但在此之前提交了2次错误尝试。队伍B在比赛开始20分钟时正确解答了问题1，但在此之前提交了3次错误尝试。

• 队伍A的罚时：
  • 解题用时：30分钟
  • 错误尝试罚时：2次错误 * 20分钟/次 = 40分钟
  • 总罚时：30分钟 + 40分钟 = 70分钟
• 队伍B的罚时：
  • 解题用时：20分钟
  • 错误尝试罚时：3次错误 * 20分钟/次 = 60分钟
  • 总罚时：20分钟 + 60分钟 = 80分钟

在这个例子中，尽管队伍B在解题用时上更短，但由于错误尝试次数较多，导致总罚时更高，因此队伍A在排名中可能更靠前。

==由此可见，ACM赛制交题需谨慎（当然时间不足的时候能A题肯定要A题，到时可以反复尝试，直到正确）。==

常见ACM赛制比赛：

ICPC（International Collegiate Programming Contest）国际大学生程序设计竞赛（The ICPC International Collegiate Programming Contest）

CCPC（China Collegiate Programming Contest）中国大学生程序设计竞赛（中国大学生程序设计竞赛(CCPC)-官网）

Codeforces Contests（Contests - Codeforces）

LeetCode 周赛/双周赛（竞赛 - 力扣 (LeetCode)）

牛客小白月赛、练习赛、挑战赛（牛客竞赛OJ_ACM/NOI/CSP/CCPC/ICPC_信息学编程算法训练平台 (nowcoder.com)）

传智杯全国大学生IT技能大赛（传智杯大赛官网-全国大学生计算机大赛 (ityxb.com)）

2. OI赛制

OI赛制提交题目得不到测试状态反馈，提交错误没有任何提示，一最后一次保存的结果为准。比赛中没有实时排行与A题情况（最讨厌这种赛制 (っ °Д °;)っ ）。

排名方式：

每道题的测试点都有对应分数，通过一个测试点就有一个测试点的分，赛后按照总分进行降序排序。

==所以遇到不会的题可以手动打表，骗测试点，能过一个就有一个的分。==

常见OI赛制比赛：

CCF CSP计算机软件能力认证（CCF CSP认证 (cspro.org)）

蓝桥杯（蓝桥杯大赛 — 全国大学生TMT行业赛事 (lanqiao.cn)）

牛客OI集训营等（牛客竞赛OJ_ACM/NOI/CSP/CCPC/ICPC_信息学编程算法训练平台 (nowcoder.com)）

3. IOI赛制

IOI赛制结合了ACM赛制和OI赛制的特点，提交之后有反馈结果，甚至可以看到本题的具体分数和排行，可以反复提交，没有罚时，按最高成绩为准。

排名方式：

每道题的测试点都有对应的分数，通过一个测试点就有一个测试点的分，按照总分数实时排名。

==IOI赛制可以各种暴力，各种打表骗分，骗测试点。==

常见IOI赛制比赛：

拼题A（PTA）（PTA | 程序设计类实验辅助教学平台 (pintia.cn)）

GPLT（Group Programming Ladder Tournament）团体程序设计天梯赛（团体程序设计天梯赛 (patest.cn)）

CCF CCSP大学生计算机系统与程序设计竞赛（CCSP - 中国计算机学会 (ccf.org.cn)）

洛谷入门赛、洛谷月赛（比赛列表 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)）

牛客周赛（牛客竞赛OJ_ACM/NOI/CSP/CCPC/ICPC_信息学编程算法训练平台 (nowcoder.com)）

二、算法竞赛题目形式

算法竞赛一道题由六个部分组成：题目描述（Description）、输入描述（Input）、输出描述（Output）、输入样例（Sample Input）、输出样例（Sample Output）、更多信息（More Information）

1. 题目描述（Description）

题目背景，题目故事描述，题目操作步骤说明，部分概念的定义和解释

2. 输入描述（Input）

题目的输入格式，输入变量说明，输入数据范围

3. 输出描述（Output）

题目结果的输出格式，输出内容 注意：严格按照要求格式输出

4. 输入样例（Sample Input）

一组或多组满足输入描述格式的数据

5. 输出样例（Sample Output）

输入样例的正确输出结果。可以在本地IDE或在线环境调试输入样例得到输出结果，再跟输出样例进行比对，初步判断自己写的代码是否正确。（往往样例自测全过，一提交就WA了 ╥﹏╥...）

6. 更多信息（More Information）

部分题目会在这部分对输入样例和输出样例进行解释说明，或者题目内部变量的取值范围说明。也有可能会透露解题的核心思路。

三、算法竞赛常见评测状态

AC：Accept，程序通过。

CE：Compile Error，编译错误。

PE：Partially Correct，部分正确。

WA：Wrong Answer，答案错误

RE：Runtime Error，运行时错误

TLE：Time Limit Exceeded，超出时间限制。

MLE：Memory Limit Exceeded，超出内存限制。

OLE：Output Limit Exceeded，输出超过限制。

UKE：Unknown Error，出现未知错误。

hwjw：这样看来还是打IOI赛制爽啊！！(☆▽☆)

shy：我个人认为 IOI > ACM > OI，但具体还要看个人喜好啦（有部分神犇喜欢OI直接看排名的刺激）

xcx：给了好多网站啊，已经迫不及待开始刷题了！！

shy：刷题不要盲目刷题，要按照知识点进行专项练习，做题不要一上来就看题解，要自己思考，要是超过半个小时还没有思路的话就不要死磕了，可以借鉴一下题解的思路，然后自己想想怎么打出代码。刷完题之后还要定期总结各类题型该怎么入手，总结做题时发现的新的知识点，不断地丰富自己的知识储备。