Maximum AND

Maximum AND

Created by LXC on Fri Oct 20 01:47:17 2023

https://codeforces.com/problemset/problem/1721/D

ranting: 1800

tag: bitmasks, dfs and similar, divide and conquer, greedy, sortings

problem

给出两个长度都为n的数组a和数组b。现在你可以重排b数组的元素。

并得到一个新数组c,其中ci=aibi

并使得Misplaced &最大

solution

让与和最大,那应该贪心,尽量选择高位全为1.

如果第x位与和为1,那么a中第x位1的数目和b中第x位1的数目之和恰好为n,否则会存在异或为0的情况。我们找到所有满足的x,设有k个,从高位到低位分别为x1,x2,,xk

ai为a的第i个元素,ai,j为a的第i个元素的低位第j位。

然后自定义一种排序比较器,对a数组中任意两个元素aiaj只有字典序ai,x1ai,x2ai,xk<aj,x1aj,x2aj,xkai排在前面。对b数组中任意两个元素bibj只有字典序bi,x1bi,x2bi,xk>bj,x1bj,x2bj,xkbi排在前面。

对a和b数组排序后,得到他们的异或与和s。如果s2xi,遍历x1,x2,,xk找到第一个xi删除掉,其中s的第xi位为0。

然后继续排序,计算异或与和s。直到s=2xi,便找到了答案。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;


void sol() {
int n;
cin >> n;
vector<int> a(n), b(n);
for (auto& i:a) cin >> i;
for (auto& i:b) cin >> i;
vector<int> d;
for (int x=30; x>=0; x--) {
int a1=0, b1=0;
for (int i=0; i<n; i++) {
a1 += a[i]>>x&1;
b1 += b[i]>>x&1;
}
if (a1 + b1 == n) d.push_back(x);
}
int ans = 0;
while (1) {
sort(a.begin(), a.end(), [&](auto x, auto y) {
for (int i:d) {
if ((x>>i&1) != (y>>i&1)) {
return (x>>i&1) < (y>>i&1);
}
}
return false;
});
sort(b.begin(), b.end(), [&](auto x, auto y) {
for (int i:d) {
if ((x>>i&1) != (y>>i&1)) {
return (x>>i&1) > (y>>i&1);
}
}
return false;
});
ans = a[0]^b[0];
for (int i=1; i<n; i++) {
ans &= a[i]^b[i];
}
int ok = 1;
for (int i=0; i<d.size(); i++) {
if (ans>>d[i]&1) continue;
d.erase(d.begin()+i);
ok = 0;
break;
}
if (ok) break;
}
cout << ans << "\n";
}

int main() {
cout << setprecision(15) << fixed;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifndef SINGLE_INPUT
int t;
cin >> t;
// if (t == 10000)
// for (int i=1; i<=t; i++) {
// int n;
// cin >> n;
// vector<int> a(n), b(n);
// for (auto& i:a) cin >> i;
// for (auto& i:b) cin >> i;
// if (13 == i) {
// cout << n << endl;
// for (auto i:a) cout << i << " "; cout << endl;
// for (auto i:b) cout << i << " "; cout << endl;
// }
// }
// else
while (t--) {
sol();
}
#else
sol();
#endif
return 0;
}