兼容数字(Compatible Numbers) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
#include <vector>
using namespace std;

const int B = 22;
const int FULL = (1 << B) - 1;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<int> a(n);
    vector<int> dp(1 << B, -1);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        dp[a[i]] = a[i];
    }
    for (int bit = 0; bit < B; ++bit) {
        int mask_bit = 1 << bit;
        for (int mask = 0; mask < (1 << B); ++mask) {
            if ((mask & mask_bit) && dp[mask] == -1) {
                dp[mask] = dp[mask ^ mask_bit];
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        if (i) cout << ' ';
        cout << dp[FULL ^ a[i]];
    }
    cout << "\n";
    return 0;
}