BZOJ 4245 「ONTAK2010」OR-XOR

发表于 | 分类于

Description

给你一个长为\(n\)的自然数序列\(a_i\)，将其分为恰好\(m\)段，设第\(i\)段异或和为\(c_i\)，请最小化\(c_1\lor c_2\lor\ldots\lor c_m\)。

\(1\leq n\leq 500000, a_i\leq 10^{18}\)。

Solution

考虑求\(a_i\)的异或前缀和\(b_i\)，那么每一段的异或和就可以用两个\(b_i\)异或起来的结果来表示。

因为是要求答案最小，那么我们就从高位往低位考虑，尽可能让高位不要填\(1\)。考虑某一位如果不能是\(1\)，并且你的第一段为\(1\ldots p\)的话，那么\(b_p\)在这一位必不为\(1\)，根据异或的结果可以知道下一个剖分点的\(b_i\)的这一位也不是\(1\)……最终\(b_n\)的这一位也不是\(1\)。换言之存在\(m\)个位置在这一位不为\(1\)，并且\(b_n\)在这一位也不是\(1\)。

最后要注意的一点是如果有一个剖分点在这一位是\(1\)的话，那么之后的位不能使用该剖分点，否则就错力。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
typedef long long ll;
const int maxn = 500005;
int n, m;
ll a[maxn], b[maxn];
bool disable[maxn];
bool check(int c) {
  ll th = 1LL << c;
  if(th & b[n]) return false;
  int cnt = 1;
  for(int i = 1; i < n; i ++) {
    if(disable[i]) continue;
    if(!(th & b[i])) cnt ++;
  }
  if(cnt >= m) {
    for(int i = 1; i < n; i ++) {
      if(th & b[i]) disable[i] = true;
    }
    return true;
  } else {
    return false;
  }
}

int main() {
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= n; i ++) scanf("%lld", &a[i]);
  for(int i = 1; i <= n; i ++) b[i] = b[i - 1] ^ a[i];
  ll ans = 0;
  for(int c = 59; c >= 0; c --) {
    if(!check(c)) ans += (1LL << c);
  }
  printf("%lld\n", ans);
  return 0;
}