P2609

jijidawang · 2022-06-28 11:41:39 · 题解

如何秒掉 ZJOI（详细揭秘）

首先因为需要高精所以选择 Python .

根本不用管题目里说的东西，直接暴力模拟：

def f(n):
    if n < 2:
        return n
    ans = f(n // 2)
    if n % 2:
        ans = ans + f(n // 2 + 1)
    return ans 

然而这样递归复杂度是有问题的，然而我们知道 Python 里有个东西叫做 LRUCache .

简单介绍一下 LRU Cache 大概就是对要记忆化的东的 Hash 开一个双向链表，然后查询一个东西就把它提到链表头，如果加东西空间不够了就丢掉链表尾 .

此处这个链表尾其实就是 LRU 元素（Least Recently Used，最近最少使用），我们根据实际经验看这个元素的应用次数是比较少的于是丢掉会更优 .

当然如果这个空间很足的话就等价于记忆化搜索

用法见代码：

import functools

@functools.lru_cache(114514)
def f(n):
    if n < 2:
        return n
    ans = f(n // 2)
    if n % 2:
        ans = ans + f(n // 2 + 1)
    return ans 

T = int(input()) 

for i in range(0, T):
    n = int(input())
    print(f(n))

@functools.lru_cache(114514) 表示 f 需要 LRU Cache 帮忙记忆化，大小是 114514 .

当然这题比较水，大小直接拉满（即 @functools.lru_cache()）也能过 .

习题：P1464 Function，需要手动设置 LRU Cache 大小 .

当然 CCF 是不把 Python 当作竞赛语言的