1 条题解

  • 1
    @ 2023-10-17 21:19:50

    本题部分分可用于找规律。

    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

    时间复杂度O(有点难算)O(有点难算),期望得分100。如果使用map期望得分可能是70。

    • 1

    信息

    ID
    203
    时间
    3000ms
    内存
    1024MiB
    难度
    9
    标签
    (无)
    递交数
    316
    已通过
    18
    上传者