[BZOJ3687][簡單題][Bitset]

題目一上來四個問題直接吓死我。。。

然後發現隻用做第四個問題。。。

思路：

由于最終答案求的是異或和，一個數異或另一個數兩遍還是這個數本身，是以每一個數隻有0/1兩種狀态，就可以開一個長度為最大數的Bitset，每一位代表這一位下标代表的數字是否存在。

那麼加入一個數K，就把這個Bitset整體左移K位就好了。

至于Bitset是什麼，感性的了解為一個超長的二進制就好了，可以進行二進制的任何操作。

然而這道題讀入優化會RE是什麼鬼……

代碼：

#include <bits/stdc++.h>
const int Maxn = ;
using namespace std;
int n, k;
long long ans;
bitset<Maxn> f;
int main(void) {
//  freopen("in.txt", "r", stdin);
    f[] = ;
    scanf("%d", &n);
    for (int i = ; i <= n; i++) {
        scanf("%d", &k);
        f = f ^ (f << k);
    }
    for (int i = ; i <= ; i++)
        if (f[i]) {
            ans ^= i;
        }
    printf("%lld\n", ans);
    return ;
} 
           

完。

By g1n0st