牛客出题（锅）记

作为 Wannafly Round 27 的三位出锅人（czx，zzy，我）之一（先甩锅，我只出了 A，E），在这里讲一下出题的心路历程。

（讲道理 Wannafly 25、26、27 一共有 15 / 18 道题是 xj 出题人的。。。）

事情要从暑假开始。

czx 收到了网友问他的一个问题（大概就是 E 题去掉恰好 $n$ 个数的限制），然后我们俩一起看错题面，看成了现在的题面。原题的构造比现在的题目要松很多，于是 czx 随便给了一个构造水过去了。然后我们就开始考虑新题。

一开始我们并不知道一定在 $k \le \frac{n(n - 1)}{2}$ 时有解，然后我的思考历程和我题解中写的一样，总之是做出来了。然后本来是想投给机房里出 CF 题的，然后他们好像不缺题了（但是也被 CF 管理员咕了。。。）。然后就屯着了。

后来很久之后，czx 突然找到我，说想出一套题，zzy 和他各有一道 hard，然后把我拉上，加上了那道题。

（好像他们当时想出的两道题都被毙了。。。）

然后我顺便把 easy 出了：写个 checker。

又过了很久，czx 说要到了一场比赛（本来是初赛前一天，后来往后咕了一场）。这时候 zzy 又加强了一道题，并决定把它放在 F（就是现在的 F），我的题还是 D，结果 czx 的 E 本来也是个数据结构，然后就有两道数据结构了。。。

然后 zzy 把 C 造了。

然后我花了一个晚上 + 一个下午把两题的 std 和数据给造完了。（其实挺好造的，但讲道理我造得还蛮认真的。。。）

当时的情况是 B C D (E) F 造完了，czx 想改 E。

把题目丢给 walker（coordinator），他被 C 打自闭了，说丢到 D。然后 czx 的 E 自然而然咕掉了。然后把我的 easy 丢 A 了。

然后就变成了 A D(zzy) D(我) F。

然后 czx 造完了道 B 之后突然说丢一道数独题放 C 吧。

我们自己说题目是 A B D D D F。walker 说把 C 换掉吧。

然后 czx 自闭了。幸好他又看错一道 NOIP 模拟题，正好把看错的题意放 C。

然后每道题就确定下来了。

(A - 我，B、C - czx，D - zzy，E - 我，F - zzy)

我和 zzy 很早就把东西准备好了，czx 因为临时造题，开始 rush，B 题是个仙人掌题，数据不好造。C 题他表示懒得写 std，把锅丢给了我。（他以为很长，结果我十几分钟写完拍上）

然后又开始整合三个人的资料。zzy 很早前提议狙击滑稽 zzq（白[数据删除]法师），然后就搞了 {灰，紫，蓝，绿，黄，红}[数据删除]法师（牛客的 rating 颜色），加上白正好七彩[数据删除]法师。

czx 一再确认牛客的题面格式。（做过题的都知道，它那里的排版并不美观，因为它用的不是 markdown + mathjax，而是纯文本 + 图片公式。。。）然后把我认真排版的数学公式一个一个删去（我看他删的时候真的好难受。。。），变成纯文本。

然后是 dls 验题。dls 上来先说这个 F 好神仙呀。。。

然后发现 B 题出锅了。

我们盯了若干遍 std，都没有发现问题。我建议写个 validator，结果不但发现 generator 的锅，而且发现我的 validator 写假了。

验 D 题，dls 操标算，然后发现 zzy 写的在牛客上 T 了。。。

验我的 E 的时候，dls 说直接看 checker，然后看到我在读选手输出的空格时表示并不一定需要（我：我只是想卡掉分 $n$ 行输出的人。。。）

验到 F 的时候，离比赛开始没多少时间了，dls 表示不验了，自闭了。。。（我们在机房里都说 zzy 清华集训要被 dls 狙了）

比赛开始前我们看题面，发现所有的 [数据删除]法师全部变成了魔法师。。。

（为什么我去安利大家做题大家都不敢做呀。。。）

比赛开始，照例机房开始轰炸答疑区，结果 app 真把答疑区轰出 bug 了。。。

2 分钟后，有人交 A，有 AC 有 WA（我 A 题就那么几个 FST 点，开始没多久就都有人踩到了）。然后看到 zzq 过了 A 题，机房一阵欢呼。

5 分钟 zzq 过 B，之后陆续有人过 B，mls 也来打了（是被 dls 拉过来的？），A 题许多人 FST。B 题样例写挂了，修了个小锅。

9 分钟 zzq 过 C，大家惊叹他的手速。

然后一会儿平静，有人交 D 被卡常了。

22 分钟 zzq 过 D，感到好害怕，感觉要被 A 穿。（dreamoon 交 A WA，大家纷纷看他的变量名），大家给我的 E 设了小目标：撑到 45 分钟。

过了很久，E、F 只有人交乱搞。~~有人被 A 打自闭了（多清真的题，怎么就自闭了。。。），~~一片 A 题写假。

45 分钟过去了，少部分人过 D（一些人被卡常），无人过 E，我们暗自庆幸。

（我在看代码的时候，突然发现我们 B 题少判 $n = 1$ 的情况，幸好我答疑的时候回复的是 $n \ge 2$）

1h20min，突然有人 E 过了（标算），一分钟后 zzq 过 E（类似标算的东西）。调查了一下，一血是隔壁的某人，但他不愿透露细节。。。

接下来一小时又有几个人过 E（感觉难度挺靠谱的），D 题许多人卡常成功。有人被 C 卡住了。

czx 去隔壁提示了一下 E 题，然后大家都过了。。。

（讲道理 lsk 验的时候花了半小时左右就得到了标算。。。）

czx 说 dreamoon 构造题很强，事实上也如此。

最后无人过 F。

然而，还是出锅了。

（本来 czx C 题数据也是全随的，在我的怂恿下加了链和菊花，还真把人给卡了。。。）

另外，zzq 对 F 题的评价

以下为 E 题题解。

首先显然的一点，当 $k > \frac{n(n - 1)}{2}$ 时无解。

而当 $k \le \frac{n(n - 1)}{2}$ 时，均存在解。

我们可以首先考虑 $k = \frac{n(n - 1)}{2} - 1$ 时的做法。此时只有一对数之和不是完全平方数。

假设存在 $a, b$，满足 $a + a$, $a + b$ 均为完全平方数，而 $b + b$ 不是完全平方数（$a = 2, b = 7$ 就是一组解）。那么我们可以发现一个有 $n - 2$ 个 $a$ 和 $2$ 个 $b$ 的序列为合法序列。

对于原题，采用类似的思路，我们首先可以找到最小的 $m > 0$，满足 $\frac{m(m - 1)}{2} \ge k$。显然 $m \le n$。我们可以解决长度为 $m$ 的问题，然后在最后添加上 $n - m$ 个不会影响答案的数。

此时我们需要有 $\frac{m(m - 1)}{2} - k$ 对数之和不是完全平方数。

我们可以找到 $a, b, c$ 满足 $a + a$, $b + b$, $a + b$, $a + c$ 为完全平方数，而 $b + c$ 不是。则我们只需要放 $1$ 个 $c$，$\frac{m(m - 1)}{2} - k$ 个 $b$，$m - (\frac{m(m - 1)}{2} - k) - 1$ 个 $a$ 即可。

接下来我们只需要证明 $\frac{m(m - 1)}{2} - k < m$：

由 $m$ 定义得 $\frac{(m - 1)(m - 2)}{2} \le k$。

所以 $\frac{m(m - 1)}{2} - k \le \frac{m(m - 1)}{2} - \frac{(m - 1)(m - 2)}{2} = \frac{(m - 1)(m - (m - 2))}{2} = m - 1 < m$。

$a, b, c$ 可以通过本机暴力寻找，$a = 2, b = 98, c = 7$ 就是一组解。

感觉出题还是很爽的，特别是实现了期望得到的效果的时候（但我也没想到 A 题这么多人 FST）。

吸金最开心