A1454 无聊的异或

《真无聊（TLE等死）》

题意

输入两个64位正整数a、b，求方程 x+y=a与x xor y的解（x要小）， 无解输出-1。

思路

思路1

写个循环枚举x+y=a，当x xor y=b时输出，结束程序。代码如下：

#include<bits/stdc++.h> 
using namespace std;
int main(){
	int a,b;
	cin>>a>>b;//输入a，b
	int x,y;//答案
	int f=a/2;//因为x<=y，所以枚举一半就可以
	for(int i=0;i<=f;i++){
		int e=i^(a-i); //e=x xor y;
		if(e==b){//如果相等
			x=i;
			y=a-i;
			cout<<x<<" "<<y;//输出
			return 0;//结束程序
		}
	}
	cout<<-1;//没找到输出-1
	return 0;
}

交了就会发现47分，其他超时。为什么呢？ 写一个循环时间复杂度就会来到O(n),n几百亿时当然会超时。 这只能说是基础思路，过不了的。

思路二

观察一下样例输出，会发现y-x=x xor y=b。 所以就是求解方程组 x+y=a与y-x=b了。

所以就有第二份代码：

#include <bits/stdc++.h>
using namespace std;
int main(){
	unsigned long long a,b;//注意unsigned long long，long long 会爆
	cin>>a>>b;
	if(a<b||(a-b)%2){//判断有没有无解的情况
		cout<<-1;
		return 0;//结束程序
	}
	unsigned long long x=(a-b)/2;//解二元一次方程组就行了
	cout<<x<<" "<<a-x<<endl;//输出
    return 0;
}

保证能过

有没有巨学知道为什么x xor y=y-x的？

我证不出来 记得点赞

构式题目去死吧