CF1148F - Foo Fighters

CF1148F - Foo Fighters

题意：你有n个物品，每个都有val和mask。

你要选择一个数s，如果一个物品的mask & s含有奇数个1，就把val变成-val。

求一个s使得val总和变号。

解：分步来做。发现那个奇数个1可以变成：每一个1就变一次。

然后把这些物品按照最高位1来分类。从0到61考虑每一类。

我们试图使每一类都与sum异号，这样总和也异号了。

具体来说就是看看这一类的总和，如果同号就把这以一位变成1。

#include <bits/stdc++.h>

typedef long long LL;
const int N = 300010;

struct Node {
    LL mask, val;
    int id, cnt;
    inline bool operator < (const Node &w) {
        return mask < w.mask;
    }
}node[N];

int main() {
    
    int n;
    LL sum = 0;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%lld%lld", &node[i].val, &node[i].mask);
        sum += node[i].val;
        for(int j = 0; j <= 61; j++) {
            if((node[i].mask >> j) & 1) {
                node[i].id = j;
            }
        }
    }
    if(sum < 0) {
        for(int i = 1; i <= n; i++) {
            node[i].val *= -1;
        }
    }
    LL ans = 0;
    for(int i = 0; i <= 61; i++) {
        LL t = 0;
        for(int j = 1; j <= n; j++) {
            if(node[j].id != i) {
                continue;
            }
            t += node[j].val;
        }
        if(t > 0) {
            ans |= (1ll << i);
            for(int j = 1; j <= n; j++) {
                if((node[j].mask >> i) & 1) {
                    node[j].val *= -1;
                }
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}