cf_628_div2

题目链接
D

Codeforces Round #628 (Div.2)

D,思路：构造公式
构造前，先了解几个异或的小知识。

1) 交换律: a ^ b = b ^ a
2) 结合律: a ^ b ^ c = a ^ (b ^ c) = (a^b) ^c
可以知道一个结论 d = a ^ b ^ c –> a = b ^ c ^ d
3) 自反性: a ^ b ^ a =b ; a ^ b ^ b = a;

题意 ：有u , v ；求一最短数组，使得数组元素之和为v,数组元素异或为u;
若不存在，则输出-1

题解开始了，易知 a + b = a ^ b + 2(a&b) 这个构造还是不太会啊
令 x = a&b，a+b=v ,a^b=u;则x = (u-v)/2;则[u,x,x]必是其中一组解；现在考虑有没有，比3长度更短的数组，考虑特殊情况，当u>v时，无解，因为等式不成立，当u == v时长度为1，解为u，其它情况，判断[u+x,x]，是否符合条件，则必须满足(u+x+x) = (u+x)&x + (u+x) ^ x –> (u+x+x) = u ^ x + x + u&x –> (u+x) = u ^ x + u&x 并且得满足 (u+x) = u ^ x + 2(u&x) 所以 u&x 必须为0 才存在数组长度为二，此时解为[u+x,x]；

代码：

#include<bits/stdc++.h>
#define sc(x) scanf("%lld",&x);
#define pf printf
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define dep(i,e,s) for(int i=e;i>=s;i--)
using namespace std;
#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef long long ll;
ll u,v,x;
int main()
{
	SIS;
	//¼ÓËÙcin/cout
	cin>>u>>v;
	if(u>v || u%2!=v%2){
		pf("-1\n");
		return 0;
	}else if(u==v){
		if(!u)
			pf("0");
		else
			pf("1 %d\n",u);
		return 0;
	}
	x=(v-u)/2;
	if(u&x)
		pf("3\n%lld %lld %lld",u,x,x);
	else
		pf("2\n%lld %lld",(u^x),x);
	return 0;
}