【其他】noip 互测 Round 3 组题过程 — Iris

记录一下出题的过程。

关于 t1：

这是最早就定好的，在萱有次模拟赛看错题的时候就觉得可以作为一个简单题放上去。

开始觉得还行，在某一个周末突然意识到是个笛卡尔树板子，但是似乎更好地对标 noip t1 了，所以没关系。

造数据的时候重造了好几次，不小心全造成大数据了，不小心 srand() 有问题……

卡了一个已知理论 $O(n^2)$ 的暴力，来自 hyf 暴力过原题的代码，因为只打算造一份这样的数据，所以开了子任务依赖。

在最后抓万来实现笛卡尔树的做法时，发现随机数据比之前的做法快很多，于是又重新确定了时限。

然后发现初版 std 带 $\log$，因为用了 sort，于是又重新确定了时限。

关于 t2：

属于是毙了两个题。

第一次，题目卒于题面比较诈骗，结论感觉有点离谱。

第二次，本来是放萱的题，但是还没来得及造，万造了一个 t3，他造完后，萱意识到 t2，t3 类型有点相似，这好像不太好。因为大家都不想验萱那个题，就把 t3 换到了 t2。把那个题丢一边去了。

然后就被抓去想 t2，大概是发现 11 可以随便动，于是就有了一段 1 的部分分。

仿照今年 csp 出了全 ? 的档，本来说要不要拿 BM 看下能不能推，后来 OEIS 到了就觉得也差不多行？

最后萱不想了，然后觉得 t2 结论比 t3 神秘，不过在 OI 里也不算难的，感觉和那种两个人相遇会掉头的可以看成直接往前走差不多（）

关于 t3：

属于是毙了两个题。

第一次，题目卒于一维比较简单，拓展到二维出问题了。

第二次，题目卒于关键结论是大家非常熟悉的，担心太简单了。

万将一个 div B 加了 $4$ 个 $0$，并且改成带修出出来成了 t3。

然后萱就被抓去想 t3，萱只会 $O(qn^2)$，然后萱继续想。萱把奇数偶数抽象成 $01$ 想了一下放数的过程，萱悟了。

萱会贪心了，于是可以 $O(qn)$ 了。意思是萱不打算验要上数据结构的那一档。

萱开始写题面，萱开始写数据生成器，萱开始改 std 的输入输出格式，萱开始写 chk，拍不上！！！

萱调了一个晚上。萱开始造特殊性质，要保证数据合法真是太不容易了，萱如是说。

本来是 $2s$ 的时限，然而随机数据 std 要 $1\sim2s$ 不等，于是时限成了 $3s$，并且开 O2。然后 chk 跑过了 subtask5，于是每个子任务时限就不一样了。

萱开始造 hack 数据，随机只能造小的，萱已经自闭不想手捏数据了，想了想好像会一个一个 subtask 写的人好像不多，就不造大的 hack 数据了，然后开了子任务依赖。

关于 t4：

属于是毙了两个题。

第一次，是州州突然 Q 万说有 idea，然而题目卒于不到 t4 难度。

第二次，题目卒于万觉得自己毛估估差不多会正解，可能也简单了。

从并不神秘的地方找了一个交互题。

然后萱被抓去想 $t4$，万说自己会 $n^2$，萱开始嘤嘤嘤，说自己连 $2^n$ 也不会。然后萱继续想。

萱发现查一个数查了个寂寞，查两个可以判断奇偶性，查三个？？

萱回想了省队集训，似乎还有一种查法是对着一个很大的集合查，于是萱突然悟了，自己似乎可以找到 $n$。

差不多就可以写 $n^2$ 了，萱写了一份 $O(\frac{n^2}{4}+\frac{n}{2})$ 的代码，然后万惊讶地发现自己下界卡的是 $O(\frac{n^2}{2})$，这告诉我们交互题绝对不可以毛估估下界。

然后萱又剪了个枝，于是重造数据再卡了一波下界。然后 $p_1=1$ 的部分分就无了。

关于其他：

• 因为萱不擅长造题，所以承担了大部分的文字工作。
• 虽然萱觉得 t2 结论比 t3 神秘一点，但是大概 t3 总体难一点，所以这样组题了，希望不要无意模拟今年 CSP 难度。
• 虽然这是个互测但是萱好像被每题都测了。
• std 都是万写的。
• 为了使题目导出的时间正确，调整了系统时间。