题解

思路推导

设最终按位或得到的值为 $x$。若某个 $a_i$ 能选择一个 $b_j$，使得 $(a_i\mathbin{\&}b_j)$ 的所有置位都已经包含在 $x$ 中，那么这一项不会让最终结果出现 $x$ 之外的新置位。反之，只要存在一个 $a_i$ 对所有 $b_j$ 都不满足这个条件，$x$ 就不可能是合法上界。

所有输入均小于 $2^9$，所以答案也一定在 $0$ 到 $511$ 之间。按数值从小到大枚举 $x$，逐个检查每个 $a_i$ 是否存在可用的 $b_j$。第一个通过检查的 $x$ 就是最小答案。

做法

依次枚举 $x=0,1,\ldots,511$。对每个 $a_i$ 扫描整个 $b$ 序列；若找不到满足 $(a_i\mathbin{\&}b_j)\mathbin{|}x=x$ 的元素，就否定当前候选。所有位置都能找到候选时立即输出 $x$。

正确性证明

对于固定的 $x$，若每个 $a_i$ 都存在一个 $b_j$ 满足 $(a_i\mathbin{\&}b_j)\mathbin{|}x=x$，分别选择这些 $b_j$ 后，每个 $c_i$ 的置位都是 $x$ 的子集，因此所有 $c_i$ 的按位或也是 $x$ 的子集，所得值不超过 $x$。

若检查失败，则存在某个 $a_i$，无论选择哪个 $b_j$，$a_i\mathbin{\&}b_j$ 都含有 $x$ 中不存在的置位。因此任何选择得到的最终按位或都不可能是 $x$ 的子集，特别地不可能不超过 $x$ 且等于某个已枚举候选。

枚举按数值递增进行，所以第一个通过检查的候选既可实现，又不存在更小的可实现值，因而就是最优答案。

复杂度分析

最多检查 $512$ 个候选，每个候选检查 $n m$ 对元素，时间复杂度为 $O(2^9nm)$，额外空间复杂度为 $O(1)$。