记录一下出题的过程。

关于 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 都是万写的。
  • 为了使题目导出的时间正确,调整了系统时间。
分类: 文章

1 条评论

000226wrp · 2021年11月9日 9:26 下午

/se

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

*

code