【bzoj3687】【简单题】bitset

[pixiv] https://www.pixiv.net/member_illust.php?mode=medium&illust_id=64333782

这次的图是自己画的，方便的话点个赞咯(^-^)

我们希望有一个数组a[]，记录每一个数的出现个数，奇数个会对答案做出贡献，偶数个则没有贡献，所以只需要1表示奇数，0表示偶数

每次新加入一个数x时，我们要对每一个a[]里有的数加x，就相当于全部右移x位（左小右大），意为新增的数们，与原a[]亦或，就可以更新每个数的奇偶了

暴力做又麻烦又要挂，考虑用bitset优化常数

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<bitset>

using namespace std;

const int N=1000+5;

const int A=2000000+5;

bitset<A> a;

int n,x;

int main(){

    scanf("%d",&n);

    a[0]=1;

    for(int j=1;j<=n;j++){

        scanf("%d",&x);

        a=a^(a<<x);

    }

    int ans=0;

    for(int i=1;i<=A;i++){

        if(a[i]) ans^=i;

    }

    printf("%d",ans);

    return 0;

}

总结：

1、学会灵活运用位运算，将普通bool数组用二进制数来表示，就可以进行很多灵活的操作

2、bitset在写暴力的时候说不定能卡过去