题解：P13684 【MX-X16-T2】「DLESS-3」XOR and Multiply
Link
题目思路
异或运算：对于 \(x \oplus y\)，若 \(x\) 和 \(y\) 的第 \(i\) 位相同，则返回 \(0\)，否则返回 \(1\)。
构造 \((x \oplus z)\) 和 \((y \oplus z)\) 的最大乘积。
令 \(a=x \oplus z\)，\(b=y \oplus z\)，\(f=x \oplus y\)，现在我们尽可能的增大 \(a \cdot b\) 即可。
我们可以从最高位逐位构造。提取每位 \(i\) 的值，将 \(i\) 与 \(f\) 进行按位与运算。若 \(i \mid f=1\)，则 \(x\) 与 \(y\) 在这个数位上不同。这里要记录最高位的 \(x\) 与 \(y\) 不同的数位的位置。因为数位越高权值越大，所以这里我们最大化 \(a\) 的贡献，即令 \(a\) 在这个地方位 \(1\)，\(b\) 为 \(0\)。对应的，在其他的 \(b\) 的数位上令其为 \(1\) 来增大 \(b\) 的值。
若 \(i \mid f=0\)，显然此时 \(x\) 与 \(y\) 在这个数位上相同。这时令其为 \(1\) 即可最大化贡献。
代码实现
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T,x,y,h;
ll read() {int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}return s*w;
}
int main() {T=read();while (T--){x=read(),y=read(),h=read();ll f=x^y;ll a=0,b=0;bool flag=false;for(int i=h-1;i>=0;i--){ll m=1LL<<i;if(f&m){if(!flag) a|=m,flag=true;else b|=m;}else a|=m,b|=m;}cout<<a*b<<"\n";}return 0;
}时间复杂度 \(O(T \cdot h)\)。