CF165E Compatible Numbers 题解

Mooncrying · 2023-05-09 22:04:25 · 题解

CF165E Compatible Numbers 题解 && 高维前缀和

这是一篇对新手比较友好的题解。

题目大意

给出一个 a 数列，对于数列中的每一个数 a_i，找到并输出数列中与之相容的数 a_j（即 a_i \& a_j = 0），无解输出 -1。

题意分析

• 我们首先会想，每个 a_i 所对应的解集是什么。

  其实很好想，对该数取反（把该数二进制表示下的每一位的 0 变成 1，1 变成 0），取反之后的结果一定满足与该数相容。

  然后我们不难发现，取反之后的数在二进制表示下，任何一位或几位的 1 变成 0，所得出的数仍满足与原数相容。

  举个栗子：

  一个数为 (010010101) _ {2}，该数取反后变为 (101101010) _ {2}，我们易证得这两个数相容。同样地，易证出 (101101000) _ {2}，(001101010) _ {2}，(100001010) _ {2} 等数都与原数相容（可以在草稿纸上写写）。

• 怎样求解出任意的一个解呢？

  这里我们可以用一个类似维护高维前缀和的东西来维护其中的一个解。

  关于高维前缀和，以下是我的一些见解，建议不懂的同学先看一看。

• 我们已知高维前缀和的求解代码为：

  for(int i = 0; i < t; ++ i)
      for(int j = 0;j < n; ++ j) 
          if( (1 << i) & j) sum[j] += sum[j ^ (1 << i)];

  而这道题让我们求的是任意一个解，那我们可以用赋值刷新解的方法存下任意的一个解。

  代码这样写：

  memset(ans, -1, sizeof(ans) );
  for(int i = 1; i <= n; ++ i)
       read(a[i]), ans[a[i]] = a[i];//基本的赋值
  
  for(int i = 0; i < 22; ++ i)
      for(int j = 0; j < (1 << 22); ++ j)
          if(j & (1 << i) && ans[j ^ (1 << i)] != -1) ans[j] = ans[j ^ (1 << i)];//存在就覆盖

  这样我们就求出了取值范围内所有数的任一解（当然无解还是 -1）。

• 接下来的事情就简单了，我们只需要对每一个 a_i 进行取反，然后判断取反之后的数所对应的 ans 数组是否有实际数字（即是否不为 -1）即可。

  这里我们要注意在有符号整数类型中对一个数进行二进制取反时所得的数一定不是正确的取反结果（机房大佬说我看不起读者的知识水平 QaQ），因为题目给定的取值范围是大约 2 ^ {22} 的规模，于是我们可以 a_i \oplus (2 ^ {22} - 1) （二进制表示下就是 22 个 1）（就是异或操作），这样的结果相当于对该数取反。

• 于是写出代码后，我们就能愉快地切掉这道大水题啦。

  下面是你们最喜欢的代码：

  #include<bits/stdc++.h>
  using namespace std;
  const int N = 1e6 + 10;
  const int M = (1 << 22) + 10;
  int n, a[N], ans[M];
  template <typename T> void read(T &x)
  {
      int f = 1; x = 0; char ch = getchar();
      while(ch > '9' || ch < '0') {if(ch == '-') f = -1;ch = getchar(); }
      while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
      x *= f;
  }
  template <typename T> void write(T x, char ch)
  {
      if(x < 0) putchar('-'), x = -x;
      if(x > 9) write(x / 10, 0);
      putchar(x % 10 + '0');
      if(ch == ' ') putchar(' ');
      if(ch == '\n') putchar('\n');
  }
  int main()
  {
      read(n);
      memset(ans, -1, sizeof(ans) );
      for(int i = 1; i <= n; ++ i)
           read(a[i]), ans[a[i]] = a[i];
      for(int i = 0; i < 22; ++ i)
          for(int j = 0; j < (1 << 22); ++ j)
              if(j & (1 << i) && ans[j ^ (1 << i)] != -1) ans[j] = ans[j ^ (1 << i)];
      for(int i = 1; i <= n; ++ i)
          write(ans[a[i] ^ ( (1 << 22) - 1)], ' ');
      return 0;//完结撒花
  }