Codeforces Round #628 (Div. 2)

谁借莪１个温暖的怀抱￠ 2023-07-15 04:57 7阅读 0赞

**D. Ehab the Xorcist**  
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≤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.  
Examples  
inputCopy  
2 4  
outputCopy  
2  
3 1  
inputCopy  
1 3  
outputCopy  
3  
1 1 1  
inputCopy  
8 5  
outputCopy  
\-1  
inputCopy  
0 0  
outputCopy  
0  
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。

bitwise-xor 按位异或 
    ⊕  		按位异或和符号

搞清楚这些就可以开始愉快(痛苦)的a题了

*  根据异或运算（1^1=0 ,00=0,10=1）的规则可以得出n个数异或运算的结果一定会小于等于n个数的和  
    所以得出如果u>v就无解
 *  还有一种无解的情况就是u和v的奇偶性不同。如果异或和u是一个奇数，那么数组里面奇数的个数也是奇数个的(奇数个奇数的异或结果最低为一定是1，即奇数)，而奇数与奇数相加(偶数的个数随便多少个，因为偶数与偶数之和一定是偶数，偶数异或和最低位也一定是0)结果一定是奇数。u和v都是偶数（理由同上推导）
 *  先判断u=v的情况，如果u=v=0输出0（样例），u=v！=0，结果就是u
 *  最简单的一个答案就是数组个数为3，数组值分别为 u、(v-u)/2、（v-u）/2  
    因为(v-u)/2 ⊕（v-u）/2=0
 *  因为要求最短，所以要判断一下数组个数为2满不满足条件，即把前两个合并一下

#include<cstdio>
    #include<iostream>
    #include<cstring>
    using namespace std;
    int main()
    { 
        long long int u,v; 
        while(cin>>u>>v)
        { 
        	if(u%2==v%2&&u<=v)//奇偶性判断以及u<=v 
        	{ 
        		if(u==v)
        		{ 
        			if(u==v&&u==0)printf("0\n");
        			else printf("1\n%lld\n",u);
    			}
    			else 
    			{ 
    				long long int w=(v-u)/2;
    				long long int sum=u+w;//合并u和（v-u）/2 
    				if((sum^w)==u&&sum+w==v)printf("2\n%lld %lld\n",w,sum);//(sum^w)这个括号不难少 
    				else 
    				{ 
    					printf("3\n%lld %lld %lld\n",u,w,w);
    				}
    			}
    		}
    		else
    		printf("-1\n"); 
    	}
        return 0;
    }