bzoj 4245 [ONTAK2015]OR-XOR

题目描述

Description

给定一个长度为n的序列a[1],a[2],…,a[n],请将它划分为m段连续的区间,设第i段的费用c[i]为该段内所有数字的异或和,则总费用为c[1] or c[2] or … or c[m]。请求出总费用的最小值。

Input

第一行包含两个正整数n,m(1<=m<=n<=500000),分别表示序列的长度和需要划分的段数。

第一行包含n个整数,其中第i个数为a[i](0<=a[i]<=10^18)。

Output

输出一个整数,即总费用的最小值。

Sample Input

3 2
1 5 7

Sample Output

3

HINT

第一段为[1],第二段为[5 7],总费用为(1) or (5 xor 7) = 1 or 2 = 3。

简要题意:给定一个长度为 $n$ 的序列 $a_i$,将其划分成 $m$ 段连续区间,每段区间的费用为这段区间的异或和,求所有段的费用的或的最小值

$n\le 5\times 10^5$

Solution

我们考虑分成 $m$​ 段相当于除了 $n$ 以外,再选 $m-1$​​ 个右端点

然后我们考虑按位贪心,注意到如果某一位出现了奇数次那么它一定要算到答案里

否则我们维护合法的右端点,注意到对于第 $k$ 位,所有前缀异或和为 $0$​ 的点都可以作为一个右端点,而这个时候注意到点 $n$ 的前缀异或和一定是 $0$,所以我们只需要判断右端点的数量是否大于等于 $m$ 即可,然后每次做完将前缀异或和为 $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
31
32
#include <iostream>
#include <cstdio>
#define maxn 500010
#define ll long long
using namespace std;

int n, m;

ll a[maxn];

bool vis[maxn];

ll ans;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
for (int o = 61; ~o; --o) {
int s = 0, num = 0;
for (int i = 1; i <= n; ++i) {
s ^= a[i] >> o & 1;
if (!s && !vis[i]) ++num;
}
if (num < m || s) { ans += 1ll << o; continue; }
for (int i = 1; i <= n; ++i) {
s ^= a[i] >> o & 1;
if (s) vis[i] = 1;
}
}
cout << ans << endl;
return 0;
}