好题。
套路地,考虑枚举最优解的 \(a\) 异或和二进制下与 \(k\) 的 \(\text{LCP}\),设在第 \(i\) 位不同。这样的好处是 \(i\) 之后的位可以随便选。
之后按位贪心确定最优解 \(b\) 的异或和。考虑之前的答案是 \(res\),当前在确定第 \(j\) 位,如何判断 \(res + 2^j\) 可行。
考虑将 \(2^i \left\lfloor\frac{a}{2^i}\right\rfloor\) 和 \(2^j \left\lfloor\frac{b}{2^j}\right\rfloor\) 拼成一个 \(60\) 位的二进制数,把它插入线性基内,判断 \(res + 2^j\) 能否被这些数凑出来即可。
注意最后要检查 \(res\) 是否能被 \(b_i\) 凑出来。
code
// Problem: G - Xor Cards
// Contest: AtCoder - Monoxer Programming Contest 2022(AtCoder Beginner Contest 249)
// URL: https://atcoder.jp/contests/abc249/tasks/abc249_g
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
struct LinearBasis {
ll p[65];
bool fl;
inline void init() {
fl = 0;
mems(p, 0);
}
inline void insert(ll x) {
for (int i = 59; ~i; --i) {
if (x & (1LL << i)) {
if (!p[i]) {
p[i] = x;
return;
}
x ^= p[i];
}
}
fl = 1;
}
inline bool check(ll x) {
if (!x) {
return fl;
}
for (int i = 59; ~i; --i) {
if (x & (1LL << i)) {
if (!p[i]) {
return 0;
}
x ^= p[i];
}
}
return 1;
}
} B;
const int maxn = 1010;
ll n, m, a[maxn], b[maxn];
void solve() {
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%lld%lld", &a[i], &b[i]);
}
ll ans = -1;
for (int i = 29; i >= -1; --i) {
if (i >= 0 && ((~m) & (1LL << i))) {
continue;
}
ll k = (i == -1 ? m : (((m ^ (1LL << i)) >> i) << i)), res = 0;
for (int j = 29; ~j; --j) {
B.init();
for (int k = 1; k <= n; ++k) {
B.insert((((a[k] >> max(0, i)) << max(0, i)) << 30) | ((b[k] >> j) << j));
}
if (B.check((k << 30) | (res | (1LL << j)))) {
res |= (1LL << j);
}
}
B.init();
for (int k = 1; k <= n; ++k) {
B.insert((((a[k] >> max(0, i)) << max(0, i)) << 30) | b[k]);
}
if (B.check((k << 30) | res)) {
ans = max(ans, res);
}
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Beginner AtCoder Contest Cards 249beginner atcoder contest cards contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 332 beginner atcoder contest 315