【MX-X16-T2】「DLESS-3」XOR and Multiply 题解

Pig_Eat_Earth · 2025-08-10 18:20:56 · 题解

记号与约定

• 本文中所有的「位」均指二进制位。

思路

在本题中，我们肯定是希望 x' 与 y' 都尽可能大。

~根据幼儿园数学~，比较数的大小要从高位向低位比较，即贪心地，我们希望 x' 与 y' 的高位中 1 尽可能多。

于是考虑从高 (h-1) 位向低 (0) 位枚举，假设枚举到第 i 位，则有以下两种情况：

1. x_i=y_i

   直接置 x'_i=y'_i=1，即置 z_i=\bar{x_i}=\bar{y_i}；

2. x_i\not =y_i

   比较 x' 与 y'，将较小者的第 i 位置为 1。
   :::info[为什么这么做] 由于我们是由高位向低位枚举，在本轮处理中较大者在最终结果中必然较大。

   根据位值原理将每一位拆开，则 x' 与 y' 中的任意一个数在本轮结束后的贡献都可以看作是高 h-i 位的贡献加上第 i 位的贡献。高 h-i 位的贡献固定，考虑第 i 位的贡献。

   :::

答案为 x'y'。

代码

#include <bits/stdc++.h>
#define DN(i, l, r) for(int i = (r); i >= (l); -- i)
using namespace std;
using ll = long long;
int t, x, y, h;
ll xz, yz; // xz:=x', yz:=y'

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while(t --){
        cin >> x >> y >> h;
        xz = yz = 0;
        DN(i, 0, h - 1){
            if((x >> i & 1) == (y >> i & 1)){
                xz |= 1 << i;
                yz |= 1 << i;
            }
            else if(xz > yz) yz |= 1 << i;
            else xz |= 1 << i;
        }
        cout << xz * yz << '\n';
    }
}