小A的位运算-(前缀和+位运算)

时间:2021-05-14 06:13:23

https://ac.nowcoder.com/acm/contest/549/D

题意:从N个数里面选出N-1个数要让它们或起来的值最大。

解题:

假设n个数分别存在a数组里。

从左到右连续或运算结果存在leftt数组里。

从右往左连续或运算结果存在rightt数组里。

对于(n-1)个数的或运算结果,每次抽去中间一个数,该数的左边连续或的结果 或 该数右边连续或的结果,动态求最大值。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<math.h>
#include<string>
#include<queue>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std; int a[];
int leftt[];
int rightt[];
int n; int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
leftt[i]=leftt[i-] | a[i];
}
for(int i=n;i>=;i--)
rightt[i]=rightt[i+] | a[i]; int maxx=-;
for(int i=;i<=n;i++)
maxx=max(maxx,leftt[i-] | rightt[i+] );
printf("%d\n",maxx);
}
return ;
}