Codeforces 1148F Foo Fighters 贪心

2019/06/02 20:31
阅读数 0

题意:给你若干个数对,每个数对有两个属性,一个属性是权值,一个属性是位标志,假设这些数对的的权值和是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);
}

  

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部