bitset刷题记录

大佬的bitset用法小结 https://www.cnblogs.com/zwfymqz/p/8696631.html

 

BZOJ3687简单题

题意:求子集的算术和的异或和,子集大小为n(n<=1000),所有数和sum<=2000000

  • 求子集和可以用01背包的那个动规,f[i]表示有多少个子集和为i 。时间复杂度O(n*sum)
  • 但是只求异或和就只表示奇偶性,所以bit[i]表示和为i的子集个数的奇偶性。
  • 时间复杂度降为O(n*sum/机器字长)
  • 代码: bitset刷题记录
     1 #include <bits/stdc++.h>
     2 #define nmax 10010
     3 #define f(a,b) for(int i=a; i<=b; i++)
     4 
     5 using namespace std;
     6 typedef long long ll;
     7 
     8 int main(){
     9     bitset<2000000> bit;
    10     bit[0] = 1;
    11     int n, x;
    12     int ans = 0;
    13     cin >> n;
    14     f(1, n) {
    15         scanf("%d", &x);
    16         bit ^= (bit << x);
    17     }
    18     f(1,2000000) if(bit[i]) ans^=i;
    19     cout << ans << endl;
    20     return 0;
    21 }
    (╹ڡ╹ )

     

上一篇:小清新人渣的本愿(莫队,bitset)


下一篇:Java手动实现布隆过滤器(BitSet)