BZOJ 3687: 简单题(dp+bitset)

传送门

解题思路

　　设\(f(i)\)表示和为\(i\)时的方案数，那么转移方程为\(f(i)+=f(i-x)\)，\(x\)为当前枚举到的数字，这样做是\(O(n\sum a_i)\)的，考虑优化。发现最后要的并不是方案数，最后的奇偶性，那么转移方程转化为\(f(i)^=f(i-x)\)，这样可以用\(bitset\)优化，时间复杂度\(O(\frac{n \sum a_i}{32})\)。

代码

#include<iostream>
#include<cstdio>
#include<bitset>

using namespace std;
const int N=2000005;

int n,sum,ans;
bitset<N> f;

int main(){
    scanf("%d",&n); int x;
    f[0]=1;
    for(int i=1;i<=n;i++) {
        scanf("%d",&x); sum+=x;
        f=(f^(f<<x));
    }
    for(int i=1;i<=sum;i++)
        if(f[i]) ans^=i;
    printf("%d\n",ans);
    return 0;   
}

BZOJ 3687: 简单题(dp+bitset)

原文：https://www.cnblogs.com/sdfzsyq/p/10367222.html