T1. 改写
如果两个数不同，那么一定存在一个 \(b\)，使得其中一个数的第 \(b\) 位为 \(1\)，另一个数为 \(0\) 。
这意味着，如果 \(\{a_i \vee x\}\) 中有至少两个不同的数，那么一定存在一个 \(b\)，使得：
- \(x\) 的第 \(b\) 位为 \(0\)
- \(\{a_i\}\) 中存在一个元素的第 \(b\) 位为 \(1\)；
- \(\{a_i\}\) 中存在一个元素的第 \(b\) 位为 \(0\)
于是我们可以枚举这个 \(b\)，判断条件2、条件3是否满足。如果满足，我们可以从高到低贪心地考虑 \(b\) 以外的每个二进制位，找到最大的合法的 \(x\) 。
时间复杂度为 \(O(30n)\) 。
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)using namespace std;
using ll = long long;void solve() {int n, k;cin >> n >> k;vector<int> a(n);rep(i, n) cin >> a[i];ll ans = 0;rep(i, 30) {int cnt = 0;for (int x : a) cnt += x>>i&1;if (cnt == 0 or cnt == n) continue;ll now = 0;for (int j = 29; j >= 0; --j) {if (j == i) continue;if (now+(1<<j) > k) continue;now += 1<<j;}ans = max(ans, now);}cout << ans << '\n';
}int main() {int t;cin >> t;while (t--) solve();return 0;
}