c/c++语言开发共享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; }