0

我想找到给定数组的所有可能子数组的按位或的总和。

这是我到目前为止所做的：

from operator import ior
from functools import reduce
n = int(input())
a = list(map(int, input().split()))
total = 0
for i in range(1,n+1):
    for j in range(n+1-i):
        total += reduce(ior, a[j:j+i])
print(total)

但这很慢。我该如何优化它？

4

2 回答 2

0

由于这个问题来自竞争，我到现在还没有回答。

代码：

#include <bits/stdc++.h>
using namespace std;
#define size 32
#define INT_SIZE 32
typedef long long int Int; 
typedef unsigned long long int Unt;
// Driver code
int main()
{
    Int n;
    cin>>n;
    Int arr[n];
    for(int i=0;i<n;i++)
        cin>>arr[i];
    int zeros[size];
    for(int i=0;i<size;i++)
        zeros[i]=1;
    unsigned long long int sum=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<size;j++)
        {
            if(!(arr[i] & 1))
                zeros[j]++;
            else
            {
                sum+=(Unt)((Unt)zeros[j]*(Unt)(1<<j)*(Unt)(n-i));
                zeros[j]=1;
            }
            arr[i]>>=1;
        }
    }
    cout<<sum;
    return 0;
}

逻辑：

注*：这是我的思考过程，这可能不是很容易理解。如果我不能让你理解，请道歉。

举个例子：5（数组大小）1 2 3 4 5（数组）

因为，1 = 1.0

1,2 = 1.0 & 2.1

1,2,3 = 1.0 & 2.1 [3.0 & 3.1 不会有用，因为它们已经被 1 & 2 占用]

1,2,3,4 = 1.0 & 2.1 & 4.2

1,2,3,4,5 = 1.0 & 2.1 & 4.2 很有用。

在上面的解释中，XY 表示数字 X 中的第 Y 位用于 OR 操作。

为了，

2 = 2.1

2,3 = 2.1 & 3.0 [因为 1.0 将不可用]

{继续..}

因此，如果您仔细观察，尽管 3.0 可用，但在 1 存在时它并没有被使用。

如果需要使用某个位，则之前的数字的相同位应该为0。[记住这一点，我们稍后会使用它]

我们将创建 1 个名为 zeros 的数组，它分别给出每个位置上先前数字的最后一组的计数 [这句话可能会让您感到困惑，尝试阅读更多内容，您可能会清楚]。

对于给定的数组，

在 1: 0 0 0

在 2: 1 1 0 {1 的二进制是 001}

在 3: 2 0 1 {2 的二进制是 010}

在 4: 3 0 0 {3 的二进制是 011}

在 5: 0 1 1 {4 的二进制是 100}

结束：0 2 0 {5 的二进制是 101}

我们上面所做的是，如果位设置为位，我们将其设为 0，否则我们添加计数，以便我们可以了解有多少数字没有分别设置位位置，意思是，在 3 之前，2 个数字没有t 在位置 2^2 设置了位，1 个数字没有在 2^0 设置位。

现在，我们只需要根据它们的设置位相乘。

如果它被设置位，那么我们将添加 (zeros[i]+1) (2^i) (ni)。

于 2018-09-15T20:03:55.277 回答
-1

让我们首先找到以位置i结尾的子数组的按位或的总和。令从 1 到 i 的所有数组元素的 OR 为or并且第 i 个元素为a[i]，未在a[i]中设置但设置在or来自某些先前元素的位，我们举个例子这里， 位置 3 处的
1 2 2
，或 = 3，a[i] = 2，或^a[i] = 1 这意味着如果我们删除 1，则 1 来自某个先​​前的元素，或者某个以 i 结尾的子数组的 OR 将是减少。位 0 打开的最后一个位置是1。所以答案是，

ans = or*i

对于从 0 到 m 的所有位，
ans -= (i - lastposition[bit])*(1 << bit); //lastposition[] 给出位打开的最后一个索引。
为什么是最后一个位置？因为该位打开的 lastposition[] 之前的索引将不会产生影响，因为由于 lastposition[] 处存在该位，OR 将保持相同。

最终答案可以通过总结 1 <= i <= n 的所有答案来找到。

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define rep(i,a,b) for(int i = a; i <= b; i++)
using namespace std;
ll r, a, sum, pos[30];
int main()
{
   int n;
   cin >> n;
   rep(i,1,n)
  {
      cin >> a;
      r |= a;
      ll ex = r^a;
      ll ans = i*r;
      rep(bit,0,30)
        if(ex & (1 << bit))
            ans -= ((ll)(i - pos[bit])* ((ll)1 << bit));
     sum += ans;
     rep(bit,0,30)
        if(a & (1 << bit))
            pos[bit] = i;
}
   cout << sum << '\n';
}
于 2018-10-02T06:54:31.253 回答