时间戳

首页 > 解决方案 > 使用 And/Or 运算符最大化按位函数

arrays - 使用 And/Or 运算符最大化按位函数

问题描述

给定一个包含 N 个整数的数组 A。此外，我们得到另一个整数 K。对于任何 1<=L<=R<=N（假设 1 个基索引），在此数组上定义的函数很少：

And(L,R) : A[L] AND A[L+1] ... AND A[R] (AND is Bitwise And operation)
Or(L,R)  : A[L] OR A[L+1] ... A[R]      (OR is Bitwise Or operation)
Sum(L,R) : A[L] + A[L+1] ...  A[R]

我们还要给出另一个函数 F(L,R)，其

  1. 如果 And(L,R) < K，则输出为0
  2. 否则它的输出是Or(L,R) + Sum(L,R) if And(L,R)>=K

现在我们要找到这个新函数的最大值 F(L,R)。此外，由于输出可能非常大，因此需要计算模 1000000007

示例：给定一个包含 4 个元素 A = [1,4,5,4] 且 K=2 的数组。答案是 18

解释: F(L,R) 的最大值是 F(2,4)

And(2,4)  = 4 AND 5 AND 4 => 4 (And 4 is greater than K, i.e 2)
Or(2,4)   = 4 OR 5 OR 4 => 5
Sum(2,4)  = 4 + 5 + 4 => 13
F(2,4)  = 5 + 13 => 18

为每对 L 和 R 计算 F 函数是我现在能够想到的解决这个问题的唯一方法。但是 N 可以增长到 100000。所以每对都不是最好的方法。有什么建议可以在 O(N) 或 O(N*LogN) 复杂度中解决这个问题？

标签： arraysalgorithmbit-manipulationdynamic-programming

解决方案

推荐阅读