「BZOJ 3687」简单题 - 位运算

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

HydroOJ 链接

求一个有 \(n\) 的元素的可重数集 \(\{a_i\}\) 的子集的算术和的异或和。

数据范围：\(a_i > 0\)，\(1 < n < 1000\)，\(\sum a_i \le 2000000\)。

解题思路

本题有一种位运算的妙解。

首先对于 \(\sum a_i \le 2000000\)，我们可以直接开一个大小为 \(2000000\) 的 bitset 来存储算术和的情况。

定义 \(f_i\) 表示算术和 \(i\) 是否对答案有效。由于最终为异或和，当 \(i\) 出现次数为偶数时，我们就可忽略 \(i\)，即 \(f_i = \text{false}\)。

每对于一个新增的数 \(a\)，我们有两种情况：

  • 算术和没有 \(a\)，则 \(f\) 保持原样。
  • 算数和有 \(a\)，则对于 \(f\) 中所有为 true 的情况加上 a。反应在 bitset 上为 f << a。

将两者异或就可得出 f 中的反映到 a 的所有算术和情况。最后将 f 中所有为 true 的情况求异或和即可。

代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <cstdio>
#include <bitset>

const int MAXN = 1000;
const int MAXS = 2000000;

int main() {
    int n;

    scanf("%d", &n);

    int sum = 0;
    static std::bitset<MAXS + 1> f;
    f[0] = 1;

    for (int i = 0; i < n; i++) {
        int a;
        scanf("%d", &a);
        sum += a;
        f ^= (f << a);
    }

    int ans = 0;
    for (int i = 1; i <= sum; i++) {
        if (f[i]) {
            ans ^= i;
        }
    }

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

    return 0;
}