Codeforces 1148F Foo Fighters 贪心

题意：给你若干个数对，每个数对有两个属性，一个属性是权值，一个属性是位标志，假设这些数对的的权值和是sum,你可以选择一个二进制数s，与所有的数对的位标志按位与，如果按位与之后的位标志有奇数个1，那么权值的符号就会翻转（正变负，负变正），现在需要找到一个数s，使得进行这样的操作后sum的符号变了。

思路：从高位向低位枚举，判断这一位需不需要选择。把当前位是最低位的所有的数对的权值加起来，如果大于0，那么这位置1后权值就会减小，然后把所有这位为1的数对的权值翻转。

代码：

#include <bits/stdc++.h>

#define LL long long

using namespace std;

const int maxn = 300010;

LL a[maxn], b[maxn];

int main() {

	int n;

	LL sum = 0;

	scanf("%d", &n);

	for (int i = 1; i <= n; i++) {

		scanf("%lld%lld", &a[i], &b[i]);

		sum += a[i];

	}

	if(sum < 0) {

		for (int i = 1; i <= n; i++)

			a[i] = -a[i];

	}

	LL ans = 0;

	for (int j = 61; j >= 0; j--) {

		LL s = 0;

		for (int i = 1; i <= n; i++) {

			if(b[i] == (1ll << j)) s += a[i];

		}

		if(s > 0) ans |= (1ll << j);

		for (int i = 1; i <= n; i++) {

			if((b[i] >> j) & 1) {

				b[i] ^= (1ll << j);

				if(s > 0) a[i] = -a[i];

			}

		}

	}

	printf("%lld\n", ans);

}

巴特西

Codeforces 1148F Foo Fighters 贪心

最新文章

热门文章