BZOJ3687 简单题 dp+bitset

xiaoxiao2021-02-28  11

给出n个数,求所有子集和的异或和。n<=2e6.

正常情况下就是一个01背包,但是范围过大会TLE

于是用bitset优化一下这个bool dp

bitset的第i位表示和为i出现次数的奇偶性

这个东西可以像位运算一样操作,比较方便但是好像用的不多。。

#include<bits/stdc++.h> #define LL long long #define clr(x,i) memset(x,i,sizeof(x)) using namespace std; const int N=2000005; bitset<N> a; int n; int main() { scanf("%d",&n); int x,sum=0,ans=0; for(int i=1;i<=n;i++) { scanf("%d",&x); a^=(a<<x);a[x]?a[x]=0:a[x]=1;sum+=x; //for(int i=0;i<=sum;i++)printf("%d ",a[i]?1:0);puts(""); } for(int i=1;i<=sum;i++) if(a[i])ans^=i; printf("%d",ans); return 0; }

转载请注明原文地址: https://www.6miu.com/read-1400243.html

最新回复(0)