题意:
给两个数字 u,v 求一个最短的数组 {ai} 使得数组内所有数字异或的结果为u 且和为v
思路:
分情况讨论一下
- 显然v>u的情况下无解输出 -1，再思考一下发现 u 和 v 不具有相同的奇偶性时同样无解
- u==v，输出u即可(特例:u==0时数组长度为0)
- 考虑到 x xor x == 0，可以输出 u xor (v - u)/2 xor (v - u)/2，其中两个(v - u)/2异或相抵消
- 题目要求输出最短的数组，这时可以考虑到如果在二进制位上 u 和 (v - u)/2 没有在同一个位置的 1，有 u xor (v - u)/2 == u + (v - u)/2，则可以把上一条中的前两个数字 u，(v - u)/2 合并，此时答案是长度为 2 的数组 u + (v - u)/2，(v - u)/2
code
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
long long u, v;
cin >> u >> v;
if (u > v || (v - u) & 1) cout << -1 << endl;
else if (u == v) {
if (u == 0) cout << 0 << endl;
else cout << 1 << endl << u << endl;
} else {
long long x = (v - u) >> 1;
if (u + x == (u ^ x)) cout << 2 << endl << u + x << ' ' << x << endl;
else cout << 3 << endl << u << ' ' << x << ' ' << x << endl;
}
return 0;
}
