BZOJ3687 简单题

背包+bitset

$n$个数所有子集的和的异或$(n \leq 1000)$
枚举所有子集进行求解复杂度为$2^n$,这是肯定不行的.
背包可以求出任意集合所能组成的数,也就是能够得到该集合的任意子集所组成的数,但是仅仅知道能否组成一个数,无法知道所有的子集中组成了几个这样的数,也无法知道是由哪个子集组成的,当然本题不需要知道是谁组成的,我们只关心组成的数是多少(即和是多少),并且出现的次数的奇偶性。
我们用bitset优化这个背包,这次其第$i$位不再表示$i$是否能由这个集合的若干个数的和组成,而是表示i出现的次数的奇偶性,既是这个集合所有子集组成奇偶次i,最后统计答案即可.
往背包中加入一个数$x$,新加入的部分为 $f<<x$,而原来的部分仍然是 $f$ , f是原集合的一个子集,$f<<x$也是 , 直接异或即可。复杂度$O(n*2e6/32)$

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
int n;
bitset < N > f;
 
int main () {
    int x;
    f.set ( 0 );
    scanf ( "%d" , &n );
    for ( int i = 0 ; i < n ; ++ i ) {
        scanf ( "%d" , &x );
        f ^= f << x;
    }
    int ans = 0;
    for ( int i = 0 ; i <= N - 10 ; ++ i ) if ( f[i] ) ans ^= i;
    printf ( "%d\n" , ans );
    return 0;
}
Last modification:February 5th, 2020 at 09:06 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment