题目链接

每日吐槽

昨天组长分了个需求，今天再去问组长已经做好了。。。

心路历程

二进制

思路

\(n \oplus x = y \Rightarrow n \oplus x \oplus x \oplus y = y \oplus x \oplus y \Rightarrow n \oplus y = x\)

然后题目是求\(MEX\{ n \oplus x | 0 \le x \le m \}\)，那么就有\(MEX = \min\{ x | n \oplus x > m\}\)。

然后就从高位开始贪心，能填0就填0。

完事。

AC代码

#include <bits/stdc++.h>
using namespace std;
#ifdef BACKLIGHT
#include "debug.h"
#else
#define debug(...)
#endif

const int N = 1e5 + 5;

void solve(int Case) {
  int n, m;
  scanf("%d %d", &n, &m);

  int k = 0;
  /**
   * n ^ x = mex
   * n ^ mex = x
   * 0 <= x <= m
   * k = min{x | n ^ x > m}
   * */
  int mask = 0;
  for (int i = 30; i >= 0; --i) {
    mask += (1 << i);
    if (n & (1 << i))
      ;
    else {
      int ma = (k ^ (n & mask)) + ((1 << i) - 1);
      if (ma > m)
        ;
      else
        k |= (1 << i);
      debug(k, ma, k ^ n, m);
    }
  }
  printf("%d\n", k);
}

int main() {
#ifdef BACKLIGHT
  freopen("a.in", "r", stdin);
#endif
  int T = 1;
  scanf("%d", &T);
  for (int t = 1; t <= T; ++t) solve(t);
  return 0;
}