338 Counting Bits

不想解释

 

my solution (没脸说...)

这样的东西必定有规律, 找出来就好了

规律如下, 每次的增加都是上次的一半的递归 (我不知道怎么解释这种规律, 感觉语言很苍白...)

仔细观察一下就发现了

我本来以为我的解法很不错, 计算次数很少, 几乎没有, 大部分的运算都是 append, 应该会很快, 然而...

那个几十毫秒的不是我的, 800/900 的才是 = =

 

best solution

他是通过计算出来的, 比我好在于, 他不会计算多余的, 然后需要裁剪

(BTW 这个算法与我原算法的速度相差无几, 但是等价的 C++ 代码却只需要几十毫秒)

(加上 tie 和 sync_with_stdio, 可能速度能更快, 我不禁陷入了沉思...)