CF1554C-Mikasa

2022-04-11 题解

题目大意：定义一个函数MEX(x[])，返回值为未出现在x[]中的最小整数。给出两个整数n和m，求MEX(n^0,n^1,n^2...n^m)（这里的^指按位异或）。

题目要找的答案x满足

\forall i \leq m( n \oplus i \neq x)

感性分析一下可以知道，如果 $a \oplus b=c$ ，那么 $a \oplus c = b$ 。那么上式其实可改写为

n \oplus x \geq m + 1

若要使x最小，可从高位到低位确定x的值，使得高位尽可能为0。具体看代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long n, m, x, t;
    int _;
    scanf("%d", &_);
    while (_--)
    {
        scanf("%lld%lld", &n, &m);
        m++;
        for (t = 33, x = 0; t >= 0 && n < m; t--)
        {
            if ((n >> t) ^ (m >> t))
            {
                if ((m >> t) & 1)
                    x |= (long long)1 << t, n |= (long long)1 << t;
            }
        }
        printf("%lld\n", x);
    }
    return 0;
}