题解：CF1554C Mikasa

jms23063 · 2026-04-20 21:49:45 · 题解

感觉是一道很巧妙的题。

首先，由于仅当 m = n 时异或值为 0，所以对于 m < n 的情况，一定无法异或得出 0，故答案为 0。

接下来考虑其他情况，本题题意相当于构造一个自然数 k，使得 k > m 且 k \oplus n 最小。

对于 k，我们明确它在二进制下存在一个 m 为 0 且 k 为 1 的位，并且所有高于它的位 k 与 m 逐位相等，这是 k > m 的硬性条件。

设将 m 为 0 的 i 位赋成 1 ，无论如何对低于 i 位进行操作，都不会影响相对大小关系，所以 k 中低于 i 的位可以与 n 逐位相等，以满足 k \oplus n 最小的最优性条件。

所以问题相当于找出这个位 i 。

首先考虑找出从高到低第一个 m 为 0 且 n 为 1 的位，将此位设置成 1 无疑是最优的。

若遍历后无法找到此位，就从低到高找到第一个 m 为 0 的位，最劣则为在 m 的最高位前再添加一位。

在判断过程中逐位记录答案即可。

code

#include<bits/stdc++.h>
using namespace std;
int T, n, m, a[50], b[50], cnta, cntb;
int main(){
    cin >> T;
    while(T--){
        for(int i = 1; i <= cnta; i++) a[i] = 0;
        for(int i = 1; i <= cntb; i++) b[i] = 0;
        cnta = cntb = 0;
        cin >> n >> m;
        if(m < n){
            cout << "0\n";
            continue;
        }
        while(m){
            a[++cnta] = (m&1);
            m >>= 1;
        }
        while(n){
            b[++cntb] = (n&1);
            n >>= 1;
        }
        int res = 0, v = 0;
        for(int i = cnta; i >= 1; i--){
            res *= 2;
            if(v) continue;
            if(i > cntb) res += a[i];
            else{
                if(a[i] < b[i]) v = 1;
                else res += (a[i] != b[i]);
            }
        }
        if(v){
            cout << res << '\n';
            continue;
        }
        int s = 1;
        res = 0;
        for(int i = 1; i <= cnta+1; i++){
            if(v) res += s*(a[i]!=b[i]);
            else if(!a[i]) v = 1, res += s;
            s = s*2;
        }
        cout << res << '\n';
    }
    return 0;
}