Codeforces Round #628 (Div. 2) D. Ehab the Xorcist 题解（思维+位运算）

桃扇骨 2023-05-28 15:53 11阅读 0赞

> 原题链接：[https://codeforces.com/contest/1325/problem/D][https_codeforces.com_contest_1325_problem_D]

Given 2 integers u and v, find the shortest array such that bitwise-xor of its elements is u, and the sum of its elements is v.

**Input**  
The only line contains 2 integers u and v  ( 0 ≤ u , v ≤ 1 0 18 ) . (0≤u,v≤10^\{18\}). (0≤u,v≤1018).

**Output**  
If there’s no array that satisfies the condition, print “-1”. Otherwise:

The first line should contain one integer, n, representing the length of the desired array. The next line should contain n positive integers, the array itself. If there are multiple possible answers, print any.

**input**

2 4

**output**

2
    3 1

**input**

1 3

**output**

3
    1 1 1

**input**

8 5

**output**

-1

**input**

0 0

**output**

**Note**  
In the first sample, 3 ⊕ 1 = 2 and 3 + 1 = 4. There is no valid array of smaller length.

Notice that in the fourth sample the array is empty.

**题意：** 给出 u, v，求出一个长度最短的数组，其各元素的异或和等于 u，和等于 v 。

**思路：** 要分类讨论。

1.  首先要知道，答案数组所有元素必须小于 v，除非数组只有一个元素，因为数组各元素的和要等于 v。如果 u > v，那么 u 的高位为 1 而小于 v 的任何数异或和都不会等于 u 。
2.  如果 u == v，且 u、v 都不为 0 ，那么答案数组元素只有一个，即 u (v) 。
3.  如果 u == v，且 u、v 都为 0 ，那么只能是空数组。
4.  其他的情况就得来构造了。因为两个相同的数异或和等于 0 ，所以有 u ^ x ^ x = u ^ 0 = u，又因为要使得 u+x+x = v，所以可以使得 x = (v - u) / 2 。
5.  所以通过上一点可以知道，如果 v - u 是奇数也无解。
6.  又因为要使得数组最短，所以上面的情况构造的数组长度为 3 ，那么我们可以把 u 和 一个 x 合并，就变成了，u+x 和 x，也就是 (v+u) / 2 和 (v-u) / 2，然后判断一下是否符合条件。不符合就输出长度为 3 的数组。
7.  综上所述，先把特判解决了，然后只要有解，就至少有长度为 3 的数组，然后再判断合并为长度为 2 是否符合条件。
8.  要注意位运算的优先级比较低，所以尽量都加个括号，不然容易出错。

> 参考博客：[https://blog.csdn.net/JiangHxin/article/details/104875015][https_blog.csdn.net_JiangHxin_article_details_104875015]

**Code：**

#include <iostream>
    using namespace std;
    typedef long long ll;
    int main(){ 
        ll u,v;    cin>>u>>v;
        if(u>v || ((v-u)&1))
            cout<<-1<<endl;
        else if(u==v){ 
            if(!u)  cout<<0<<endl;
            else    cout<<1<<endl<<u<<endl;
        }
        else{ 
            ll x = (v-u)/2;
            if(((u+x)^x)==u && u+x+x==v)  cout<<2<<endl<<u+x<<' '<<x<<endl;
            else    cout<<3<<endl<<u<<' '<<x<<' '<<x<<endl;
        }
        return 0;
    }

[https_codeforces.com_contest_1325_problem_D]: https://codeforces.com/contest/1325/problem/D
[https_blog.csdn.net_JiangHxin_article_details_104875015]: https://blog.csdn.net/JiangHxin/article/details/104875015