Siyuan

「Codeforces 1148F」Foo Fighters
「Codeforces 1148F」Foo Fighters
扫描右侧二维码阅读全文
03
2019/06

「Codeforces 1148F」Foo Fighters

题目链接:Codeforces 1148F

你有 $n$ 个物品,每个物品有两个属性 $val_i$ 和 $mask_i$。保证最初 $val_i$ 的和非零。

你想要选择一个正整数 $s$ 并将所有物品的 $val_i$ 进行修改,第 $i$ 个物品的 $val_i$ 通过如下方法修改:

  • 将 $mask_i$ 和 $s$ 在二进制下考虑。
  • 计算 $s\ \text{AND}\ mask_i$ 的值。
  • 如果 $s\ \text{AND}\ mask_i$ 的值中有奇数个 $1$,那么将 $val_i$ 替换为 $-val_i$;否则不进行修改。

你需要找到这样一个整数 $s$,使得所有物品 $val_i$ 的和相对最初的和正负号相反(不允许为 $0$)。但是和的绝对值可以是任意的。

数据范围:$1 \le n \le 3 \times 10 ^ 5$,$-10 ^ 9 \le val_i \le 10 ^ 9$,$1 \le mask_i, s < 2 ^ {62}$。


Solution

我们考虑用数学归纳法,归纳得到 $1 \le mask_i, s < 2 ^ K$ 时的答案。

边界条件为 $K = 1$,此时 $s = 1$ 即可。

加入我们已经处理好了 $2 ^ K$ 的答案 $s'$,那么考虑 $\forall 2 ^ K \le val_i < 2 ^ {K + 1}$ 必有 $val_i\ \text{AND}\ 2 ^ K \ne 0$。那么答案的第 $K$ 位为 $1$ 当且仅当:$s = s' + 2 ^ K$ 时,这些 $val_i$ 的贡献和(根据 $mask_i\ \text{AND}\ s$ 的 $1$ 的个数判断贡献的正负)与最初的和正负号相反。

上面说的有点拗口,具体实现详见代码。

吐槽:编译器内置的 __builtin_popcount 竟然不支持 long long,需要使用 __builtin_popcountll

时间复杂度:$\mathcal O(n \log mask_i)$。


Code

#include <cstdio>

const int N = 3e5 + 5;

int n, v[N];
long long s[N];

int main() {
    scanf("%d", &n);
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d%lld", &v[i], &s[i]);
        sum += v[i];
    }
    if (sum < 0) {
        for (int i = 1; i <= n; i++) v[i] *= -1;
    }
    long long ans = 0;
    for (int k = 0; k < 62; k++) {
        long long sum = 0;
        for (int i = 1; i <= n; i++) {
            if ((1LL << k) <= s[i] && s[i] < (1LL << (k + 1))) {
                sum += ((__builtin_popcountll(ans & s[i]) & 1) ? v[i] : -v[i]);
            }
        }
        if (sum < 0) ans |= (1LL << k);
    }
    printf("%lld\n", ans);
    return 0;
}

2 条评论

  1. LMOliver

    题目链接放成 E 题的了 QAQ

    1. Siyuan
      @LMOliver

      修改好了

发表评论