Сумма побитового ИЛИ всех возможных подмассивов данного массива - PullRequest
Новая
       28

Сумма побитового ИЛИ всех возможных подмассивов данного массива

0 голосов
/ 15 сентября 2018

Я хочу найти сумму побитового ИЛИ всех возможных подмассивов данного массива.

Это то, что я делал до сих пор: 

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)

Но это довольно медленно.Как я могу оптимизировать это?

Ответы [ 2 ]

0 голосов
/ 02 октября 2018

Давайте сначала найдем сумму побитового ИЛИ подмассивов, заканчивающихся в позиции i .Пусть OR для всех элементов массива от 1 до i равно или , а i-й элемент равен a [i] , биты которого не установлены в a [i], но установленные в или исходят из некоторых предыдущих элементов, давайте рассмотрим пример здесь,
1 2 2
в позиции 3 или = 3, a [i] = 2,или ^ a [i] = 1, это означает, что 1 исходит из некоторого предыдущего элемента, если мы удалим 1 ИЛИ некоторого подмассива, заканчивающегося в i, будет уменьшено.последняя позиция, в которой установлен бит 0, 1 .Таким образом, ответ будет

ans = или * i

для всех битов от 0 до m,
ans - = (i - lastposition [бит]) * (1 << бит); </strong> // lastposition [] дает последний индекс, в котором бит включен.
Почему последняя позиция?Так как индексы перед последним положением [], где этот бит включен, не окажут никакого влияния, так как ИЛИ будет равнозначным из-за присутствия этого бита в последнем положении [].

Окончательный ответ можно узнать суммированиемна все ответы 1 <= i <= n. </p> 

#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';
}
0 голосов
/ 15 сентября 2018

Поскольку этот вопрос из конкурса, я до сих пор не ответил.

Код: 

#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 (массив)

for, 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 означает, что Y-й бит в числе X взят для операции ИЛИ.

Для,

2 = 2,1

2,3 = 2,1 и 3,0 [Так как 1.0 не будетдоступно]

{продолжается ..}

Так что, если вы внимательно наблюдаете, хотя версия 3.0 доступна, она не используется, когда присутствует 1.

Если необходимо использовать бит, тот же бит предыдущих чисел должен быть 0. [Запомните это, мы будем использовать его позже]

Мы создадим 1 массив с именем нули,который дает счет последнего установленного бита предыдущих чисел в каждой позиции соответственно [это предложение может ввести вас в заблуждение, попробуйте прочитать больше, вы можете получить ясность].

Для данного массива,

В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 числа не имеют установленного бита в позиции 2 ^ 2, 1 число не имеет установленного бита в 2 ^ 0.

Теперь нам просто нужно умножить в зависимости от их установленных бит.

Если бит установлен, то мыдобавить (нули [i] +1) (2 ^ i) (ni).

...