OI 出题指南
ouuan
2019-06-16 18:35:23
---
本文已在优化、扩充后合并至 OI-wiki，推荐在 OI-wiki 上阅读：<https://oi-wiki.org/topic/problemsetting/>
---
首先，你需要意识到，自己出的题是要**给别人做**的。
请不要说这是一句废话。这是做一名好的出题人必须要明白的。
出题比起展示自己，更是服务他人。
## 题目内容
### 关于原题
原题大致可分为完全一致、几乎一致和做法一致三种。
- 完全一致：使用一题的 AC 代码可以 AC 另一题。
- 几乎一致：由一题的 AC 代码改动至另一题的 AC 代码可以由一个不会该题的人完成。
- 做法一致：核心思路、做法一致，但代码实现上、不那么关键的细节上有差异。
这三种原题自下而上为包含关系。
以下情况不应出现：
1. 在明知有“几乎一致”的原题的情况下出原题。
2. 由于未使用搜索引擎查找导致自己不清楚有原题，从而出了“几乎一致”的原题。
3. 在“做法一致”的原题广为人知（如：NOIp、NOI 原题）时出原题。
4. 在带有选拔性的考试的非送分题中出现“做法一致”的原题。
以下情况最好不要出现：
1. 在明知有至少为“做法一致”的原题的情况下出原题。
2. 由于未使用搜索引擎查找导致自己不清楚有原题，从而出了“做法一致”的原题。
3. 在任何情况下出“几乎一致”的原题。
可以放宽要求的例外情况：
1. 校内模拟赛。
2. 以专题训练为目的的模拟赛。
3. 难度较低的比赛，或是定位为送分题的题目。
### 关于毒瘤题
“毒瘤题”是一个非常模糊而主观的观念，我在这只是引用一些前人关于此的探讨，加以自己的一些理解。这个话题是非常开放的，欢迎大家来发表自己的观点。
> 一道好题不应该是两道题拼在一起，一道好题会有自己的idea —— 而它应该不加过多包装地突出这个idea。
>
> 一道好题应该新颖。真正的好题，应该是能让人脑洞出新的好题的好题。
>
> —— vfk《UOJ精神之源流》
例子：[【XR-1】柯南家族](https://www.luogu.org/problemnew/show/P5346)，做法的前后两部分完全割裂，前半部分为[【模板】树上后缀排序](https://www.luogu.org/problemnew/show/P5353)，后半部分是经典树上问题。
> 一类OI题以数学为主，无论是题目描述还是做法都是数学题的特征，并且解法中不含算法相关的知识点，这类OI题目统称为纯数学题。
>
> —— 王天懿《论偏题的危害》
经典例子：[NOIP2017 小凯的疑惑](https://www.luogu.org/problemnew/show/P3951)
我自己的标准是：尽量不要出数学填空题。但这样的纯数学题也不是完全不可取，有时纯粹地考察一些 OI 常用数学知识也是可以接受的。
> 一部分偏题中牵涉到了大学物理的内容，导致选手在面对这些从未接触过的物理知识点时变得不知所措，造成了知识上的隔膜。
>
> —— 王天懿《论偏题的危害》
经典例子：[【清华集训2015】多边形下海](http://uoj.ac/problem/159)
不止是物理，OI 题目中不应过多涉及到其它学科的知识，如果涉及应当给予详细的解释，不应使其它学科的知识作为解题的重大障碍。
> 一道好题无论难度如何，都应该具有自己的思维难度，需要选手去思考并发现一些性质。
>
> 一道好题的代码可以长，但一定不是通过强行嵌套或者增加条件而让代码变长，而是长得自然，让人感觉这个题的代码就应该是这么长。
>
> —— 王天懿《论偏题的危害》
经典例子：[[SDOI2010]猪国杀](https://www.luogu.org/problemnew/show/P2482)，[【集训队互测2015】未来程序·改](http://uoj.ac/problem/98)
在一般的 OI 比赛中，思维难度应占主要部分。当然，如 THUWC / THUSC 的 Day 2+ 那样的工程题也有其存在的道理 —— 毕竟体验营的目的除了考察选手的算法设计能力，还有和大学学习对接的工程代码以及文档学习能力。但在一般的 OI 比赛中，考察更多的应当还是算法设计与思维能力。
## 题面
### 题目背景
题目背景最好尽量简短。
在题目背景较长时，应当与题目描述分开。
需要绝对避免的情况：题目背景严重影响题意的理解。
必要时，可以提供与背景结合的题目描述与简洁的题目描述两个版本。
### 题目描述
简而言之，题目描述需要**清晰易懂**。
题面中的每个可能不被理解的定义都应得到解释，不应凭空冒出未加定义的概念。例如：在 [CF1172D Nauuo and Portals](https://codeforces.com/problemset/problem/1172/D) 中，你必须在题面中解释什么是“传送门”。
题面中涉及到的每个概念应当使用单一的词汇来描述。例如：不应一会儿说“费用”，一会儿说“代价“。
不应不加说明地使用与原义、常见义不同的词汇。例如：不应不加说明地用“路径”代指一条边。
你需要保证你的题面不会自相矛盾。例如：在 [CF 1173A Nauuo and Votes](https://codeforces.com/problemset/problem/1173/A) 中，没有把 "?" 作为一种 "result"，是因为 "?" 的含义是 "there are more than one possible results"。
你需要保证你的题面不能被错误理解而自圆其说，即使这种理解是反常识、没有人会这么去想的。例如：在 [CF1172D Nauuo and Portals](https://codeforces.com/problemset/problem/1172/D) 中，之所以要繁琐地定义 "walk into" 并与 "teleport" 区分，是为了防止这种理解：通过传送门可以到另一个传送门，而到了传送门会传送，因此会反复横跳。
顺着读题目描述应当能看懂每一句话，并理解题目的任务与要求。至少在紧接着的下一段话中疑惑能够得到解释，而不是需要在若干段后才能得到解释，或者要看了输入输出格式才能明白题意，甚至需要根据样例来猜题意。例如：在 [「GuOJ Round #1」琪露诺的冰雪宴会](https://guoj.icu/problem/1171) 中，在输出格式才第一次出现了题目的目标“雾之湖最终能接收到的最大水量”，再加上“灵梦当然能很快算出来清理完全部小溪的总费用是多少”这句带有误解性质的话，更容易使人读错题意，这是不可取的，应当在题目描述中就对题目的目标进行说明。（在这个例子中还存在题目背景严重影响题意理解的问题。）
### 输入输出格式
输入输出格式清晰**完整**即可，没有死板的要求，个人建议参照 CF 的题目来写输入输出格式，具体可以参考 [cf 出题人须知](https://ouuan.github.io/bad-round-与出题人的坚守/rules.jpg)。
需要特别注意的是，如果输出中含有小数，请尽量使用 SPJ。如果无法使用 SPJ，请保证对精度的要求是有限的。
如果没有保证，对精度的要求可能是无限的。例如：要求保留三位小数，实际答案为 $0.0015$，此时只要有任意大小的误差导致计算出的答案小于 $0.0015$，即使计算出的答案是 $0.0014999999999\cdots$ 也会输出错误的答案。
保证对精度要求有限的例子：请输出答案四舍五入后保留小数点后三位的结果。令标准答案为 $ans$，数据保证对于任意满足 $\frac{|x-ans|}{\max(1,ans)}<10^{-9}$ 的 $x$，四舍五入后结果与 $ans$ 四舍五入后相同。
可以参考的一些句子：
```
输入的第一行包含三个正整数 $n$, $m$, $k$ ($1\le n,m\le 2\cdot 10^5$, $1\le k\le 100$) — $n$ 表示数列的长度，$m$ 表示操作个数，$k$ 的意义见题目描述。
```
```
输入的第二行包含 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$ ($1\le a_i\le 10^9$) — 题目给出的数列。
```
```
接下来的 $m$ 行中的第 $i$ 行包含两个正整数 $l_i$ 和 $r_i$ ($1\le l_i\le r_i\le n$)，表示第 $i$ 次操作在区间 $[l_i,r_i]$ 上进行。
```
```
接下来的 $n-1$ 行，每行包含两个正整数 $u$ 和 $v$ ($1\le u,v\le n$)，表示 $u$ 和 $v$ 之间由一条边相连。
数据保证给出的边能构成一棵树。
```
```
输入的唯一一行包含一个由小写英文字母构成的非空字符串，其长度不超过 $10^6$。
```
```
输入的第二行包含一个小数点后不超过三位的实数 $x$ ($-10^6\le x\le 10^6$)，意义见题目描述。
```
```
输出包含一个实数，当你的输出与标准答案之间的绝对误差或相对误差小于 $10^{-6}$ 时视作正确。
```
```
输出的第二行包含 $n$ 个正整数，表示你构造的一组方案 — 其中第 $i$ 个数表示你打出的第 $i$ 张牌的编号。
如果有多组合法的答案，可以任意输出其中一组。
```
### 数据范围
按照 CF 的要求，数据范围要写在输入格式里，但在国内，数据范围往往是写在题目的最后的。
数据范围中最容易犯的错误就是不完整。输入中的每一个数、每一个字符串都应该有清晰的界定。在上文所给出的输入输出格式示例中就有一些数据范围的正确写法。
数据范围的常见遗漏：
1. “整数”中的“整”。
2. 题面中只说了是“整数”没说是“正整数”，并且数据范围中只有上限没有下限。
3. 字符串没说字符集。
4. 实数没说小数点后位数。
5. 某些变量没有给范围。
你需要保证标程可以通过满足题面所述数据范围的任何一组数据。
### 样例
样例应当有一定的强度，能够查出一些简单的错误。读错题意的人应当能够通过样例发现自己读错了题意。
有多种操作的题，每种操作都应在样例中出现。
有多种输出的题（如 [CF 1173A Nauuo and Votes](https://codeforces.com/problemset/problem/1173/A)），每种输出都应在样例中出现。例外：实际上不可能无解，但要求判断是否有解的题目。
### 样例解释
题目描述越复杂、越不易理解就越应当有详细的样例解释。
题目难度越简单就越应当有详细的样例解释。
详细的样例解释可以选择配上图片。
较大的样例可以没有样例解释。
为了照顾色觉障碍者，最好不要使颜色成为理解样例解释所必备的。可以用彩色图片来美化样例解释，但如果一定要用颜色传递一些必要的信息，最好不要同时出现红黄或者红绿。
## 时限、空间限制与部分分
时限与空间限制的目的是卡掉复杂度错误的做法。（当然，也是为了防止评测用时过长，如：只对交互次数有限制而对时间复杂度没有限制的交互题也有时间限制。）
因此，原则上时间限制应当选取不使错误做法通过的尽量大的值。
一般地，时限应满足以下要求：
1. 至少为 std 在最坏情况下用时的两倍。
2. 如果比赛允许使用 Java，应使 Java 能够通过。
3. 不应使错误做法通过（实在卡不掉、想放某种错解过除外）。
为了更好地在放大常数做法过的同时卡掉错解，一般可以采用同时增大数据范围和时限的方法。但要注意，有时正解（由于缓存等玄学问题）会在数据范围增大时有极大的常数增加，此时增大数据范围不一定能够增大正解与错解之间用时的差距。
在有部分分的赛制中，还可以通过设置有梯度的数据、数据范围稍小的数据来使较为优秀的错解和大常数正解不能通过，同时使其获得较高的部分分。
需要注意的是，在数据范围小于 $5\cdot 10^5$ 时，应当考虑是否能使用[指令集](https://ouuan.github.io/n方过百万-暴力碾标算——指令集优化的基础使用)通过。
一般情况下空间限制应当设置的足够大，除非空间复杂度更优的做法的确十分巧妙，值得卡掉空间复杂度大的做法。这种情况下可以考虑设置空间限制较松的部分分。值得注意的是，如果不想卡掉空间消耗较大的做法，数据结构题一般需要设置较大的空间限制。
> 一道好题应该具有它的选拔性质，具有足够的区分度。应该至少4档部分分，让新手可以拿到分，让高手能够展示自己的实力。
>
> —— vfk《UOJ精神之源流》
部分分一般分为较小数据范围与特殊性质两种。
较小数据范围一般要设置多档，即使你想不到某种复杂度的做法，也可以考虑给这种复杂度一档分。一般来说，为了避免卡常，可以设置一档极限数据除以二的部分分。
“数据有梯度”最好用多档部分分替代。
特殊性质部分分的设置要依具体题目而定。理想的特殊性质部分分应当是能够引导选手思考正解的。与较小数据范围部分分不同，在你不会针对某种特殊性质的做法时，最好不要给这种特殊性质一档分。例如：[[CTS2019]随机立方体](https://www.luogu.org/problemnew/show/P5400) 的 $k=1$ 这档部分分在讲题时就被很多人吐槽，称这档部分分妨碍了思考正解。
如果不是测试点等分且总分为测试点得分相加（如：绑 Subtask 测试），一定要在题面中说明。
## 数据
### 数据的多样性与强度
在不绑 Subtask，按测试点给分时，本部分内容可以酌情不遵守。
数据中应当包含每个变量的最小值与最大值。
数据中应当包含各种各样的构造，即使你不知道什么错解会挂在这组构造上。
当然，如果你已知一个（正常人能想的到、写的出的）正确性有问题的错解，要尽量卡掉它。（时间复杂度有问题的错解已在上文讨论过了。）
需要特别提醒的是，如果有整型溢出的可能，一定要卡掉会溢出的做法。在有部分分的赛制中，不应使不开 long long 的人得到和暴力一样甚至更低的分数。
### 如果有 pretests
pretests 应尽量强（，同时尽量少）。换言之，你需要在 pt 中（用尽量少的数据组数）包含该题的所有已知叉点。（括号中为个人观点。）
如果你希望出现少量而非没有 fst，你可以问问 Sooke 对这件事的看法（Sooke 曾经坚称“fst 是 CF 的灵魂”，在我的强烈要求下，在 [CF1172A Nauuo and Cards](https://codeforces.com/problemset/problem/1172/A) 中，他构造了许多数据，在 pt 中卡掉了所有已知错解，最后，这题在比赛中 Div.2 的 fst 率为 $18.5\%$）。
### 使用 testlib.h 造数据
在平常的出题中使用 [Polygon](https://polygon.codeforces.com/) 可能不是最为方便的选择（事实上如果是多人协作出题，即使不是出 cf，使用 Polygon 依然是非常棒的选择），但 Polygon 为我们提供的出题方式十分值得借鉴。
简而言之，在 Polygon 中，数据要么是手造，要么由 generator 生成。而这个 generator 使用 [testlib.h](https://github.com/MikeMirzayanov/testlib)，并且使用命令行参数来设置数据范围、构造类型等参数。
使用 testlib.h 的好处是，它内置了随机数生成器 `rnd.next()`，它在不同平台上返回同样的结果，并且其种子是基于整个命令行参数生成的，不用手动设置种子，并且在参数一样时生成的数据总是一样的。
使用命令行参数的好处是，你可以写一个 .bat 文件（或者 Linux 下的 .sh 文件），把生成数据的命令写进去，可以十分方便地生成数据。
一个简单的 generator 例子：
```cpp
// gen.cpp
#include "testlib.h"
using namespace std;
int n, m, k;
vector<int> p;
int main(int argc, char* argv[])
{
registerGen(argc, argv, 1);
int i;
n = atoi(argv[1]);
m = atoi(argv[2]);
k = rnd.next(1, n);
for (i = 1; i <= n; ++i) p.push_back(i);
shuffle(p.begin(), p.end()); // testlib.h 自带的 random_shuffle，使用 rnd.next() 进行 shuffle
printf("%d %d %d\n", n, m, k);
for (i = 0; i < n; ++i) printf("%d%c", p[i], " \n"[i == n - 1]); // 把字符串当作数组用，中间空格，末尾换行，是一个造数据时常用的技巧
return 0;
}
```
```bash
gen 10 10 > 1.in
gen 1 1 > 2.in
gen 100 200 > 3.in
gen 2000 1000 > 4.in
gen 100000 100000 > 5.in
```
[官方 generator 教程](https://codeforces.com/blog/entry/18291)。
如果你愿意，还可以写一个 validator。validator 是用来检查数据合法性的，在 cf 赛制中由于 hack 的存在是必备的，而在其它赛制中，validator 相当于给数据上了一道保险锁，个人十分推荐写一个 validator。
[官方 validator 教程](https://codeforces.com/blog/entry/18426)。
最后推荐一个我自己经常使用的生成输出文件的 bat：
```bash
@echo off
for /R "%cd%" %%i in (*.in) do (
echo %%i
validator < %%i
if errorlevel 1 pause
std < %%i > %%~ni.out
)
pause
```
## Special Judge
输出方案题和输出浮点数题是两种较为常见的需要使用 SPJ 的题型，其它题目视情况也需要使用 SPJ。在 CF 上，所有题目都必须使用基于 testlib.h 的 checker，例如：题目要求输出若干个整数时，你可以任意输出空白字符（既可以空格也可以换行）。
checker 一般使用 testlib.h 编写，[在 lemon 中也可以使用 testlib.h](/使用-testlib-h-写-lemon-SPJ/)。一般来说，不使用 testlib.h 是很难写好 checker 的，因为你要应对各种各样的不合法输出，需要极强的鲁棒性。
编写 checker 需要注意以下两点：
1. 你需要应对各种不合法的输出，因此，请检查读入的每个变量是否在合法范围中（`readInt(minvalue, maxvalue)`）。例如：读入一个在 check 过程中会作为数组下标的变量时必须检查其范围，否则可能引发数组越界，有时这会导致 RE，有时则可能判为 AC。
2. 原则上 checker 中不应检查空白字符（即，不应使用 readSpace()、readEoln()、readEof()，值得一提的是，testlib.h 会自动检查是否有多余的输出）。
[官方 checker 教程](https://codeforces.com/blog/entry/18431)。
## 题解
题解的目标是让预计会来参加比赛的人都能看懂。所以官方题解详细程度的要求会比一般的题解高。
### 关于部分分
在有部分分的题目中，题解里可以考虑写一写部分分的做法。
### 关于知识点
解题中用到的知识点应当写出来。对于一些难度和题目难度相当的知识点，最好给出学习该知识点的资料（比如一篇博客的地址）。“这样，再这样，然后**用一些技巧**就可以了”，而其中的“一些技巧”并不是谁都会的，这种情况要绝对避免。
### 关于定义
题解中不要凭空冒出来一些概念。
例如：dp 的题解要解释清楚状态的定义。
再例如：cy 曾经写过一版 [CF1172F Nauuo and Bug](https://codeforces.com/problemset/problem/1172/F) 的题解，其中对“分段函数”没有定义，这是绝对不可取的。
### 关于细节
具体的实现细节如果比较巧妙最好写出来，否则的话“详见代码”也是可以的。如果“详见代码”的话，最好在代码中加上一定的注释。
### 标程
标程中最好去掉冗余部分。比如，有人在题解中保留了完整的 define 模板（为了提高做题速度，包含大量 define 与常用函数，常用于 CF 等在线比赛），并且其中很大一部分都没有用到，这是不好的。
上文已经说过了，如果涉及到一些题解中没有详细说明的实现细节，最好加上适量的注释。
## 比赛
### 比赛通知中的题目难度需真实
感觉这个是比赛通知中比较需要注意的一点。
如果不会评难度可以不评..
> Remember that authors tend to underestimate the difficulty of their problems.
>
> —— Codeforces PROPOSE A PROBLEM 页面的提醒
需要特别强调的是，如果你以 CF 的难度来进行类比（如：该比赛为 Div.2 A ~ Div.2 E 难度），不仅是难度需要与 CF Div.2 类似，题型也应当是 CF 风格。
### 题目难度的分配
在类国内 OI 的模拟赛中，往往是三道题的整体难度与比赛难度相当即可。
在类 CF / ATC 这种线上赛的比赛中，需要尽量保证难度的递增（虽然由于对难度的误估很多时候都并不能真正做到），并且尽量避免出现大的 difficulty gap。可以通过把一题分为难易两题（两个 Subtask）来减少 difficulty gap。
### 题目知识点的分配
一场比赛应尽量涵盖较广的知识点（专题训练赛当然除外）。
经典反例：涵盖了动态规划、期望、组合计数、容斥原理、多项式等多种知识点的 CTS2019。（~~组题人：我要从五道题里选六道，我也很无奈啊。~~）
## 参考资料
1. [vfk《UOJ精神之源流》](http://vfleaking.blog.uoj.ac/blog/909)
2. [王天懿《论偏题的危害》](https://ouuan.github.io/ouuan-的出题规范/7-王天懿-论偏题的危害.ppt)
3. [cf 出题人须知](https://ouuan.github.io/bad-round-与出题人的坚守/rules.jpg)
4. [vfk 博客](https://blog.csdn.net/VFleaKing/article/details/90521383)中的[CF出题人的自我修养](https://www.luogu.org/paste/sxvu97yz)