C. Boboniu 与位运算 —— 详细题解

---

题目重述

给定两个序列：

• $a_1, a_2, \dots, a_n$（$0 \le a_i < 2^9$）
• $b_1, b_2, \dots, b_m$（$0 \le b_i < 2^9$）

对于每个 $i$（$1 \le i \le n$），你需要选择一个 $j$（$1 \le j \le m$），令：

$$c_i = a_i \ \&\ b_j$$

其中 $\&$ 是按位与运算。

求：

$$c_1 \ | \ c_2 \ | \ \dots \ | \ c_n$$

的最小可能值，其中 $|$ 是按位或运算。

---

关键观察

观察 1：值域很小

因为 $a_i, b_j < 2^9 = 512$，所以：

• $a_i \ \&\ b_j < 512$
• $c_1 \ | \ c_2 \ | \dots \ | \ c_n < 512$

因此，答案 $ans$ 的取值范围是 $[0, 511]$。

观察 2：OR 运算的性质

设 $X = c_1 \ | \ c_2 \ | \dots \ | \ c_n$。

对于任意 $i$，$c_i$ 的二进制表示中，所有为 $1$ 的位，在 $X$ 中一定也是 $1$。
反过来，$X$ 中为 $0$ 的位，在所有 $c_i$ 中也都必须是 $0$。

即：

$$c_i \ \& \ (\sim X) = 0 \quad \text{对所有 } i \text{ 成立} $$

等价地：

$$(c_i \ | \ X) = X \quad \text{对所有 } i \text{ 成立}$$

观察 3：可行性判断

对于固定的 $X$，如果能对每个 $i$ 找到一个 $j$，使得：

$$(a_i \ \&\ b_j) \ | \ X = X$$

则 $X$ 是一个可行答案。

上式等价于：

$$(a_i \ \&\ b_j) \ \& \ (\sim X) = 0$$

即 $a_i \ \&\ b_j$ 不能包含任何 $X$ 中为 $0$ 的位。

---

解法一：暴力枚举答案（推荐）

由于答案只有 $512$ 种可能，从小到大枚举 $X = 0$ 到 $511$，检查是否可行。第一个可行的 $X$ 就是答案。

检查方法

对每个 $i$，检查是否存在 $j$ 使得：

$$(a_i \ \&\ b_j) \ | \ X = X$$

等价于：

$$(a_i \ \&\ b_j) \ \& \ (\sim X) = 0$$

即 $(a_i \ \&\ b_j)$ 不含有任何 $X$ 中没有的位。

实现时，可以预先计算 $\sim X$，然后对每个 $(i, j)$ 判断。

---

代码实现（解法一）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    vector<int> a(n), b(m);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) cin >> b[i];
    
    // 从小到大枚举答案
    for (int ans = 0; ans < 512; ans++) {
        bool ok = true;
        
        for (int i = 0; i < n; i++) {
            bool found = false;
            for (int j = 0; j < m; j++) {
                if (((a[i] & b[j]) | ans) == ans) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                ok = false;
                break;
            }
        }
        
        if (ok) {
            cout << ans << '\n';
            return 0;
        }
    }
    
    return 0;
}

时间复杂度：$O(512 \cdot n \cdot m) \le 512 \times 200 \times 200 = 2 \times 10^7$，可接受。

---

解法二：逐位贪心（更高效）

从高位到低位确定答案的每一位。

思路

1. 初始 $ans = 0$
2. 对于 $bit$ 从 $8$ 到 $0$（从高到低）：
   • 尝试将这一位设为 $0$，即检查 $candidate = ans$（当前已确定的位保持原样，当前位为 $0$）是否可行
   • 如果可行，则这一位保持 $0$
   • 如果不可行，则这一位必须为 $1$，即 $ans \ |= (1 \ll bit)$

可行性判断

与解法一相同：对每个 $i$，检查是否存在 $j$ 使得 $(a_i \& b_j) \ | \ candidate = candidate$。

---

代码实现（解法二）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    vector<int> a(n), b(m);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) cin >> b[i];
    
    int ans = 0;
    
    // 从高位到低位贪心
    for (int bit = 8; bit >= 0; bit--) {
        int candidate = ans;  // 当前位尝试设为 0
        
        bool ok = true;
        for (int i = 0; i < n; i++) {
            bool found = false;
            for (int j = 0; j < m; j++) {
                if (((a[i] & b[j]) | candidate) == candidate) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                ok = false;
                break;
            }
        }
        
        if (!ok) {
            // 当前位必须设为 1
            ans |= (1 << bit);
        }
        // 如果 ok，当前位保持 0，ans 不变
    }
    
    cout << ans << '\n';
    
    return 0;
}

时间复杂度：$O(9 \cdot n \cdot m) \le 9 \times 200 \times 200 = 3.6 \times 10^5$，非常快。

---

解法三：DP / 位掩码

定义 $dp[i][mask]$ 表示考虑前 $i$ 个数，能否得到 OR 值为 $mask$。

转移

$$dp[i+1][mask \ | \ (a_i \& b_j)] = true \quad \text{若 } dp[i][mask] = true $$

初始化

$dp[0][0] = true$

答案

$\min\{mask \mid dp[n][mask] = true\}$

---

代码实现（解法三）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    vector<int> a(n), b(m);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) cin >> b[i];
    
    vector<vector<bool>> dp(n + 1, vector<bool>(512, false));
    dp[0][0] = true;
    
    for (int i = 0; i < n; i++) {
        for (int mask = 0; mask < 512; mask++) {
            if (!dp[i][mask]) continue;
            for (int j = 0; j < m; j++) {
                int newMask = mask | (a[i] & b[j]);
                dp[i + 1][newMask] = true;
            }
        }
    }
    
    int ans = 511;
    for (int mask = 0; mask < 512; mask++) {
        if (dp[n][mask]) {
            ans = min(ans, mask);
        }
    }
    
    cout << ans << '\n';
    
    return 0;
}

时间复杂度：$O(n \cdot m \cdot 512) \approx 2 \times 10^7$，可接受。

---

复杂度总结

解法	时间复杂度	空间复杂度
暴力枚举答案	$O(512 \cdot n \cdot m)$	$O(n + m)$
逐位贪心	$O(9 \cdot n \cdot m)$
DP / 位掩码	$O(n \cdot m \cdot 512)$	$O(n \cdot 512)$

---

推荐

• 解法一最简单，不易出错，适合比赛时快速实现
• 解法二最快，适合追求效率
• 解法三最直观，适合理解 DP 思想