我的题解怎么了
  • 板块灌水区
  • 楼主_Trangle_
  • 当前回复4
  • 已保存回复5
  • 发布时间2024/4/7 16:27
  • 上次更新2024/4/7 19:23:08
查看原帖
我的题解怎么了
768144
_Trangle_楼主2024/4/7 16:27

文章

### solution
显然,当 $C$ 的某位取值为 $1$ 时,$a$ 和 $b$ 的这一位的值相异。

所以它们二进制下 $1$ 的个数的差就是从这里来的。

根据和差问题的解决方法,所以 $X$ 和 $C$ 同取值为 $1$ 的位数为 $\dfrac{a-b+\operatorname{popcount(C)}}{2}$,而 $X$ 和 $Y$ 不与 $C$ 同取值为 $1$ 的位数是 $a$ 减去 $X$ 和 $C$ 同取值为 $1$ 的位数。

根据上面的方法模拟,最后判断是否合法即可。

### code
```cpp
#include <bits/stdc++.h>
#define rep(i, b, e) for (auto i(b); i != (e); i++)
#define req(i, b, e) for (auto i(b); i >= (e); i--)
using namespace std;

int a, b, p, must1a, need1a;
long long X, Y, C;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	cin >> a >> b >> C;
	p = __builtin_popcountll(C);
	must1a = a - b + p >> 1;
	need1a = a - must1a;

	for (long long i = 1; i <= 1ll<<60; i <<= 1) {
		if (C & i) {
			if (must1a) {
				must1a--;
				X |= i;
			}
			else Y |= i; //如果 X 和 C 同取 1 的位数达到要求,那么 Y 要和 C 同取 1
		}
		else if (need1a) {
			need1a--;
			X |= i; Y |= i;
		}
	}

	if (__builtin_popcountll(X) == a && __builtin_popcountll(Y) == b && X ^ Y == C) cout << X << ' ' << Y;
	else cout << -1;

	return 0;
}

这篇题解既没多空格也没少空格,为什么打回理由是 LaTeX 公式/英文与汉字之间少空格?。

2024/4/7 16:27
加载中...