题意
给正整数 n , m n,m n,m,构造出 0 ⨁ n , 1 ⨁ n . . . . m ⨁ n 0\bigoplus n,1\bigoplus n....m\bigoplus n 0⨁n,1⨁n....m⨁n,求此序列中未出现的最小数字。
解析
出现未出现的最小数字字眼,只要代换进公式即可,假设 k k k是出现过的数字, 设 0 < = x < = m 0<=x<=m 0<=x<=m。
x
⨁
n
=
k
x \bigoplus n =k
x⨁n=k
根据交换律
n
⨁
k
=
x
<
=
m
n \bigoplus k =x <=m
n⨁k=x<=m
也就是说,如果你出现过,你就会满足这个条件,因此我们加以转换
当
n
⨁
k
>
=
m
+
1
,
k
n \bigoplus k >= m+1,k
n⨁k>=m+1,k 的最小值就满足题意。
因此这个问题就转化成
n
⨁
k
>
=
m
+
1
=
p
n \bigoplus k>=m+1=p
n⨁k>=m+1=p
已知
n
,
p
n,p
n,p求
k
k
k的最小值
这个问题就实属典中点问题了。
我们画个图来解释,假设
n
=
1010
(
2
)
,
p
=
1101
(
2
)
n=1010(2),p=1101(2)
n=1010(2),p=1101(2)
由于
n
⨁
k
>
=
p
n \bigoplus k>=p
n⨁k>=p,因此第一位的n异或k我们必须为1
所以我们此时的k必须为0
同理,第二位的n异或k,必须为1,k也必须为1
第三位的时候,n异或k为1和为0都能满足公式,但是为了让我们的k尽可能小,因此我们选择n异或k为1,k=0,让我们的k尽可能地小。
第四位的时候也同理
所以我们就能根据从高位到低位的按位枚举从而求出k的最小值。
很典中典了。
但是当我们处在下面阶段的时候就没必要比较了,因为
n
⨁
k
>
=
p
n \bigoplus k>=p
n⨁k>=p已经永远成立,因此k的后面的位数所有取0就是最小的。
代码
#include<bits/stdc++.h>
using namespace std;
void solve(){
int n,m;
cin>>n>>m;
int p=m+1,k=0;
for(int i=30;i>=0;i--){
int a=(n>>i)&1,b=(p>>i)&1;
if(a!=b){
if(b){//
n|=(1<<i);//把答案存进n里面。
k|=(1<<i);
}
}
if(n>=p)break;//满足了条件了,我们就没必要再比较了
}
cout<<k<<endl;
}
int main(){
int t;
cin>>t;
while(t--){
solve();
}
}