题目描述
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 7Sample 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 |
|