1325 D. Ehab the Xorcist

题意:

给两个数字 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;
}