BZOJ 3687 简单题

bitset维护某个和是否存在。

bit<<x：所有子集的和+x。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#define maxn 2000050
using namespace std;
bitset <maxn> bit;
int n,x,ans=0,sum=0;
int main()
{
    scanf("%d",&n);bit[0]=1;
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        sum+=x;bit^=(bit<<x);
    }
    for (int i=1;i<=sum;i++)
        if (bit[i]) ans^=i;
    printf("%d
",ans);
    return 0;
}