题解『CF1554 C』

_Fontainebleau_ · 2021-07-30 11:28:13 · 题解

题意

• 给定两个整数 n,m。求序列 n \oplus 0,n\oplus 1,n\oplus 2,n \oplus 3, \cdots,n\oplus m 的 \operatorname{mex}。

• 多测 。

分析

设最终答案为 k,由异或的性质可知：n \oplus k > m。

令 p=m+1，即求最小的 k，使 n\oplus k \ge p。

我们一位一位考虑。 令 x_i 表示 x 在二进制下的第 i 位。

则共有四种情况。

• case 1： n_i=p_i=1，此时 k_i=0。
• case 2： n_i=p_i=0，此时 k_i=0 即可，因为要满足 \operatorname{mex} 的条件。
• case 3： n_i=0,p_i=1，此时 k_i=1。
• case 4： n_i=1,p_i=0，此时 k_i=0，注意此时 n \oplus k 一定大于 p，所以我们可以直接 break 掉。

代码

#include<bits/stdc++.h>
using namespace std;
int tc,n,p;
long long ans;
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int main()
{
    tc=read();
    while(tc--)
    {
        n=read(),p=read()+1;
        ans=0;
        for(int i=30;i>=0;i--)
        {
            if((n>>i &1)==1&&(p>>i &1)==0)  break;
            if((n>>i &1)==0&&(p>>i &1)==1)  ans|=1<<i;
        }
        printf("%lld\n",ans);   
    }

    return 0;
}