算法竞赛命题指南(命题流程、Polygon的使用等)

本文主要讲述人经验，可能与实际理解存在偏差，亦有片面的观点，还请见谅！ 部分内容引自OIWIKI：https://oi-wiki.org/

一.引言

命好一场题目，是一个艰巨的任务。它非常考察个人水平和团队合作能力。在出题前，你应该做好以下准备：

抱有认真负责的态度

出题是给别人做的，比起展示自己，更多是为了是服务他人。算法竞赛是选手之间的竞赛，而不是出题人与做题人之间的较量。因此，出题不应以考倒选手为目标（当然，适当的防 AK 与良好的区分度也是非常重要的），而应当让选手能在比赛中有所收获。花费足够的时间精力去学习如何出题并认真负责地出题非常重要。

在命题前，请与命题团队认真开讨论会，确定比赛的定位，讨论比赛的受众群体，设计、划分题目的难易度，设计每道题目的考察知识点等等。请重视讨论会，没有良好的沟通，题目质量必然参差不齐，带来糟糕的比赛体验。

做好耗费大量时间的准备

如果想要认真地出题，就必然要花费大量的时间。如果不做好心理准备，可能导致比赛准备匆忙，质量不过关，也可能在事后由于没有将时间花费在学习上而懊悔。但出题也可以带来很多美好的回忆，如果真的对出题抱有兴趣，并做好了充分的心理准备，出题带来的收获也能够弥补那些花费的时间。

如果要准备一场标准ICPC比赛(校赛级别)，请至少在赛前1个月开始命题计划。如果准备一场选拔赛，请至少在赛前半个月开始命题。短期准备命制的题目可能不乏有好题，但垃圾题会比好题多的多！如果赛前几天才开始命题，你将面临一场充满锅和抱怨的比赛，此时建议直接拉原题，不要在花心思去准备新题。

命题组的沟通

一般而言，不建议5人以上同时命制一场比赛，众口难调，作为比赛的组织者会非常被动，从而导致比赛题目难度不一。

请务必于组内成员保持良好的沟通！并选择尽可能熟悉的人来命题。

二.大脑篇

想命好一道题目，是非常考察命题者的综合素养的。

你需要具备一定的刷题量，通过刷题你可以了解设计题目的各种小 t r i c k trick trick，以及想到一些合适的 i d e a idea idea;

你需要拥有清晰的命制思路，确保命制过程严丝合缝，否则你会命出一道锅题;

你需要有至少清晰的表达能力，能表达你的题目意图而不产生歧义;

你需要了解并熟练运用各种工具，以命制符合规格的题目;

…

1.idea 的来源

1. 受到已有题目的启发（但不能照搬或无意义地加强，如：序列题目搬到仙人掌上）。
2. 受到学过的知识点的启发（但不能毫无联系地拼凑知识点）。
3. 从生活/游戏中受到启发（但注意不要把游戏出成大模拟）。
4. 不知道为什么，就是想到了一道题。

2.什么样的 idea 是不好的 关于原题

原题大致可分为完全一致、几乎一致和做法一致三种。

• 完全一致：使用一题的 AC 代码可以 AC 另一题。
• 几乎一致：由一题的 AC 代码改动至另一题的 AC 代码可以由一个不会该题的人完成。
• 做法一致：核心思路、做法一致，但代码实现上、不那么关键的细节上有差异。

这三种原题自下而上为包含关系。

以下情况不应出现：

1. 在明知有“几乎一致”的原题的情况下出原题。
2. 由于未使用搜索引擎查找导致自己不清楚有原题，从而出了“几乎一致”的原题。
3. 在“做法一致”的原题广为人知（如：NOIP、NOI 原题）时出原题。
4. 在带有选拔性的考试的非送分题中出现“做法一致”的原题。

以下情况最好不要出现：

1. 在明知有至少为“做法一致”的原题的情况下出原题。
2. 由于未使用搜索引擎查找导致自己不清楚有原题，从而出了“做法一致”的原题。
3. 在任何情况下出“几乎一致”的原题。

可以放宽要求的例外情况：

1. 校内模拟赛。
2. 以专题训练为目的的模拟赛。
3. 难度较低的比赛，或是定位为送分题的题目。

关于毒瘤题

“毒瘤题”是一个非常模糊而主观的观念，在这只是引用一些前人关于此的探讨，加以自己的一些理解。这个话题是非常开放的，欢迎大家来发表自己的观点。

一道好题不应该是两道题拼在一起，一道好题会有自己的 idea——而它应该不加过多包装地突出这个 idea。

一道好题应该新颖。真正的好题，应该是能让人脑洞出新的好题的好题。

——[vfk《UOJ 精神之源流》][1]

例子：「XR-1」柯南家族，做法的前后两部分完全割裂，前半部分为 「模板」树上后缀排序，后半部分是经典树上问题。就算是随意输入树的点权，依然可以做第二部分，前后部分没有联系。

一类 OI 题以数学为主，无论是题目描述还是做法都是数学题的特征，并且解法中不含算法相关的知识点，这类 OI 题目统称为纯数学题。

——[王天懿《论偏题的危害》][2]

经典例子：NOIP2017 小凯的疑惑

OI 中的数学题与其它数学题的区别，也是体现 OI 本质的一个特点，是 OI 中的数学题往往重点不在答案 是什么，而在如何 加快 答案的计算。如果一道题考察的重点是“怎么算”而非“怎么快速计算”，这样的数学题一般都是不适合出在 OI 中的。

一部分偏题中牵涉到了大学物理的内容，导致选手在面对这些从未接触过物理知识点时变得不知所措，造成了知识上的隔膜。

——[王天懿《论偏题的危害》][2]

经典例子：「清华集训 2015」多边形下海

不止是物理，OI 题目中不应过多涉及到其它学科的知识，如果涉及应当给予详细的解释，不应使其它学科的知识作为解题的重大障碍。

一道好题无论难度如何，都应该具有自己的思维难度，需要选手去思考并发现一些性质。

一道好题的代码可以长，但一定不是通过强行嵌套或者增加条件而让代码变长，而是长得自然，让人感觉这个题的代码就应该是这么长。

——[王天懿《论偏题的危害》][2]

经典例子：「SDOI2010」猪国杀，「集训队互测 2015」未来程序·改

在一般的 OI 比赛中，思维难度应占主要部分。当然，如 THUWC/THUSC 的 Day 2+ 那样的工程题也有其存在的道理——毕竟体验营的目的除了考察选手的算法设计能力，还有和大学学习对接的工程代码以及文档学习能力。但在一般的 OI 比赛中，考察更多的应当还是算法设计与思维能力。

三.题面篇 本部分引自 OI-Wiki：出题 - OI Wiki (oi-wiki.org) 1.题目背景

题目背景最好尽量简短。在题目背景较长时，应当与题目描述分开。

需要绝对避免题目背景严重影响题意的理解。

必要时，可以提供与背景结合的题目描述与简洁的题目描述两个版本。

2.题目描述

简而言之，题目描述需要 清晰易懂。

题面中的每个可能不被理解的定义都应得到解释，不应凭空冒出未加定义的概念。例如：在 CF1172D Nauuo and Portals 中，你必须在题面中解释什么是“传送门”。

题面中涉及到的每个概念应当使用单一的词汇来描述。例如：不应一会儿说“费用”，一会儿说“代价“。

不应不加说明地使用与原义、常见义不同的词汇。例如：不应不加说明地用“路径”代指一条边。

你需要保证你的题面不会自相矛盾。例如：在 CF1173A Nauuo and Votes 中，没有把 “?” 作为一种 “result”，是因为 “?” 的含义是 “there are more than one possible results”。

你需要保证你的题面不能被错误理解而自圆其说，即使这种理解是反常识、没有人会这么去想的。例如：在 CF1172D Nauuo and Portals 中，之所以要繁琐地定义 “walk into” 并与 “teleport” 区分，是为了防止这种理解：通过传送门可以到另一个传送门，而到了传送门会传送，因此会反复横跳。

顺着读题目描述应当能看懂每一句话，并理解题目的任务与要求。至少在紧接着的下一段话中疑惑能够得到解释，而不是需要在若干段后才能得到解释，或者要看了输入输出格式才能明白题意，甚至需要根据样例来猜题意。例如：在 「GuOJ Round #1」琪露诺的冰雪宴会 中，在输出格式才第一次出现了题目的目标“雾之湖最终能接收到的最大水量”，再加上“灵梦当然能很快算出来清理完全部小溪的总费用是多少”这句带有误解性质的话，更容易使人读错题意，这是不可取的，应当在题目描述中就对题目的目标进行说明。（在这个例子中还存在题目背景严重影响题意理解的问题。）相同的错误还出现在 CF1423(4)N Bubblesquare Tokens 中，在输出格式才第一次出现了题目的目标 “friend pairs and number of tokens each of them gets on behalf of their friendship”。

3.输入输出格式

输入输出格式清晰 完整 即可，没有死板的要求，个人建议参照 CF 的题目来写输入输出格式，具体可以参考[CF 出题人须知][3]。

为了方便选手做题，输入输出格式中最好说明每个变量的具体含义，除非变量的意义非常长，没法一句话说清楚（这时可以说“意义见题目描述”）。

需要特别注意的是，如果输出中含有小数，请尽量使用 SPJ 来对误差的大小进行限制，而非要求“保留 x 位小数”。

“保留 x 位小数”对精度的要求可能是无限的。例如：要求保留三位小数，实际答案为 0.0015 0.0015 0.0015，此时只要有任意大小的误差导致计算出的答案小于 0.0015 0.0015 0.0015，即使计算出的答案是 0.00149999 ⋯ 0.00149999\cdots 0.00149999⋯ 也会输出错误的答案。

如果无法使用 SPJ，请保证对精度的要求是有限的，例如：请输出答案四舍五入后保留小数点后三位的结果。令标准答案为 a n s ans ans，数据保证对于任意满足 ∣ x − a n s ∣ max ⁡ ( 1 , a n s ) < 1 0 − 9 \frac{|x-ans|}{\max(1,ans)}{${statement.path}}}