1554C. Mikasa 按位枚举求最小值

题意

给正整数 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)
1554C. Mikasa 按位枚举求最小值
由于 n ⨁ k > = p n \bigoplus k>=p n⨁k>=p,因此第一位的n异或k我们必须为1

1554C. Mikasa 按位枚举求最小值

所以我们此时的k必须为0
1554C. Mikasa 按位枚举求最小值

同理,第二位的n异或k,必须为1,k也必须为1
1554C. Mikasa 按位枚举求最小值
第三位的时候,n异或k为1和为0都能满足公式,但是为了让我们的k尽可能小,因此我们选择n异或k为1,k=0,让我们的k尽可能地小。

1554C. Mikasa 按位枚举求最小值
第四位的时候也同理
1554C. Mikasa 按位枚举求最小值
所以我们就能根据从高位到低位的按位枚举从而求出k的最小值。
很典中典了。

但是当我们处在下面阶段的时候就没必要比较了,因为 n ⨁ k > = p n \bigoplus k>=p n⨁k>=p已经永远成立,因此k的后面的位数所有取0就是最小的。
1554C. Mikasa 按位枚举求最小值

代码

#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();
    }
}
上一篇:位运算的一些性质


下一篇:关于状压DP枚举子集的方法与理解