[Codeforces Mail.Ru Cup 2018 Round 1] D. Changing Array (异或和，贪心)

发表于 | 分类于 ， | 评论数： | 阅读次数：

http://codeforces.com/contest/1054/problem/D

一个人有$n$个二进制最高位$1%不超过$k$位的数，现在允许每一个数按位取反，统计这个数列中最多有多少个区间异或和不是0。

发现一个重要的性质是，每一个区间内有两个数进行取反操作的话，实际就是没有进行取反操作。因为取反操作可以看做是一个数对$2^k-1$异或，两个数进行取反的话，那么就是异或$2^k-1$两次，就被抵消了。

假设前缀和为$sum$的点有$k$个，那么一定有$C_{k-1}^2$种构成区间异或和为0的方式，现在的问题就是尽量减少每一种$sum$出现的次数了。

于是我们可以贪心地去比每一个数和它翻转后与前缀和异或后的次数，每次往出现少的异或和上加。总的贡献是$\sum_i C^2_{cnt_i-1}$。

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
#include <bits/stdc++.h>
using namespace std;

using LL = long long;
const int maxn = 200200;
int n, k;
LL a[maxn];
map<LL, int> cnt;

signed main() {
  // freopen("in", "r", stdin);
  auto rev = [=](LL x) { return x ^ ((1LL << (LL)k) - 1); };
  while(~scanf("%d%d",&n,&k)) {
    LL ret = 1LL * (n + 1) * n / 2;
    LL sum = 0;
    cnt.clear();
    cnt[sum]++;
    for(int i = 1; i <= n; i++) {
      scanf("%lld", &a[i]);
      if(cnt[sum^a[i]] > cnt[sum^rev(a[i])]) sum ^= rev(a[i]);
      else sum ^= a[i];
      cnt[sum]++;
    }
    for(auto p : cnt) {
      ret -=  1LL * (p.second - 1) * p.second / 2;
    }
    printf("%lld\n", ret);
  }
  return 0;
}