2021.5.21 模拟赛游记

其实又是未遵循标准程序造成的严重事故征候。

吸取了上次的经验,开始记录较为详细的 CVR 数据了,用来 热烈庆祝 加速调查。

先放上 CVR 数据:

比赛开始于 0110Z

共产生三份备份,备份最终修改时间 0218Z 0239Z 和 0318Z。
未进行回滚。

A:
// 0130Z - coding completed
// 0137Z - before submit checklist completed

B:
// 0210Z - coding compeleted
// 0211Z - error occured ! 
// 0225Z - extra tests begin
// 0235Z - error occured !
// 0310Z - skip procedues
// 0328Z - debug again
// 0343Z - before submit checklist compeleted

C:
未执行检查单。

A

看题之后先瞎想了一会儿,然后模拟了一下暴力思路,很快发现了重复,写出了正解。

由 CVR 数据可知在比赛开始之后二十分钟写完了,然后没经过什么调试并在七分钟后完成了提交前检查单。对于模拟赛第一题来说这个速度可能略微有一点慢,但从总体看对这场比赛的影响不大。

B1

明明是数位 dp 的模板,但事情有一点儿不太对劲了。

从 CVR 看,B 题完成第一份代码一共使用了超过半小时,对于一个不是很复杂的模板这个用时显然有一点高了。

随后开始执行提交前检查单,很快发现了错误,即输入数据无法使用整型进行存储,然后开始修正,最终在十多分钟后通过了样例。由于独立完成的数位 dp 不多,所以有点不放心,而且人工难以完成检查单所要求的 tests, 所以开始对拍。

然后直接就拍出了错误……接着就是一堆的调试了。

甚至写完之后一个小时了都没有调处来,因为这题总用时已经达到一小时三十分,严重超出了最开始的计划,所以执行跳题程序,先去 C 了。

C

看了题觉得是有什么结论的,但是由于前一题的原因,直接就写了个模拟,时间上可能是可以过的,但是没空考虑证明了,所以这大概是一个谭变。

既然没有给出啥证明,就觉得 速度大点没事,检查单啥的不管了。

B2

调了一会儿总算是调出来了。一个很傻的小问题。

比赛开始之后两小时三十二分完成了检查单。

然后……

然后呢!这个时候明明已经完成了,为什么不去做最后一题的检查单?!

最后因为 (返回值不为 00

if(b == 0) return printf("%lld\n", ans);

而 RE 了,失去了 AK 的机会。

还是得讲一下最后一题的:

两个数,每次可以把大的一个减去小的并把小的一个翻倍,问多少次之后一个为 00

反过来考虑这个问题,若最后有解,那么一次次的分裂之中不可能超过 O(log2n)O(\log_2 n) 级别次,所以复杂度是对的。

事实上还有一种更简单的做法:因为永远是把一个减掉,所以分的最小的块就是两个的最大公约数了,除掉这个公约数答案不会发生变化。而由前面的分裂理论得到,把两个数的和除掉公约数然后取个 log2\log_2 就可以了。

结论和建议

这次严重事故征候的原因主要在于对于简单问题过于放松,未完整执行检查单。

所以建议在任何情况下都应遵循标准操作程序并严格执行检查单。同时,对 IO 的检查中也应该加入对输出后退出的检查, tests 检查中应确认程序返回值。

对于一些合并的证明可以反向思考。