传送门：https://www.luogu.com.cn/problem/CF165E
题意简述：给定一个数组，对于每个数寻找任意一个与其位与为 \(0\) 的数。
字典树上貌似不太可做，找找看性质。我们只需要保证当前数为 \(1\) 的位为 \(0\)，而为 \(0\) 的位置没有限制条件。例如一个数和 \((1011)_2\) 位与为 \(0\)，那么显然与 \((1001)_2\) 位与为 \(0\)，因为他在相同位置少了个 \(1\)。
我们不妨可以预处理出整个数组每个数可能与其位与为 \(0\)，最紧的数，也就是在可为 \(1\) 的位置上都放上 \(1\)。与某个数位与为 \(0\) 的数，只能由最紧的数去除若干个 \(1\) 得到。对于每个可行的数，去除二进制为 \(1\) 的位置把自身的答案给到下一个更松的数，显然无后效性，可以用动态规划解决这个问题。
方程很简单：令 \(f_i\) 表示原数组中一个位与 \(i\) 为 \(0\) 的数，初始 \(f_{a_i \oplus INF}=a_i\)，转移：\(f_i=f_{i|(1<<j)}\)，当发现第一个合法位置break掉。
#include <bits/stdc++.h>const int N = 2e6 + 1, inf = (1 << 22) - 1;using namespace std;int f[inf + 1], a[N];int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);memset(f, -1, sizeof f);int n;cin >> n;for (int i = 1; i <= n; ++i) {cin >> a[i];f[inf ^ a[i]] = a[i];}for (int num = inf; ~num; --num) {for (int i = 0; i <= 21; ++i) {if (~f[num]) break;if ((num >> i & 1) == 0) f[num] = f[num | 1 << i];}}for (int i = 1; i <= n; ++i) cout << f[a[i]] << ' ';return 0;
}