小A的位运算【牛客tracker 每日一题】

小A的位运算时间限制1秒 空间限制256M知识点枚举网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述位运算是一个非常重要的东西。而小A AA最近在学习位运算小A AA看到了一道很简单的例题是说从N NN个数里面选出N − 1 N-1N−1个数要让它们或起来的值最大小A AA想知道这个答案是多少。你可以帮帮他吗输入描述第一行一个整数N NN表示有N NN个数接下来一行N NN个数表示A 1 , A 2 . . . A N A_1,A_2...A_NA1​,A2​...AN​输出描述一行输出个结果代表最大值一行输出个结果代表最大值示例1输入5 1 2 4 8 16输出30说明选择2 , 4 , 8 , 16 2,4,8,162,4,8,16或的和是最大的没有比这个更大的方案。备注1 ≤ N ≤ 5 e 6 1 ≤ A i ≤ l o n g l o n g 1≤N≤5e61≤A_i≤longlong1≤N≤5e61≤Ai​≤longlong解题思路本题是位运算性质 鸽巢原理优化的经典思维题利用二进制位数有限的特性将百万级数据规模的问题降为常数级运算。核心性质推导或运算满足单调性对于任意二进制位只要剩余数中至少有一个数该位为1最终或结果该位就为1。我们的目标是去掉一个数使得剩余数的或值最大。若某数的所有为1的二进制位都能在其他数中找到则去掉该数不会影响总或值此时结果等于所有数的总或。若某数拥有至少一个“独有位”其他数该位均为0去掉它会导致该位丢失或值减小。鸽巢原理优化long long仅有 64 个二进制位因此最多只能有 64 个数各自拥有至少一个独有位不可被替代。根据鸽巢原理当N 64 N 64N64时必然存在至少一个没有独有位的数去掉它不会改变总或值因此答案就是所有数的按位或总和。当N ≤ 64 N \le 64N≤64时数据规模极小直接暴力枚举去掉每个数计算剩余数的或值取最大值即可。算法复杂度N 64 N 64N64时仅需一次遍历求总或时间复杂度O ( N ) O(N)O(N)可轻松处理 500 万级数据。N ≤ 64 N \le 64N≤64时暴力枚举的总运算量为64 2 4096 64^2 40966424096常数级开销。总结核心逻辑利用二进制位数有限的特性通过鸽巢原理判断是否存在可无损移除的数大规模数据直接返回总或小规模数据暴力枚举验证。关键操作或运算单调性分析、鸽巢原理降维、分情况处理不同数据规模。效率保障百万级数据仅需一次线性遍历无嵌套循环运行效率极高。代码简要说明分支判断根据n nn是否大于 64 分为两种处理逻辑适配不同数据规模。大规模处理n 64 n64n64时逐个读入数字并累加到总或变量mx中遍历完成后直接输出总或。小规模处理n ≤ 64 n\le64n≤64时先将所有数存入数组再双重循环枚举去掉第i ii个数计算剩余所有数的或值同步更新全局最大值。类型适配使用long long存储数值匹配题目中long long范围的数据要求避免溢出。输入优化关闭流同步并解绑 tie大幅提升百万级数据的读取速度。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll mx0;ll n;cinn;if(n64){for(ll i0;in;i){ll x;cinx;mx|x;}coutmxendl;}else{vectorllv(n);for(ll i0;in;i)cinv[i];for(ll i0;in;i){ll res0;for(ll j0;jn;j){if(i!j)res|v[j];}if(resmx)mxres;}coutmxendl;}return0;}