题目:[链接]
题目描述:
位运算是一个非常重要的东西。而小A最近在学习位运算,小A看到了一道很简单的例题,是说从N个数里面选出N-1个数要让它们或起来的值最大,小A想知道这个答案是多少。你可以帮帮他吗?
输入描述:
1
| 第一行一个整数N表示有N个数接下来一行N个数表示A1,A2...AN第一行一个整数N表示有N个数接下来一行N个数表示A1,A2...AN
|
输出描述:
1
| 一行输出个结果代表最大值一行输出个结果代表最大值
|
输入:
输出:
说明:
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++) if(a[i]>>j&1) bits[j]++; } for(int i=0;i<n;i++) { memset(c,0,sizeof(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]; for(int i=1;i<=n-2;i++) maxx=max(maxx,pre[i]|suf[i+2]); maxx=max(maxx,pre[n-1]); printf("%lld\n",maxx); return 0; }
|