本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-31 09:37:49

解决

题意

您将得到非负整数 $a$ 、 $b$ 和 $C$ 。

确定是否有一对非负整数 $(X, Y)$ 满足以下所有五个条件。如果存在这样的对，则打印一个。

• $0 \le X \lt 2^{60}$

• $0 \leq Y \lt 2^{60}$

• $\operatorname{popcount}(X) = a$

• $\operatorname{popcount}(Y) = b$

• $X \oplus Y = C$

思路

首先要满足 $X \oplus Y = C$ 我们需要在把 $C$ 转化成二进制后的所有位在 $X$ 和 $Y$ 中出现仅一次。那么 $X$ 和 $Y$ 的其余的位 只需要根据 $a$ 和 $b$ 的大小都选或者都不选即可。

细节

• 判断当 $a$ 和 $b$ 的位数减去构成 $C$ 要用的位数后如果是奇数个，那么说明之后不能通过选取同一个位数相互抵消。

• 判断 $a$ 和 $b$ 能否用完，用不完也是不行的。

• 开 long long

• $a$ 和 $b$ 要均衡使用（尽量使 $a$ 和 $b$ 相等）

代码

#include<bits\/stdc++.h>
#define ll long long
#define int long long
#define int_128 __int128
#define lowbit(x) (x&(-x))
using namespace std;
int a,b,c;
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>a>>b>>c;
	int cnt=0;
	int x=c;
	while(x) {
		x-=lowbit(x);
		cnt++;
	}
	if(a+b<cnt || (a+b-cnt)%2==1) {
		cout<<-1;
	}
	else {
		int ans=0,anss=0;
		for(int i=0;i<=60;i++){
			if(c&(1ll<<i)){
				if(a>=b){
					ans|=(1ll<<i);
					a--;
				}
				else {
					anss|=(1ll<<i);
					b--;
				}
			}
		}
		for(int i=0;i<=60;i++){
			if((c&(1ll<<i)) == 0){
				if(a&&b){
					a--;
					b--;
					ans|=(1ll<<i);
					anss|=(1ll<<i);
				}
				else {
					break;
				}
			}
		}
		if(a||b){
			cout<<-1;
		}
		else cout<<ans<<" "<<anss<<"\n";
	}
	return 0;
}