美团2026.8.16笔试个人题解
T1.非负整数数组
题目描述
小美有一个长度为 $ n $ 的数组 $ {a_1, a_2, \dots, a_n} $，她希望构造一个非负整数 $ c $，满足 $ c $ 的二进制位数不超过数组中最大值的二进制位数（特别地，0 的二进制位数定义为 1）。
随后，她可以对数组重复进行以下操作，以使所有元素的总和最大：
- 选择一个下标 $ i $，将 $ a_i $ 修改为 $ a_i \mid c $（按位或），同时将 $ c $ 修改为 $ a_i & c $（按位与）。
在使数组元素总和达到最大值的前提下，要求初始的 $ c $ 尽可能小。
请输出最大总和以及对应的最小初始 $ c $。
说明：
- 按位或（
|）：对两个整数的二进制表示的每一位进行逻辑或操作。 - 按位与（
&）：对两个整数的二进制表示的每一位进行逻辑与操作。 - 操作可以执行任意多次，每次选择一个下标 $ i $。
输入描述
每个测试文件包含多组测试数据。
第一行输入一个整数 \(T\)（$ 1 \leq T \leq 1000 $），表示测试数据的组数。
对于每组测试数据，输入格式如下：
- 第一行输入一个整数 \(n\)（$ 1 \leq n \leq 500 $），表示数组的长度；
- 第二行输入 \(n\) 个整数 \(a_1, a_2, \ldots, a_n\)（$ 0 \leq a_i < 2^{30} $），表示数组 $ a $ 的元素。
题目分析
这两个数学运算组合起来，本质上就是，每次操作都会从\(x\)当中取出一个1分给\(a_i\)，那么我们最终的\(x\)，其实就是所有\(a_i\)所缺少的1构成的总和。
python代码
import sysLENGTH = 30
UPPER = (1 << LENGTH) - 1def len_of_bits(x):ans: int = 0while x:ans += 1x >>= 1if not ans:ans = 1return ansdef main():input = sys.stdin.read().strip('\r\n\t ').split()it = iter(input)T = int(next(it))ans = []for _ in range(T):n = int(next(it))arr = [int(next(it)) for _ in range(n)]s = sum(arr)_max = max(arr)len = len_of_bits(_max)mask = (1 << len) - 1upper = UPPERfor ai in arr:upper &= aiupper &= maskx: int = mask ^ upper # 通过和mask异或，来翻转0和1s += xans.append(f"{s} {x}")print("\n".join(ans))if __name__ == "__main__":main()
CPP代码
#include <algorithm>
#include <iostream>
#include <cstdio>constexpr int N = 505, LEN = 30;
constexpr int UPPER = (1 << LEN) - 1;
int arr[N], T;int len_of_bits(int x) {int ans = 0;while (x) {ans++;x>>=1;}return ans?ans:1;
}int main() {freopen("input.txt", "r", stdin);scanf("%d", &T);int len;while (T--) {scanf("%d", &len);int _max = -1, sum = 0;for (int i = 1; i <= len; i++) {scanf("%d", &arr[i]);sum += arr[i];_max = std::max(_max, arr[i]);}int len = len_of_bits(_max);int upper = UPPER, mask = (1 << len) - 1;for (int i = 1; i <= len; i++) {upper &= arr[i];}upper &= mask;int x = mask ^ upper;sum += x;printf("%d %d\n", sum, x);}return 0;
}