题解 CF1554C【Mikasa】

Blunt_Feeling · 2021-07-31 11:20:22 · 题解

CF1554C Mikasa 题解

题意是让我们找出最小的一个自然数 k，满足 k\notin \{n\oplus 0,n\oplus 1,\ldots,n\oplus m\}。这里的 n 和 m 都是 10^9 级别，我们只能通过位来构造，用 \log 的时间复杂度来过这道题。

由于不可能一个一个枚举，所以这道题要用到异或的一些性质。设 i\in \{0,1,\ldots ,m \}，与其让 n 去一个一个异或 i，不如构造一个答案，让这个答案不属于这个集合。

根据这个性质，为了使 n\oplus i \ne k，其实只要构造出一个 k，使得 n\oplus k \notin \{0,1,\ldots ,m \}，也就是 n\oplus k \ge m+1，接下来就是按位进行构造了。

从高位到低位一位一位构造，对于第 i 位，我们可以分四种情况讨论：

Code

#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
using namespace std;
int T,n,m,k;
int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        bool flag=false;
        k=0; m++; //别忘了++
        Rep(i,31,0)
        {
            if(!flag&&(n&(1<<i)||m&(1<<i))) flag=true; //标记表示遍历到了有效位
            if(!flag) continue;
            if(n&(1<<i))
            {
                if(m&(1<<i)) k<<=1; //左移一位表示后面添上一个0
                else
                {
                    Rep(j,i,0) k<<=1; //后面几位都是0
                    break; //可以输出了
                }
            }
            else
            {
                if(m&(1<<i)) k=(k<<1)|1; //先左移，再或一下，表示后面添上一个1
                else k<<=1; //左移一位表示后面添上一个0
            }
        }
        cout<<k<<endl;
    }
    return 0;
}

记得点赞哦~