题目链接
昨天组长分了个需求,今天再去问组长已经做好了。。。
二进制
\(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。
完事。
#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; }