我的出题记录

NOIP 2021 T3

链接：https://www.luogu.com.cn/problem/P7962

在写这一段之前，我诚挚地向因为本题的数据受到影响的所有选手道歉。

出好此题并提交题面之后，我突然发现此题的数据十分难造，难以卡掉所有错误的算法。于是我向负责命题的 yyl 说明了这一点。但是，选题人最后还是决定选了我的题。由于我在造数据方面的经验和方法不够，我并没有想到开多测、写模拟退火与正解对拍等常见的方法。我只是简单地造了我给的算法所对应的极端数据，没有对其它可能的思路做充分的思考。

考试结束那一天，我所预料到的事情还是发生了，很多选手表示通过”乱搞“通过了我场上给的大样例。出数据的那天，选手对此题提出了很多了不合理之处，其中不乏情绪比较激动的选手。

我必须承认当时的我不是一个勇敢坚定的人。那几天之后我认真思考过我究竟应该继续在官方比赛里面出题。或许是突如其来的消息让我本能性的回避，或许是害怕承担责任，抑或是害怕更多的选手，甚至是我认识的选手因我的失误而折戟。只是“你这次的数据已经无法改动的，唯一能做的就是再出一道好题来补偿这次的失误”这句话点醒了我。可以说这句话是支撑我完成今后出题工作的全部，我希望我之后的工作确实对得起这句话。

也是从那次起，我发现我的角色并不是一场游戏的玩家，而是一个亲手决定选手命运的人。每一个小失误都可能造成不合理的区分度，不合理的比赛效果。而这背后是无数选手的努力因出题人的失误而付之东流。既然在役期间我不愿看到身边的选手以这种方式退役，我就要尽力确保题目设计是合理的，让选手不受非水平因素的困扰，最大限度地发挥自己的水平。

AHOI 2022 T4/LNOI 2022 T3

链接：https://www.luogu.com.cn/problem/P8341，https://www.luogu.com.cn/problem/P8367

出这题是我最辛苦的一次命题经历。因为疫情的缘故，很多省份不得不退出联合省选，改为独立命题。于是我们接到任务：在五一节的时候给多个省出一套带有六个题的卷子。Itst 在五一节前两周左右拉了我们这一届的选手，组建了命题组。然而疫情变化莫测的局势导致了许多省加入又退出了这套卷子的覆盖范围，最后只剩下安徽一个省孤零零地走完了全程，不免生出悲壮苍凉之感。我们想出了9题左右，淘汰了一些过难的题目和重复知识点的题目，选出了6题（其中被淘汰的某一道题目变成了 CTS 2023 的 D2T2）。最后 AHOI 再一次延迟，赛制由两天六题改为一天四题。于是我先前提供的两道题一道被放在了 AHOI 2022 T4，一道放在了 LNOI 2022 T3。

初步设计完题目之后，我发现这道题的数据也很难造。如果直接随机的话，几乎所有错误算法都能够通过。出于对重蹈覆辙的恐惧，我写了大部分的部分分算法和一些会 TLE 或者 WA 的算法。我开了多测，并且把我能想到的构造数据和上百组随机的小数据悉数加入测试点。部分分的繁多导致了我需要写多个不同的生成器，最后写了将近 30K 的代码。

曾多次向 Itst 表示自己完不成工作的我，终究还是突破了自己的极限。我连着几天从早上八点赶工到到晚上十一点多，连着几夜在床上仍思考着 idea 和数据生成方法。记得那天晚上我旁听完微分几何课之后，跑到一间自习教室，一个人对着电脑调着代码，丝毫未察觉学生的离去和保安的到来。我没想到第一次成为最晚出教学楼的人，竟然是为了出题。

AHOI 那题的题面是我写的唯一带很长背景的题面。我想以题面中的角色指代退役选手，用他们的口吻来表达我们对自己 OI 生涯的回忆和目睹 OI 发展的一些感受。我不能说很多话，毕竟这是考题的题面。我只希望寥寥数语能表达我所理想中的 OI 发展的状态，我所理解的 OI 知识与大学知识的异同。希望看到此题的选手们能够理解出我的意思。

讨论此题时 Itst 和我基本上想到了相同的思路，验题人想了另外一种贪心 + 数据结构的做法，考场上唯一过了的人又用了第三种贪心 + 数据结构的做法。赛后的 myh 和我的学弟 zx 也使用了这种算法。几天之后，我看到洛谷上竟然又出现了一种不用数据结构的线性做法，时间和空间都远胜于我的标程。他们的思考成果，和我自己的思考一样都让我欣慰。或许当这题被扔到比赛之后，它就不再属于出题人自己了，而是选手们训练、思考的起点。是选手们的思考让这题有了更丰富、更优美的内容。OI 是选手们的 OI，也是出题人的 OI，但终究还是选手们的 OI。这也正好应了题目背景里的那段话。

NOI 2022 D2T2

链接：https://www.luogu.com.cn/problem/P8500

其它资料：https://www.bilibili.com/read/cv18339107?spm_id_from=333.999.0.0

想完这题的题面和做法之后，我发现这题的做法需要用到两到三个不同的观察，结合所有的观察才能够做出此题。自然地，我希望给想出部分性质的选手一些分数，同时也照顾大部分的选手。经过了一段思考，我才设计出合适的”特殊性质”部分分来反映选手推出了哪些性质。而这道题的特殊性质 A，B 又恰好有 DP 的做法，能够让本题的得分对应思考程度的曲线平缓一些。

其实，并不是所有的试题都能够设计出平滑的部分分的。有时候我们很难把一个思路上未完成的正解对应一个较劣时间复杂度的算法或是特殊性质的部分分。很多情况部分分的思路无法与正解完全匹配。甚至对有些问题来说，选手要么拿到暴力分，要么拿到满分，即使离正解仅一步之遥也只能和暴力同分。而官方比赛的特点决定了它的试题需要有较为平滑的部分分。因此，我常常会因为一个问题难以设计部分分，不适合放在 OI 赛制比赛中而不得不忍痛割爱。对我和对选手都非常幸运的是，这个模型的性质和解法本身的结构决定了它能设计出丰富而恰当的部分分。

出这题的过程比较顺利，但这题几经波折之后才进入比赛。一开始，组题人决定了将此题放在 NOI 中，我也得以能够 NOI 现场从事监考、押运试题、分析得分情况等工作。可二附中毕业选手的身份让 CCF 害怕此题的保密性问题，或是害怕我被怀疑泄密。于是他们决定把我的题换成另外一道题目，并建议我不要来 NOI 现场。反转在 D2 考试的前一天晚上来临了。CCF 打算重新使用我的 D2T2，以平衡 D1 的难度，挽救 D1 不太高的区分度。工作人员们紧急讨论，最终决定启用这套方案，并增加了这道题的前几档部分分，使这场 D2 变成了现在看到的样子。

虽说我已是退役选手了，NOI 2022 也是我印象最深刻的一次 NOI。一是看到我的题目被绝大多数选手点赞，一些 D1 发挥失常的选手纷纷靠此题翻盘。我希望这能够弥补 NOIP 2022 犯下的失误，对得起电话里的那句话。二是听闻了母校进了六个集训队的好消息。我很感谢教练的付出，也佩服学弟们的强大。我希望母校能抓住 OI 大环境的变化所带来的机遇，再续 NOI 2022 的辉煌。三是本次 NOI 的活动策划无疑是最丰富、最精彩的一次。作为时常与 gyf，wc 见面的同校同学，我能体会到他们费尽了大量的心血，施展了全部的才华，把自己对 OI 乃至人生的理解融入到了节目策划里面去。虽说碍于身份原因无法与选手面对面交流，无法近距离欣赏他们的作品，参与他们策划的活动，观看录制的视频也足以带来厚重的回忆。

CTS 2022 D2T3

链接：https://uoj.ac/problem/791

其它资料：https://uoj.ac/problem/787

由于时间充裕，出 CTS 2022 D2T3 并不需要赶工，但是出这题应该是我思考时间最长的一次。在想出 idea 之后，我花了不长的时间想出了一个 \(O(n \log n)\) 做法，但是当时的我并不确定这题最好能够做到多好。于是接下来几天，我连着想了几个不同的想法，它们有的只能做到 \(O(n \log n)\)，有的只适合随机数据。幸运的是（但对选手不幸的是），灵感在某一天的晚上出现了，我把众多 \(O(n \log n)\) 做法中的一种优化到了 \(O(n)\)。这个技巧我依然觉得非常的巧妙。要是我那天并没有恰巧想到这一个点，兴许我就尝试说服自己这个问题的极限就是 \(O(n \log n)\) 了，然后假装自己完全解决了此问题。

除了负责本题的命制之外，我也负责了比赛的选题和 D1T2 一题的讨论。在与 E.space 讨论中我发现了另一种做法，这种做法略优于他原先的做法。快睡觉时我不经意地在 QQ 上对他说："这么说说不定还有优化空间？比如说可不可以尝试把我的想法与你的想法结合？"

正是这句话，让他又思考了几天的时间，得出了一个我都很难看懂的做法，并令有人通过的题目数量再度减少。

可惜这场比赛也有一些缺陷。赛后某位我认识的 MO 选手说 D1T1 正好和 2021 俄罗斯数学竞赛的最后一道题撞了。这点是我和出题人怎么也料想不到的。除非我早生一年，那时候我才会是数竞的现役选手，才有可能发现这道重题。其次是 WC 的选手反映 T1 不给 SPJ 导致调试验证比较困难，花费大量时间。WC T3 的题面和 sample 代码都出现了一些小错误，这点我感到很愧疚。

换了视角的赛场，依旧热血澎湃。在选手们考 D2 时，我的内心也从未停歇过。一是祈祷我的学弟们能在此次比赛中创造我在役时未创造的奇迹。看到 gyr 的 D2T1 代码里面有线段树，我一度以为她想出了那题的正解并马上会交上去。看到 ix35 有很长一段时间迟迟没有提交，我也一度认为他还在调某道题的正解，又有些担心他能否在比赛前调完。比赛的最后几分钟我依然想过：ix35 一直是 D2 选手，他 D1 这么好了 D2 一定会交上某题的满分代码翻盘的。虽然我祈祷的奇迹全都没有发生，但我也认为他们已经非常不容易了。我一直很佩服学弟们取得的成绩，和那种坚持战斗到最后一刻的勇气。二是观望 rk 4 与 rk 5 之间激烈胶着的战斗。D1 时 lyp 在最后十分钟交了 T2 的最高分代码，翻到了 rk4，D2 时 wxw 又在最后十分钟用常数优秀的平方算法拿到 T1 的 70 分，重回 rk4 的位置。正当我们都以为一切已经尘埃落定时，答辩又来了一记惊天大反转。

NOI 2023 联合省选 D2T2

链接：https://www.luogu.com.cn/problem/P9170，https://uoj.ac/problem/803

此题的 idea 是从做六级匹配题被卡住时得来的。众所周知，匹配题是要将每个空填入适当的词语，且题目规定了每个空匹配的选项互不相同。我确定了某些空应该填什么，但某些空我则在两个不同词语之间犹豫。自然，我盘算着在题目保证每个空填的选项不相同，而我可以填相同选项的情况下，我可以怎样填写答案，使得我在最坏情况下的得分最大。

经过思考，我发现对这个最优化问题，建图之后它有一个 \(O(n^3)\) 的 dp 做法和 \(O(n^2)\) 的 dp 做法，而一个关键的观察可以直接告诉我们答案其实就与基环树的环长，树的直径相关，得到一个 \(O(n)\) 做法。但一个只要猜出结论就能通过的题似乎不太适合显然出在正式比赛中。我不得不尝试着对此问题进行改造、推广，在脑中产生了五六个不同的 generalization。这六七个改版的问题，有的依然不适合出在比赛中，有的没有找到多项式算法，只有一个版本是合适的。最终，我把这个推广的问题出了出来，而推广前的版本放在了特殊性质 D 里面。原先 \(O(n^3)\), \(O(n^2)\) 的两个解法依然适用，但选手要完整做出这个推广的问题，他就不能仅靠猜测答案的公式，而是要推出那个关键的观察。

在此解释一下改造的过程。其实原问题可以被转述为做题的人 (Alice) 与给答案的人 (Bob) 的博弈问题。此时 Alice 第 \(i\) 个空的可能答案列表 \(S_i\) 与 Bob 第 \(i\) 个空答案列表 \(T_i = S_i\) ，填答案的人 (Alice) 需要规划她填的答案（允许相同），使得在给答案的人 (Bob) “与她作对” 的情况下她的得分能够最大化。如果我们保留 \(1 \leq \lvert S_i \rvert, \lvert T_i \rvert \leq 2\) 这个条件，但去掉 \(S_i = T_i\) 这个条件，得到的问题就是省选 D2T2 了。

但我不得不指出的是，由于各种原因，这场比赛的 D2 并没有发挥它应有的正向区分的效果。D2T1 的细节比较多，码量并不小，选手的时间会耗费在此题上。而 D2T2 码量也比较大，D2T3 又是不可做的题。选手可能会因为细节问题和常数问题失去 D2T1 的大量分数，可能会因为 D2T1 的原因没有充分时间思考、实现 D2T2，甚至可能会在 D2T3 上耗费无用的时间。这都极大的增加了 D2 的随机因素。也许把 D2T3 换成其它的题，或者调换一下 D1 与 D2 的题序，D2 的效果会好一些。

NOI 2023 D1T1/D1T3

链接：https://www.luogu.com.cn/problem/P9480，https://www.luogu.com.cn/problem/P9478

其它资料：https://www.luogu.com.cn/blog/flyingfan/noi2023-you-ji-da-gong-ren-shi-jiao-ban-post

省选征题的顺利使我未曾料到命题危机出现在了最重要、最严肃的比赛——NOI 上。选题会议前，我们甚至连 6 道题都没有征集到。听到此消息的我甚至担心过 NOI 能否如期举办的问题，但所幸一周之后我们还是征集到了足够的题目。

这一周的命题过程几经波折。psj 和 yyl 在 ddl 缠身的情况下，联系了所有可能联系到的人，其中也包括我。一开始 psj 出出来的初版问题被 lbt 发现不太合适，改版的问题又发现做法有点问题。正当我以为这个 idea 将要夭折时，他想出了合适的问题。我想出的第一个 idea，刚要出出来，就发现它与最近的 CF 题撞车了，不得不从头再来。庆幸的是短时间之内，我硬是通过枚举简单模型的组合，重新生成了一道合适的题目，成为了比赛的 D1T3。最后我们缺一道简单题，yyl 就给了一个 idea，我将它出成了本次的 D1T1.

此次比赛中，我看到了两点进步，一是 CCF 推出了 selfeval 自测程序， 使选手不至于因为空间超限等小错误而失掉大量分数。二是在 psj 给我看他的题面之后，我和 zyy 决定在测试数据里面输入测试点编号。这样写部分分的选手不用花大量时间写数据分治，可以投入更多的时间在更有意义的思考上。然而，我们工作的结果也并未让所有选手满意，区分度的问题依然严重。我希望下次的征题能够顺利，也希望在下次的比赛中，我们能够想出更合理的给部分分的方法。

很遗憾我又没能来到 NOI 的现场。但看到一位来到现场的验题人的游记，依然带给我许多的感动。在此我不必多言，只希望读者看一下她的游记。这里放一段她的原文：

“ 21年曾许愿能再来 NOI，今年终于实现了。这几天我有幸认识了 yyl，zyb, EI, Itst, LCA 这些曾经取得过出色成绩，如今又回来为 OI 发光发热的选手（曾经传说中的名字出现在面前还是很神奇），在和他们的交流中我对 OI 比赛的理解加深了很多，也了解到一场场比赛背后有多少努力付出，很羡慕他们能深度参与 OI。因为我的 OI 时光太短，OI 于我像一场梦，我于 OI 似是过客。当然更多的是对他们的钦佩与感谢，有一代代这样的 OIer 在，可以期待 OI 会变得更好吧。”

对出题工作的一些思考

相关资料：https://oi-wiki.org/contest/problemsetting/

出题的宗旨

个人认为，出题的宗旨不外乎两点。一是分享、传播一个有意思、有价值的知识、模型或方法，二是把选手对一个问题最可能的完成情况呈现在考试结果上。

现实的限制

然而，实现这两个宗旨会遇到很多现实的限制。第一点是比赛形式的限制。OI 的评测方式是黑盒评测，因此有些知识并非不重要，但无法在黑盒评测的模式中直接考察。而且黑盒评测的结果也无法全面地显示出选手对一个问题的思考状况。他究竟是想出来了代码写错了，还是没想出来，还是差一点想出来了，这些都不可能体现在最终得分里面。比赛形式我们很难改变，我们只求在这个比赛形式的限制内最大化题目的效果。

第二点限制，通俗地说就是所谓的“考场 debuff”。比赛不是研究，是在有限时间内，高压状态下完成题目。选手不是做题机器，而是人。因此，很多绝对水平之外的原因都会影响发挥，影响我们出题的第二点宗旨的实现。选手对拍查错需要耗费宝贵的时间，攻一道难题需要冒着巨大的风险。选手对自己得分的预判会影响他的决策，选手做前面的题的情况会影响做后面的题的状态。也许我们不能完全消除“考场 debuff”，但是在我们这一方，可以避免因题目设计、比赛安排的原因（例如难度排序不当，题意出现歧义等）而造成的“考场 debuff”。

第三点限制是社会因素的限制。比如说出题需要考虑某个知识的普及情况和选手的熟悉程度，确保不同区域的 OI 竞赛的均衡发展。我猜测这或许是 CCF 设立大纲的初衷。这类的限制虽然没有中考高考这种考试那么大，但也不能完全忽略。

我们与选手的联系

出题人曾经也是选手。有的选手在 OI 的某一方面的知识上钻研得很深，甚至发展出了新的工具，有的选手在现役时就有了丰富的出题、授课等经验。他们在自己的 OI 生涯中形成了自己对知识体系的理解，对题目的审美，和对未来 OI 的愿景。成为出题人，对我们来说，是将在役时未能实现的想法实现，将自己的理解融入于题目，让现实的 OI 与心目中理想的 OI 靠近。所以说，每一年 OI 试题的变化，多少与前两年 OI 界出现的新的想法，新的工具有关系。所以说，成为出题人并不意味着脱离选手，而是选手身份的延伸。我们不能因为自己出的比赛自己不会打就随意地出题。我们应该想着自己做这套比赛会是什么感觉，自己会不会觉得它是好的卷子。

当然，我们现役时的 OI 也许和退役时的 OI 迥然不同，我们心目中的理想比赛也许并不是我们所面向的选手的理想比赛。所以，我们仍然需要保持同选手的血肉联系。我们需要倾听选手们对某一场比赛、某一道题目的看法，甚至了解当今 OI 的发展动向，并依此指导自己的工作。

最后，我们也渴望被了解。了解怎么出题的选手、了解出题机制的选手，更能够对我们的工作提出针对性的意见。他也不至于一遇到认为不好的题目就把怨气撒到“ccf”这个抽象的法人上，而是给出有价值的反馈。

我们能够怎么做

最基础的注意事项是保证题面是严谨的，数据和样例是正确的。样例出错，数据出错应该属于最严重的命题事故了。出题人自己或者验题人会反复检查题面，并对数据和样例写 validator 来保证这一点。至少我会尽量多地提供大样例，而且样例的生成方法和评测数据是一致的，以避免因代码写错而失分的现象。

个人认为，想 idea，设计题意等工作，需要把某个题一个或几个关键点凸显出来，不必节外生枝。我们尽量不要人为地为了把一道题变难而增加条件，增加细节，增加码量等。我们要明确考察的核心是什么，这个核心是你自己做一道题最有收获的地方，是你自己在做完之后会印象深刻，会铭记在心的东西。我们不希望自己明明基本想出来了这题怎么做，却倒在人为设置的障碍上，因此也不应该人为地设计这样的障碍。

当然，实践中出现的情况会更复杂。有的问题本身容易被人想到，也很重要，但解决它的方法比较繁琐、有不少细节（这在数学领域的论文中也不少见）。这可能需要在比赛层面上斟酌，比如说放了这道题之后就不再放有很多细节的题目。有的问题的确需要对它进行改造才能起到出题人的考察效果。比如说，IOI 2022 D1T3 一题，我们考虑它单组询问不带数据结构的版本，发现它存在着两种复杂度均为线性的算法。然而，只有其中的一种需要推出更彻底的结论，因此更容易推广到带数据结构的区间多组询问的版本。这时候将它出成带数据结构的版本是合理的。但如果一个问题在链上和在树上、在仙人掌上做没有本质差别，推广到树上、仙人掌上的思维难度不高于这个问题本身的思维难度，此时我们一般不必把它出在树上、仙人掌上。

设计出题意之后的拟定部分分，造数据等工作，核心是“预判”。我们需要把自己带入不同类型的选手的身份，穷尽他们所有可能的思考路径，他们可能想到的算法，他们实现此题可能的码量和时间，以及他们在做这题的时候会有什么感觉，遇到什么困难。我们可以以这些对选手的预判为参照，来设计部分分，生成数据，让分数真实地显示选手的完成情况。我们尽量通过精心的设计避免差一点思考出正解的选手拿到和暴力一样的分数，也避免”乱搞“算法拿到过高的分数。为了评定一道题的难度并把它放在合适的比赛，合适的位置，我们也不得不预判出一道题可能的得分分布，可能耗费选手的时间等等因素。

然而，无数个选手做一道题，他们的做题历程必定是多样的。他们可能会走一条和出题人不一样的思考路径，可能会写出接近正解方向的乱搞，也可能写出正解但没有考虑一些细节。尽管这些复杂情况很难一一考虑，我们还是要考虑一切能考虑的，保证一道题、一道比赛的评分机制对大部分人来说是合理的。

总结

总之，我们不帮助选手做题，但是我们为选手提供精致、优美的问题作为他们思考研究的材料，作为 OI 发展的养分。我们也尽量减少水平之外的因素对选手的影响，让他能舒适、安心地思考问题、实现算法。如果说教练的一大任务是为选手创造更好的训练环境，那我们其实也是在为 OI 创造更好的比赛环境。

出题的号召

我非常鼓励选手们在役时尝试出题工作。一方面，你要出出来一道题，往往要尝试很多种模型的组合，提出别人没有提过的问题。你不得不把你自己诠释一个知识点或模型的角度，运用到新的问题上。这其实是非常高层次的训练。

另一方面，每个人初次出题时难免会犯错，会出锅，甚至会被人骂。但只要不是正式比赛，这都不要紧。踩坑、被骂反而增长自己的经验，让”什么题是好题“，“应该怎样出出好题”的答案在实践中愈加清晰。我们真正理解出题，也是在一次次被骂”毒瘤“之后的。但是在正式比赛中，出题的小失误，落在每一个不幸的选手身上，就可能是 OI 生涯的终结、人生命运的改变，任何人都难以挽回它带来的后果。所以，我们希望选手成为出题人之前就已经积累了相当的出题经验，对出题有了充分而成熟的理解，以免在正式比赛中再犯错。

出题这份工作和别的工作性质不一样，它更接近于一种艺术创作，依赖于飘忽不定的灵感。因此，几乎所有出题人很难保证他在任何时候都能产出质量较高的赛题，更遑论他需要面对大学繁重的学业压力。在近几年，出题压力巨大，题目供不应求的情况是时有发生的。例如 CTS 2019 时出题组只征到了 5 道题，CTS 2023 时我们也只得从 8 道题中选 6 道。例如 2022 年疫情导致很多省退出联合省选，AHOI、LNOI 和 ZJOI 等出题组不得不短时间内把一套比赛出出来。所以，单从 OI 竞赛运转的角度来说，我们也希望有更多人在退役后投入到出题工作中，增加人手，缓解压力，避免命题危机。