题解 [email protected]洛谷 | [email protected] 【Foo Fighters】

有点毒瘤的贪心题,当然也可能是我太菜了。


翻译的挺清楚的了,直接说思路:

我们考虑在读入时顺便把每个数的 maskmask 权值的二进制最高位预处理出来,同时统计权值和。由于正数变负数和负数变正数本质上是一样的,为了方便考虑,如果 valval 权值和为负数,将所有 valval 取相反数。

随后考虑如何贪心:

枚举每一位,统计二进制最高位为该位的所有数的 valval 权值和。如果这个权值和小于或等于零,那么没有修改该位的必要,因为修改不会使总权值增加,反而可能减少。如果最高位为该位的权值和大于零,那么修改该位比不修改更优。在答案变量中将该位置为 11,并且枚举所有数修改即可。

以上为正解,复杂度 O(nlogx)O(n\log{x})xx 为变量范围(26212^{62}-1)。

坑点:贪心时必须从低位到高位枚举每一位进行更新,否则后面的更改可能导致更高位的决策被干扰,得不到正确答案!


代码:

//By: [email protected]_er(122461)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 3e5+5, bit = 62;

ll n, ans;
struct Node {ll val, mask, bits;}a[N];

int main() {
	scanf("%llu", &n);
	for(ll i=1;i<=n;i++) {
		scanf("%lld%lld", &a[i].val, &a[i].mask);
		ans += a[i].val;
		for(ll _=bit;_+1;_--) if((a[i].mask >> _) & 1) {a[i].bits = _; break;}
	}
	if(ans < 0) for(ll i=1;i<=n;i++) a[i].val = -a[i].val;
	ans = 0;
	for(ll _=0;_<=bit;_++) {
		ll s = 0;
		for(ll i=1;i<=n;i++) s += (a[i].bits == _) * a[i].val;
		if(s <= 0) continue;
		ans |= (1LL << _);
		for(ll i=1;i<=n;i++) a[i].val *= ((a[i].mask >> _) & 1) ? -1 : 1;
	}
	printf("%lld\n", ans);
//	puts("----------\nDEBUG: "); for(ll i=1;i<=n;i++) printf("%lld\n", a[i].val);
	return 0;
}