1 题目大意
给定一个长度为 $n$ 的序列 $a$。
对于每一个 $a_i$,询问是否存在 $a_j$ 使得 $a_i \& a_j = 0$,如果有输出 $a_j$(如果有多个,输出任意一个),否则输出 $-1$。
$1 \leq n \leq 10^6, 1 \leq a_i \leq 4\cdot 10^6$。
2 思路
注意到 $a_i \& a_j = 0$,其实就是询问是否有数字满足其是 $a_i$ 的补集的子集。
SOS DP 求出每个集合是否有数字是其子集即可。
Continue reading “Codeforces 165E Compatible Numbers”