赛事 & 题型

Summary

梳理算法竞赛的赛事、赛制与题型。赛事部分区分 OI 与 ICPC/CCPC 两大体系及其起源，赛制部分对比 OI、IOI、ICPC 与 Codeforces 四种规则在提交次数、实时反馈、罚时和 Hack 机制上的差异。题型部分列出传统题的各类评测结果，如 AC、CE、WA、TLE、MLE 等缩写的含义，并说明交互题、通信题以及输出自身源代码的自产生程序（Quine）各自的特点。

参考资料

• OI 赛事与赛制 - OI Wiki
• ICPC/CCPC 赛事与赛制 - OI Wiki
• 题型概述 - OI Wiki
• 自产生程序 - 维基百科

赛事

OI

信息学奥林匹克竞赛（Olympiad in Informatics，OI）是一门在中学生中广泛开展的学科竞赛，和物理、数学等竞赛性质相同；该竞赛于 1984 年在中国起源，属中国高中五大学科竞赛之一。OI 考查的内容是参赛者运用算法、数据结构和数学知识，通过编写计算机程序解决实际问题的能力。

• NOI 全国青少年信息学奥林匹克竞赛

ICPC

国际大学生程序设计竞赛（International Collegiate Programming Contest，ICPC）由 ICPC 基金会（ICPC Foundation）举办，是最具影响力的大学生计算机竞赛。

• The ICPC International Collegiate Programming Contest
• 中国大学生程序设计竞赛(CCPC)-官网

赛制

OI 赛制

选手仅有一次提交机会。比赛时无法看到评测结果，评分会在赛后公布。每道题都有多个测试点，根据每道题通过的测试点的数量获得相应的分数；每个测试点还可能会有部分分，即使只有部分数据通过也能拿到分数。

CSP-J/S 第二轮、NOIP、省选、NOI 都是 OI 赛制。

IOI 赛制

选手在比赛时有多次提交机会。比赛实时评测并返回结果，如果提交的结果是错误的，不会有任何惩罚。每道题都有多个测试点，根据每道题通过的测试点的数量获得相应的分数。

APIO、IOI 都是 IOI 赛制。目前国内比赛也在逐渐向 IOI 赛制靠拢。

ICPC 赛制

一般是三个人组成一队使用一台机器，在比赛时有多次提交机会。比赛实时评测并返回结果，如果提交的结果错误会有 20 分钟的罚时，错误次数越多，加罚的时间也越长。每个题目只有在所有数据点全部正确后才能得到分数。比赛排名根据做题数来评判，做题数相同的，根据总用时来评判。总用时是每题用时的和。每题的用时是从比赛开始到做出该题的分钟数与该题的罚时之和。

一些 ICPC 相关赛事中，选手允许带一定量的纸质资料；比赛结束前一小时进行封榜，封榜后的提交和排名将无法被其他选手看见。

除 ICPC 和 CCPC 外，众多比赛也采用该赛制，如 LeetCode 周赛及全国编程大赛、牛客小白赛练习赛挑战赛等。

CF 赛制

Codeforces 是一个俄罗斯的在线评测系统，会定期举办比赛。

它的比赛特点是在比赛过程中只测试一部分数据（Pretests），而在比赛结束后返回完整的所有测试点的测试结果（System Tests）。比赛时可以多次提交，允许 Hack 别人的代码（此处 Hack 的意思是提交一个测试数据，使得别人的代码无法给出正确答案）。如果想要 Hack，选手必须要锁定自己的代码（换言之，比赛时无法重新提交该题）。Hack 时不允许将选手程序拷贝到本地进行测试，源代码会被转换成图片。

Codeforces 同时提供另外一种赛制，称作扩展 ICPC（Extended ICPC 或 ICPC+）。在这一赛制中，在比赛过程中会测试全部数据，但比赛结束以后会有 12 小时的全网 Hack 时间。Hack 时允许将选手程序拷贝到本地进行测试。

题型

传统题

评测结果：

• AC（Accepted）：程序通过。
• CE（Compile Error）：编译错误。
• PC（Partially Correct）：部分正确。
• WA（Wrong Answer）：答案错误。
• PE（Presentation Error）：格式错误。
• RE（Runtime Error）：运行时错误。
• TLE（Time Limit Exceeded）：超出时间限制。
• MLE（Memory Limit Exceeded）：超出内存限制。
• OLE（Output Limit Exceeded）：输出超过限制。
• UKE（Unknown Error）：未知错误。

tip

在 ICPC 赛事中，你的程序需要在一道题目的所有测试点上都取得 AC 状态，才能视为通过相应的题目。

在 OI 赛事中，在一个测试点中取得 AC 状态，即可拿到该测试点的分数。

洛谷 P1001 A+B Problem

输入两个整数 $a,b$，输出它们的和。（$|a|,|b|\le{10}^9$）

交互题

交互题近年来没有在省选以下的比赛中出现。

洛谷 P1733 猜数（IO交互版）

交互题。评测机在 $[1,10^9]$ 中选定一个整数，你最多询问 $50$ 次，每次给出一个整数，返回 $0$（猜中）、$-1$（你的数偏小）或 $1$（你的数偏大）。请猜出该数。

通信题

通信题是需要两个程序进行通信，合作完成某项任务的题目。第一个程序接收问题的输入，并产生某些输出；第二个程序的输入会与第一个的输出相关。

洛谷 P12509 【模板】通信题

这是一道通信题，只支持 C++ 语言。请不要使用 C++14 (GCC 9) 提交。

给定两个长度相等（不超过 $10^6$）且 至多 有一个位置的字符不同的 01 串 $S,T$（下标从 $1$ 开始）。Alice 只知道 $S$，Bob 只知道 $T$。

Bob 想要确定 $S,T$ 字符不同的那个位置。为了达成这一目的，Alice 决定偷偷帮助他。

具体来说，Alice 可以向 Bob 传递一个整数 $X$，满足 $X\in[0, 2^{20})$。

特别地，如果 $S=T$，Bob 应返回 0。

UOJ #178. 新年的贺电

你需要写一个程序，实现编码和解码的功能。

自产生程序

自产生程序（Quine）指的是输出结果为程序自身代码的程序。

LibreOJ #4. Quine

写一个程序，使其能输出自己的源代码。代码中必须至少包含十个可见字符。