美团笔试 美团笔试题 0816
笔试时间：2025年8月16日
往年笔试合集：
第一题：组数制进二
小美有一个长度为 n 的数组 {a_1,a_2,...,a_n}，他希望构造一个非负整数 x，满足 x 的二进制位数不超过数组中最大值的二进制位数（特别的 0 二进制位数为 1 ）。 随后，可对数组 a 重复进行以下操作，以使所有元素的总和最大：
选择一个下标 i，同时将 a_i 修改为 a_i or x，将 x 修改为 a_i and x。 在使元素总和达到最大值的前提下，要求所有操作前初始的 x 尽可能小。请输出最大总和及对应的最小 x。
按位或：or 表示按位或运算，即对两个整数的二进制表示的每一位进行逻辑或操作。 按位与：and 表示按位与运算，即对两个整数的二进制表示的每一位进行逻辑与操作。
输入描述
每个测试文件均包含多组测试数据。 第一行输入一个整数 T，代表数据组数；
对于每组测试数据，输入如下： 第一行输入一个整数 n，表示数组的长度；
第二行输入 n 个整数 a_1,a_2,表示数组 a 的元素。
输出描述
对于每组测试数据，新起一行。输出两个整数，用空格分隔：第一个整数为数组可以达到的最大总和；第二个整数为在达到最大总和的前提下初始最小的 x。
样例输入
2
2
3 3
3
1 2 3
样例输出
6 0
9 3
参考题解
这个问题的关键在于理解重复执行操作后，数组 a 和整数 x 的最终状态会是什么。操作如下：a_i = a_i or xx = a_i and x考虑系统中所有数字（a_1, a_2, ..., a_n 和 x）的总和。有一个重要的位运算性质：对于任意两个整数 p 和 q，它们的和等于它们按位或与按位与的和，即 p + q = (p | q) + (p & q)。当我们在 a_i 和 x 上执行操作时，它们的新值是 a_i' = a_i | x 和 x' = a_i & x。根据上述性质，a_i' + x' = a_i + x。这意味着每次操作，a_i 和 x 的总和保持不变。由于其他数组元素 a_j (j ≠ i) 不受影响，因此整个系统 (a_1 + a_2 + ... + a_n + x) 的总和是一个不变量。我们的目标是最大化最终的数组总和 sum(a_final)。 因为系统总和不变，所以： sum(a_final) + x_final = sum(a_initial) + x_initial要使 sum(a_final) 最大化，我们必须让 x_final 尽可能小。现在的问题是，x_final 的最小值是多少？让我们分析单个比特位（例如第 k 位）的行为。如果 a_i 的第 k 位是 0，而 x 的第 k 位是 1，操作后 a_i 的第 k 位变为 1，x 的第 k 位变为 0。这个比特从 x 移动到了 a_i。如果 a_i 的第 k 位是 1，而 x 的第 k 位是 1，操作后 a_i 和 x 的第 k 位都保持为 1。这个比特无法从 x 中移除。由此我们得到一个关键结论：x 中某个位置的比特 k，只有在与一个 a_i 进行操作，而这个 a_i 在 k 位上为 0 时，才能从 x 中被“清除”（移出）。如果对于某个比特位 k，数组中所有的元素 a_i 在该位上都是 1，那么一旦 x 在该位上也是 1，这个比特将永远“卡”在 x 中，无法被清除。确定最终的 x： 令 AND_a = a_1 & a_2 & ... & a_n。这个数代表了数组 a 中所有元素共同拥有的比特位。如果初始 x 在某个位上是 1，并且 AND_a 在这个位上也是 1，那么最终的 x_final 在该位上必然是 1。在其他所有位上，我们都可以通过选择一个合适的 a_i (在该位上为0) 来将 x 的对应位清零。因此，x_final = AND_a & x_initial。确定最大和的表达式： 将 x_final 代入不变量公式： sum(a_final) = sum(a_initial) + x_initial - x_final sum(a_final) = sum(a_initial) + x_initial - (AND_a & x_initial)利用 p - (p & q) = p & (~q)，我们可以简化表达式：sum(a_final) = sum(a_initial) + (x_initial & (~AND_a))寻找最优的 x：我们的目标是选择一个初始 x (x_initial) 来最大化 sum(a_final)，同时在总和最大的前提下让 x 尽可能小。为了最大化 sum(a_final) = sum(a_initial) + (x_initial & (~AND_a))，我们需要最大化 (x_initial & (~AND_a)) 这一项。x 受到约束：它的二进制位数不能超过数组最大值 max(a) 的二进制位数。设 max_bits = max(a).bit_length()（特别地，当 max(a) = 0 时，位数为1），这意味着 x < 2^max_bits。所有小于 2^max_bits 的数可以用一个掩码 mask = (1 << max_bits) - 1 来表示。那么，要最大化 x & (~AND_a)，我们应该让 x 包含 ~AND_a 中尽可能多的比特位，同时受 mask 的限制。最优的选择就是 x = (~AND_a) & mask。这个 x 不仅使 (x & (~AND_a)) 达到最大值，它本身也是所有能达到这个最大值的 x 中最小的一个。因为任何更小的 x 都会缺少一些必要的比特位，导致 (x & (~AND_a)) 的值变小。
C++：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
if (!(cin >> T)) return 0;
while (T--) {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
long long sum_a = 0;
for (int x : a) sum_a += x;
if (n == 0) {
// 与原 Python 行为一致的保护（虽然通常 n >= 1）
cout << 0 << ' ' << 0 << "\n";
continue;
}
int and_a = (1 << 30) - 1; // 覆盖所有可能位 (a[i] < 2^30)
for (int x : a) and_a &= x;
int max_val = 0;
if (!a.empty()) max_val = *max_element(a.begin(), a.end());
int max_bits = (max_val == 0) ? 1 : (32 - __builtin_clz(max_val)); // bit_length
long long mask = (1LL << max_bits) - 1; // 用 64 位承接
long long min_x = (~and_a) & mask; // 两数补与掩码
long long max_sum = sum_a + min_x;
cout << max_sum << ' ' << min_x << "\n";
}
return 0;
}
Java：
import java.io.*;
import java.util.*;
public class Main {
// 简单快速输入
static final class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0, len = 0;
FastScanner(InputStream is) { this.in = is; }
private int read() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) return -1;
}
return buffer[ptr++];
}
int nextInt() throws IOException {
int c, sgn = 1, x = 0;
do { c = read(); } while (c <= 32 && c != -1);
if (c == '-') { sgn = -1; c = read(); }
while (c > 32 && c != -1) {
x = x * 10 + (c - '0');
c = read();
}
return x * sgn;
}
}
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner(System.in);
StringBuilder out = new StringBuilder();
int T = fs.nextInt();
for (int tc = 0; tc < T; tc++) {
int n = fs.nextInt();
int[] a = new int[Math.max(n, 0)];
for (int i = 0; i < n; i++) a[i] = fs.nextInt();
long sumA = 0L;
for (int x : a) sumA += x;
if (n == 0) {
out.append("0 0\n");
continue;
}
int andA = (1 << 30) - 1; // 覆盖所有可能位 (a[i] < 2^30)
for (int x : a) andA &= x;
int maxVal = 0;
for (int x : a) if (x > maxVal) maxVal = x;
int maxBits = (maxVal == 0) ? 1 : (32 - Integer.numberOfLeadingZeros(maxVal));
int mask = (1 << maxBits) - 1; // maxBits ≤ 30，int 安全
int minX = (~andA) & mask; // 与 Python: (~and_a) & mask 一致
long maxSum = sumA + (minX & 0xffffffffL) - 0L; // minX 作为非负整型加到 long
out.append(maxSum).append(' ').append(minX).append('\n');
}
System.out.print(out.toString());
}
}
Python：
import sys def solve(): n = int(input()) a = list(map(int, input().split())) # 1. 计算初始总和与按位与 sum_a = sum(a) if n == 0: # 边界情况处理，虽然题目约束 n >= 1 print(0, 0) return # Python的 ~-1 是 -2, 而不是全1。为了安全，用一个足够大的数来初始化与操作的起始值 # 2^30 - 1 < 2^30, a_i < 2^30, 所以 (1<<30) - 1 包含所有可能的位 and_a = (1 << 30) - 1 for x in a: and_a &= x # 2. 找到最大值 max_val = 0 if a: max_val = max(a) # 3. 确定x的最大位数 # 特别的 0 二进制位数为 1 if max_val == 0: max_bits = 1 else: max_bits = max_val.bit_length() # 4. 创建掩码 mask = (1 << max_bits) - 1 # 5. 计算最小的最优x # ~and_a 在Python中是负数，直接与正数mask进行&操作即可得到正确结果 min_x = (~and_a) & mask # 6. 计算最大总和 # 根据推导，增加的和就是 (min_x & (~and_a))，由于min_x的定义，这等于min_x max_sum = sum_a + min_x print(max_sum, min_x) def main(): T = int(input()) for _ in range(T): solve() if __name__ == "__main__": main()
第二题：数组同构
定义变换函数：将一个正整数 x 用其二进制表示中 1 的个数替换，记作 g(x)（即 popcount）； 给定两个长度均为 n 的正整数数组 A 和 B； 你可以对 A 或 B 中的任意元素反复执行以下操作，每次操作计数 1：将该元素 x 替换为 g(x)； 当且仅当存在置换 \pi，使得对所有 1\leqq i\leqq n 都有 A_i = B_{\pi(i)}，也就是两个数组都排序后完全相同，我们称 A 与 B 同构。请计算使 A 与 B 同构所需的最少操作次数。 可以证明题目一定有解。
输入描述
第一行输入一个整数 t，表示测试用例数；
每个测试用例输入格式如下：
第一行输入一个整数 n；
第二行输入 n 个整数 A_1, A_2,；
第三行输入 n 个整数 B_1, B_2
输出描述
对于每个测试用例，输出一行整数——使 A 与 B 同构的最少操作次数。
样例输入
2
3
4 1 2
2 2 1
3
7 3 5
3 3 5
样例输出
2
1
参考题解
C++：
#include <bits/stdc++.h>
using namespace std;
static const int MAX_SMALL = 60;
int popcnt_ll(long long x) {
return __builtin_popcountll((unsigned long long)x);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
if (!(cin >> t)) return 0;
while (t--) {
int n;
cin >> n;
vector<long long> A(n), B(n);
for (int i = 0; i < n; ++i) cin >> A[i];
for (int i = 0; i < n; ++i) cin >> B[i];
// Counter(A), Counter(B)
unordered_map<long long, long long> ca, cb;
ca.reserve(n * 2 + 3);
cb.reserve(n * 2 + 3);
for (auto x : A) ++ca[x];
for (auto x : B) ++cb[x];
vector<long long> extraA(MAX_SMALL + 1, 0), extraB(MAX_SMALL + 1, 0);
long long total_cost = 0;
// all_keys = keys of ca ∪ keys of cb
unordered_set<long long> keys;
keys.reserve(ca.size() + cb.size());
for (auto &p : ca) keys.insert(p.first);
for (auto &p : cb) keys.insert(p.first);
f
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南
投递美团等公司10个岗位