BZOJ4245: [ONTAK2015]OR-XOR(首碼和)

題意

題目鏈接

Sol

又是一道非常interesting的題目

很顯然要按位考慮

因為最終答案是xor之後or，所以分開之後之後這樣位上1的數量是一定是偶數，否則直接加到答案裡面

同時，這裡面有些部分是不能切的(分開之後會產生奇數個1)，把這些位置記出來

如果能保證每次都有大於\(m\)個位置能切，就是合法的

#include<bits/stdc++.h>
#define LL long long 
using namespace std;
const int MAXN = 5e5 + 10, B = 62;
inline LL read() {
    char c = getchar(); LL x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M;
LL a[MAXN];
bool flag[MAXN];
int main() {
    N = read(); M = read();
    for(int i = 1; i <= N; i++) a[i] = read();
    int tot = 0; LL ans = 0;
    for(int k = 62; k >= 0; k--) {
        int num = 0, sum = 0;
        for(int i = 1; i <= N; i++) {
            sum ^= a[i] >> k & 1;
            if((!sum) && (!flag[i])) num++;
        }
        if((sum & 1) || (num < M)) {ans += 1ll << k; continue;}
        sum = 0;
        for(int i = 1; i <= N; i++) {
            sum ^= a[i] >> k & 1;
            if(sum && !flag[i]) flag[i] = 1;
        }
    }
    cout << ans;
    return 0;
}