Codeforces 题解 - [B. Friendly Arrays]
题目描述
You are given two arrays of integers — \(a_1, \ldots, a_n\) of length \(n\), and \(b_1, \ldots, b_m\) of length \(m\). You can choose any element \(b_j\) from array \(b\) (\(1 \leq j \leq m\)), and for all \(1 \leq i \leq n\) perform \(a_i = a_i | b_j\). You can perform any number of such operations.
After all the operations, the value of \(x = a_1 \oplus a_2 \oplus \ldots \oplus a_n\) will be calculated. Find the minimum and maximum values of \(x\) that could be obtained after performing any set of operations.
Above, \(|\) is the bitwise OR operation, and \(\oplus\) is the bitwise XOR operation.。
输入格式
The first line contains a single integer \(t\) (\(1 \leq t \leq 10^4\)) — the number of test cases. This is followed by the description of the test cases.
The first line of each test case contains two integers \(n\) and \(m\) (\(1 \leq n, m \leq 2 \cdot 10^5\)) — the sizes of arrays \(a\) and \(b\).
The second line of each test case contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(0 \leq a_i \leq 10^9\)) — the array \(a\).
The third line of each test case contains \(m\) integers \(b_1, b_2, \ldots, b_m\) (\(0 \leq b_i \leq 10^9\)) — the array \(b\).
It is guaranteed that the sum of values of \(n\) and \(m\) across all test cases does not exceed \(2 \cdot 10^5\).
输出格式
For each test case, output \(2\) numbers: the minimum and maximum possible values of \(x\) after performing any set of operations.
题目大意
对于每个测试用例，有一个数组a，和一个数组b。
对于每个 \(a_{i}\), 可以选择 \(b_{j}\) 对所有的\(1 \leq i \leq n\)进行 \(a_{i} = a_{i} | b_{j}\) 的操作，进行任意次。 求出 \(x = a_{1} \oplus a_{2} \oplus \ldots \oplus a_{n}\) 的最小值和最大值。
输入
2
2 3
0 1
1 2 3
3 1
1 1 2
1
输出
0 1
2 3
解题思路
- 对于每个\(b_{j}\)进行操作以后, \(b_{j}\)的二进制位上为1的位，在a数组中所有的对应的位都会变成1。(并且会保持这种状态，因为在OR中的运算，位不会由1变成0)。
- 由以上的操作，仍是对于每个\(b_{j}\)，我们仍对对应的这些为1的位考虑, 如果\(n\)为奇数，那么a的最终的XOR的结果会将此位变成1(因为有奇数个1进行异或)。同理如果\(n\)是偶数最终的XOR的结果会将此位变成0。
- 因此可以得出结果，如果是奇数，最大值就是对所有的\(b_{j}\)都进行一次操作的a的XOR的结果，最小值就是不进行操作的直接a的XOR的结果。如果是偶数，最大值就是不进行操作的直接a的XOR的结果，最小值就是对所有的\(b_{j}\)都进行一次操作后的a的XOR的结果。
- 可以看到如果直接对每个\(b_{j}\)进行操作时间复杂度是\(O(nm)\)，会超时。但是由于第一个要点，我们可以先对b数组进行预处理，将b数组中所有的数进行OR运算，得到一个数，然后再对这个数进行操作。时间复杂度为\(O(n+m)\)。
代码实现
#include "bits/stdc++.h"
using namespace std;
// #define int int64_t
constexpr int INF = 1e9 + 10;
void Solution()
{
int n, m;
cin >> n >> m;
vector<int> a(n + 1), b(n + 1);
int c = 0;
for(int i = 1;i <= n;++i)
{
cin >> a[i];
}
for(int i = 1;i <= m;++i)//预处理所有的b数组的OR运算
{
int aa; cin >> aa;
c |= aa;
}
int Ans = 0, ansOnly = 0;
if(n & 1)//a数组个数为奇数
{
for(int i = 1;i <= n;++i)
{
ansOnly ^= a[i];
Ans ^= a[i] | c;
}
cout << ansOnly << ' ' << Ans << '\n';
}
else//为偶数
{
for(int i = 1;i <= n;++i)
{
ansOnly ^= a[i];
Ans ^= a[i] | c;
}
cout << Ans << ' ' << ansOnly << '\n';
}
return;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--)
{
Solution();
}
return 0;
}
/*
1
3 3 2
3 4 5
1 2 3
*/