补充题意解读 X 的每一个二进制位上的 1最多可以给数组里某一个数字的对应二进制位补一个 1。如果数组全部 n 个数字的某一二进制位已经全部是 1这个位置就无法再做填充X 该位必须置 0只要数组存在至少一个数字该二进制位为 0X 就可以把这一位置 1以此获得总和增益。解题思路本题属于位运算 贪心题型核心思想按二进制位从低位到高位统计判断每一个二进制位是否还有提升空间。统计数组每一个二进制位上 1 出现的总次数存入数组v[]v[i]代表数组第i位二进制为 1 的元素个数。对于第 i 位如果v[i] n说明数组中至少有一个数字的第i位是 0X 可以把该位设置为 1带来 \(2^i\) 的总和增益如果v[i] n数组全部数字该位已经是 1无法再填充X 该位置 0。将所有可以开启的二进制位组合得到 X。最终最大总和 原数组总和 X。关键点X 每一位只要有机会就置 1因为每一位的增益互相独立贪心选择全部可填充的二进制位即可得到全局最优解。#include bits/stdc.h using namespace std; int main() { int t,n,i,j,a; cint; while(t--) { long long sum0; int v[35]{0},x0; cinn; for(i1;in;i) { cina; suma;/** 读数据统计综合 */ j0; while(a)/** V数组统计数字二进制的1的个数 */ { v[j]a%2; j; a/2; } } i32; while(v[i]0) i--;/** 找到最高位i */ for(;i0;i--) if(v[i]n)/** 第i为不全都是1X中这一位二进制置为1 */ x(1i);/** 加入X */ coutsumx xendl; } return 0; }
