假设由N(N
我想到了将大集合{1,2,....,10}中每个数字可除的值的数量存储在N个元素的10个数组中,并进行累加总和以得到任何特定数字可除的值的数量在O(1)时间的任何范围内,例如,如果需要获取至少下列数之一可整除的值的数量:2、3、5,则我将被每个值整除的值的数量相加,然后删除交集,但是我没有正确地计算出每次没有2 ^ 10或2 ^ 9计算的交集,这也会非常慢(并且可能会消耗大量内存),因为它可能会完成100000次,任何想法?

最佳答案

你的想法是正确的。您可以使用包含-排除原理和前缀和来找到答案。您只需要再进行一次观察即可。

如果集合中有一对数字ab,使得a除以b,我们可以删除b而无需更改查询的答案(实际上,如果是b | x,则为a | x)。因此,我们总是得到一个集合,使得没有元素可以划分任何其他元素。

此类掩码的数量小于2^10。实际上,它是102。这是计算它的代码:

def good(mask):
    for i in filter(lambda b: mask & (1 << (b - 1)), range(1, 11)):
        if (any(i % j == 0 for j in filter(lambda b: mask & (1 << (b - 1)), range(1, i)))):
            return False
    return True

print(list(filter(good, range(1, 2 ** 10)))))

因此,我们的预处理大约需要100N操作和数字来存储(它看上去很小)。

此外,任何“良好”掩码中都有大多数5元素(可以使用上面的代码进行检查)。因此,我们可以使用2^5运算来回答每个查询。

关于c++ - 在给定范围内找到路口?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/41774967/

10-08 22:03
查看更多