【位运算】Boboniu and Bit Operations—CF1395C

Bit Operations—CF1395C"/>

【位运算】Boboniu and Bit Operations—CF1395C

Boboniu and Bit Operations—CF1395C

翻译

Boboniu喜欢位运算。他想和你玩一个游戏。

Boboniu给你两个非负整数序列 a 1 , a 2 , … , a n a_1,a_2,\ldots,a_n a1​,a2​,…,an​ 和 b 1 , b 2 , … , b m b_1,b_2,\ldots,b_m b1​,b2​,…,bm​。

对于每个 i i i ( 1 ≤ i ≤ n 1\le i\le n 1≤i≤n)，你需要选择一个 j j j ( 1 ≤ j ≤ m 1\le j\le m 1≤j≤m)，并令 c i = a i & b j c_i=a_i\& b_j ci​=ai​&bj​，其中 & \& & 表示位与运算。注意，你可以为不同的 i i i选择相同的 j j j。

找到可能的最小值 c 1 ∣ c 2 ∣ … ∣ c n c_1 | c_2 | \ldots | c_n c1​∣c2​∣…∣cn​，其中 ∣ | ∣ 表示位或运算。
输入

第一行包含两个整数 n n n 和 m m m ( 1 ≤ n , m ≤ 200 1\le n,m\le 200 1≤n,m≤200)。

接下来一行包含 n n n 个整数 a 1 , a 2 , … , a n a_1,a_2,\ldots,a_n a1​,a2​,…,an​ ( 0 ≤ a i < 2 9 0\le a_i < 2^9 0≤ai​<29)。

接下来一行包含 m m m 个整数 b 1 , b 2 , … , b m b_1,b_2,\ldots,b_m b1​,b2​,…,bm​ ( 0 ≤ b i < 2 9 0\le b_i < 2^9 0≤bi​<29)。
输出

输出一个整数：可能的最小值 c 1 ∣ c 2 ∣ … ∣ c n c_1 | c_2 | \ldots | c_n c1​∣c2​∣…∣cn​。
注意

对于第一个例子，我们有 c 1 = a 1 & b 2 = 0 c_1=a_1\& b_2=0 c1​=a1​&b2​=0， c 2 = a 2 & b 1 = 2 c_2=a_2\& b_1=2 c2​=a2​&b1​=2， c 3 = a 3 & b 1 = 0 c_3=a_3\& b_1=0 c3​=a3​&b1​=0， c 4 = a 4 & b 1 = 0 c_4 = a_4\& b_1=0 c4​=a4​&b1​=0。因此 c 1 ∣ c 2 ∣ c 3 ∣ c 4 = 2 c_1 | c_2 | c_3 |c_4 =2 c1​∣c2​∣c3​∣c4​=2，这是我们能得到的最小答案。

思路

我们发现答案的范围很小（ [ 0 , ( 1 > > 9 ) − 1 ] [0, ~(1>>9)-1] [0, (1>>9)−1]），所以我们可以尝试遍历答案，找出一个满足题目要求的最小的值。

假设当前遍历到了 r e s res res，如果 r e s res res 是最终的答案，那么以下条件必须要满足：
对于任意的 a i a_i ai​ （ 1 ≤ i ≤ n 1 \le i \le n 1≤i≤n），存在 b j b_j bj​ （ 1 ≤ j ≤ m 1 \le j \le m 1≤j≤m）使得 a i & b j ∣ r e s = r e s a_i \& b_j |~res=res ai​&bj​∣ res=res。意思就是 a i & b j a_i \& b_j ai​&bj​ 的二进制表示中，不存在它的某一位上是 1 1 1 而 r e s res res 的二进制表示中这一位是 0 0 0 的情况。

假如以上条件已经满足，那么 r e s res res 的二进制位为 0 0 0 的位 在 c 1 ∣ c 2 ∣ … ∣ c n c_1 | c_2 | \ldots | c_n c1​∣c2​∣…∣cn​ 的二进制位中一定为 1 1 1。但 r e s res res 的二进制位为 0 0 0 的位在 c 1 ∣ c 2 ∣ … ∣ c n c_1 | c_2 | \ldots | c_n c1​∣c2​∣…∣cn​ 的二进制位中一定是 1 1 1 吗？
假如 c 1 ∣ c 2 ∣ … ∣ c n c_1 | c_2 | \ldots | c_n c1​∣c2​∣…∣cn​ 这一位不是 1 1 1，例如这种情况：
r e s = 101011 1 2 res = 1010111_2 res=10101112​， c 1 ∣ c 2 ∣ … ∣ c n = 101001 1 2 c_1 | c_2 | \ldots | c_n = 1010011_2 c1​∣c2​∣…∣cn​=10100112​，那么这时的 r e s res res 虽然满足上述条件，但却也不是正确答案。
其实这种情况不必担心，因为在 1101011 1 2 11010111_2 110101112​ 之前已经遍历到了 101001 1 1 1010011_1 10100111​ 了，而根据上边的推论这个就是最终答案，这也是为什么我们要升序遍历 r e s res res 的原因。

这里很难理解，文字并不能准确地表达出我的意思，仅仅作为思路上的引导。

C o d e Code Code

#include <bits/stdc++.h>
#define int long long
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
using namespace std;
using PII = pair<int, int>;
using i128 = __int128;
const int N = 2e5 + 10;int n, m;void solve(int Case) {cin >> n >> m;vector<int> a(n + 1), b(m + 1);for (int i = 1; i <= n; i ++) cin >> a[i]; for (int i = 1; i <= m; i ++) cin >> b[i];// 升序遍历，找到满足条件的最小resfor (int res = 0; res < 1 << 9; res ++) {int OK = 1;for (int i = 1; i <= n; i ++) {int ok = 0;for (int j = 1; j <= m; j ++) {if ((a[i] & b[j] | res) == res) {ok = 1;break;}}if (ok == 0) {OK = 0;break;}}if (OK) {cout << res << "\n";return;}}
}signed main() {cin.tie(0)->ios::sync_with_stdio(false);int T = 1;
//	cin >> T; cin.get();int Case = 0;while (++ Case <= T) solve(Case);return 0;
}