1 条题解
-
1
本题部分分可用于找规律。
Solution 1
在OEIS中输入任意前几个数,发现这个数列可以在这篇文章中找到:
https://oeis.org/A000695/a000695_1.pdf
翻到Corollary 3,发现它的递归式是
$$T(2^k+i)=\begin{cases} \frac13(2^{2k+1}+1)&\text{if }i=0;\\ T(2^k)+2T(i)+T(i+1)-1&\text{if }i=1,\dots,2^k-1.\\ \end{cases} $$关于递归式的详细推导可参考文章。
照着写即可。注意需要使用记忆化和
unordered_map
。时间复杂度,期望得分100。如果使用
map
期望得分可能是70。
- 1
信息
- ID
- 203
- 时间
- 3000ms
- 内存
- 1024MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 316
- 已通过
- 18
- 上传者