Codeforces 165 E. Compatible Numbers【子集前缀和】

LINK

---

题目大意

给你一个数组，问你数组中的每个数是否可以在数组里面找到一个数和他and起来是0，如果可以就输出这个数，否则就输出-1

思路

首先很显然的是可以考虑找到每个数每一位都取反的数的子集

如果子集中存在一个数就满足，否则就不满足

然后就做一个子集前缀和

for (int i = 0; i < n; i++) {

  for (int s = 0; s <= up; s++) {

    if ((s >> i) & 1) dp[s] trans from dp[s ^ (1 << i)];

  }

}

---

//Author: dream_maker

#include<bits/stdc++.h>

using namespace std;

//----------------------------------------------

typedef pair<int, int> pi;

typedef long long ll;

typedef double db;

#define fi first

#define se second

#define fu(a, b, c) for (int a = b; a <= c; ++a)

#define fd(a, b, c) for (int a = b; a >= c; --a)

#define fv(a, b) for (int a = 0; a < (signed)b.size(); ++a)

const int INF_of_int = 1e9;

const ll INF_of_ll = 1e18;

template <typename T>

void Read(T &x) {

  bool w = 1;x = 0;

  char c = getchar();

  while (!isdigit(c) && c != '-') c = getchar();

  if (c == '-') w = 0, c = getchar();

  while (isdigit(c)) {

    x = (x<<1) + (x<<3) + c -'0';

    c = getchar();

  }

  if (!w) x = -x;

}

template <typename T>

void Write(T x) {

  if (x < 0) {

    putchar('-');

    x = -x;

  }

  if (x > 9) Write(x / 10);

  putchar(x % 10 + '0');

}

//----------------------------------------------

const int N = (1 << 24) + 10;

int n, dp[N], a[N];

int bitlen(int x) {

  int res = 0;

  while (x) ++res, x >>= 1;

  return max(1, res);

}

int main() {

#ifdef dream_maker

  freopen("input.txt", "r", stdin);

#endif

  memset(dp, -1, sizeof(dp));

  Read(n);

  int len = 0;

  fu(i, 1, n) {

    Read(a[i]);

    dp[a[i]] = a[i];

    len = max(len, bitlen(a[i]));

  }

  int up = (1 << len) - 1;

  fu(i, 0, len)

    fu(s, 0, up) if (dp[s] == -1 && ((s >> i) & 1))

      dp[s] = dp[s ^ (1 << i)];

  fu(i, 1, n) Write(dp[up ^ a[i]]), putchar(' ');

  return 0;

}