「BZOJ 4245」OR-XOR

发表于 | | 阅读次数:
字数统计: 569 字

Description

题目链接：BZOJ 4245

给定一个长度为 $n$ 的序列 $a_i$，将它划分为 $m$ 段连续的区间。设第 $i$ 段的费用 $c_i$ 为该段内所有数字的异或和，则总费用为 $c_1\ \text{OR}\ c_2\ \text{OR}\cdots\ \text{OR}\ c_m$，求出总费用的最小值。

数据范围：$1\le m\le n\le 5\times 10^5$，$0\le a_i\le 10^{18}$

Solution

我们要让答案最小，那么可以贪心地让最高位尽可能为 $0$。我们先预处理出前缀异或和 $sum_i$，然后从高位到低位枚举答案的第 $i$ 位是否可以为 $0$。统计出 $n$ 个前缀异或和第 $i$ 位为 $0$ 的个数 $cnt$。如果 $cnt\geqslant m$ 并且 $sum_n$ 的第 $i$ 位也为 $0$，那么第 $i$ 位可以为 $0$；否则第 $i$ 位只能为 $1$。

考虑正确性的证明：根据题目要求，我们需要找 $m$ 个右端点，使得每个区间的异或和都为 $0$。由于到当前位置时一定保证了之前每个区间第 $i$ 位答案都是 $0$。所以如果当前位置的前缀异或和的第 $i$ 位为 $0$，那么这个新的区间第 $i$ 位的答案也一定是 $0$。特殊的，$n$ 一定是最后一个区间的右端点，所以如果 $sum_n$ 的第 $i$ 位为 $1$，那么这个区间的答案和最终答案的第 $i$ 位一定不可能为 $0$。

对于每一位计算完之后，要对于所有前缀异或和在第 $i$ 位为 $1$ 的进行标记，表示这一位不可能作为右端点了。

时间复杂度：$O(n\log a_i)$

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
 
#include <cstdio>
const int N=5e5+5;

int n,m;
long long a[N],sum[N];
bool flg[N];

int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) scanf("%lld",&a[i]),sum[i]=sum[i-1]^a[i];
    for(int i=1;i<=n;++i) flg[i]=1;
    long long ans=0;
    for(int j=62;j>=0;--j) {
        int cnt=0;
        for(int i=1;i<=n;++i) if(flg[i]&&((sum[i]>>j)&1)==0) ++cnt;
        if(cnt>=m&&((sum[n]>>j)&1)==0) {
            for(int i=1;i<=n;++i) if((sum[i]>>j)&1) flg[i]=0;
        } else {
            ans|=1LL<<j;
        }
    }
    printf("%lld\n",ans);
    return 0;
}
0%