我们可以多次选择当前数组中的某个数 x,把所有元素同时变为 a_i xor x。关键观察:
g。x=a_k,则 g=a_k;第二步必须从新数组中选 x'=a_j xor a_k,于是新的整体异或量变为 g'=a_k xor (a_j xor a_k)=a_j;继续下去可证明每一步后的整体异或量始终是原数组中的某个元素。{a_i xor g},其中 g ∈ {0} ∪ {a_1,…,a_n}(允许不操作时 g=0)。于是问题化简为:在有限候选集合 G={0} ∪ {a_i} 中,选择 g 最大化
给定一个由 n 个非负整数构成的数组 {a1,a2,…,an} 。你可以进行以下操作任意次(可以不执行任何操作):
你的目标是使操作后数组中所有元素之和最大化,输出该最大值。