牛客小白月赛13 D题(位运算)

发表于
字数统计: 1k字 | 阅读时长 ≈ 4分钟

题目：[链接]

题目描述：

位运算是一个非常重要的东西。而小A最近在学习位运算，小A看到了一道很简单的例题，是说从N个数里面选出N-1个数要让它们或起来的值最大，小A想知道这个答案是多少。你可以帮帮他吗？

输入描述：

1
第一行一个整数N表示有N个数接下来一行N个数表示A1,A2...AN第一行一个整数N表示有N个数接下来一行N个数表示A1,A2...AN

输出描述：

1
一行输出个结果代表最大值一行输出个结果代表最大值

输入：

1
2
5
1 2 4 8 16

输出：

1
30

说明：

1
2
3
选择2,4,8,16或的和是最大的，没有比这个更大的方案。

1≤N≤5e6，1≤Ai≤longlong

第一次看到题，直接上去sort排序，从第二个开始或运算和(贼尴尬啊)，肯定秒WA啊，原来没想象的那么水哇，这题恶心就恶心到n个数就让你或运算n-1个(或运算n个就多好)，后来通过大神室友的指点，略懂一二，我试着解释解释吧，或运算 1|1=1，1|0=1,0|0=0，此题就是每个数值位1，0之间的或运算(最下面有后续)

此题思路就是，将每数位1的个数记录下来

比如 n个数每个位上的1的总个数为

4 2 5 1 3 1

对a[i]进行遍历，

例如a[0]=5转化为二进制

0 0 0 1 0 1

对应位上减掉1的个数

则变成

4 2 5 0 3 0

则此时最大值即是

1 1 1 0 1 0 (即是各位置剩余1的个数>=1 即对应的值为1)此时的十进制为2^5+2^4+2^3+2^1 将此时的最大值保存下来

然后继续对a[i]重复进行上面的操作，每次保存下来最大值

遍历结束

AC代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
typedef long long ll;
const int mod=1e9+7;
using namespace std;
ll a[500003];
int bits[64],c[64];
int main() 
{
	int n;
	ll maxx=0;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%lld",&a[i]);
		for(int j=0;j<64;j++)//题上范围long long 最大2^63-1，所以定义64，也可以先求出a[i]的最大值，来获得最高位
			if(a[i]>>j&1)
				bits[j]++;
	}
	for(int i=0;i<n;i++)
	{
		memset(c,0,sizeof(c));//c数组用来存放当前最大或值
		for(int j=0;j<64;j++)
		{
			if(a[i]>>j&1)
			{
				if(bits[j]-1>=1) 
					c[j]=1;	
			}	
			else
			{
				if(bits[j]>=1) 	
					c[j]=1;	
			}
				
		}
		ll sum=0;
		for(int x=0;x<64;x++)
			sum+=c[x]*pow(2,x);
		maxx=max(maxx,sum);
	}
	printf("%lld\n",maxx);
	return 0;
}

后续补充：

无意中看到大佬利用前缀和与后缀和求的，思路比这个清晰，简单(还是自己太菜，当时没想到)，下面就简单分享下思路，

先用一个数组保存下所有的或前缀和，再用另一个数组保存所有的或后缀和，然后保存前缀和与后缀和或的最大值即可 ，

pre[i] | suf[i+2]，具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
typedef long long ll;
const int mod=1e9+7;
using namespace std;
ll a[500003];
ll pre[500003],suf[500003];
int main() 
{
	int n;
	ll maxx=0;
	scanf("%d",&n);
	memset(pre,0,sizeof(pre));
	memset(suf,0,sizeof(suf));
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		pre[i]=pre[i-1]|a[i];//求或的前缀和
	}
	for(int i=n;i>=1;i--)
		suf[i]=suf[i+1]|a[i];//求或的后缀和
	maxx=suf[2];//先把第一个元素不取的或的和赋值给maxx
	for(int i=1;i<=n-2;i++)
		maxx=max(maxx,pre[i]|suf[i+2]);
    //由题意知取n-1个元素，所以每次取前缀和然后隔一个元素的后缀和的或值，然后最大值保存在maxx中
	maxx=max(maxx,pre[n-1]);//pre[n-1]即是最后一个元素不取的或值
	printf("%lld\n",maxx);
	return 0;
}
hey!baby,站住，点它!