P8019 按位贪心题

· · 题解

题解

前置知识：

做这个题之前我们先要了解与按位异或相关的两个性质：

  1. b=a\oplus b\oplus a
  2. 0\oplus1=1,0 \oplus 0=0

以及按位或的一个性质：多个数按位或，任意一个数的第 i 位为 1，则结果的第 i 位为 1。

题目分析：

回到题目本身，要求将数列分成 M 段，求每段的异或和，让最后每段异或和的按位或最小。首先每段异或和，根据上面异或的第一条性质，我们很容易想到前缀异或和，结合按位或的性质，我们可以按位从高往低贪心，尽量保证高位为 0，也就是说，让分成的 M 段，每段都为 0。

代码设计：

对于第 j 位，从前往后异或，统计出现 0 的次数，若小于 M，则说明该位无论怎么分最后按位或结果都是 1。这里要注意的是，0 的次数可能会大于 M，因为我们用的是前缀和，所以两个相邻 0 区间合并之后异或和还是 0。

因为贪心思想为尽量保证高位为 0，所以低位的分发不能与高位相冲突，否则也是 1。

那么我们需要将高位不能作为 M 段断点的位置标记下来，在枚举低位的时候，要同时异或和为 0 以及该点是否为高位断点。

如果第 j 位的结果能为 0，那么需要更新断点标记。

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define N 500010
ll n,m,a[N],flag[N],ans;
//flag数组为断点标记数组
int main(){
    ll i,j;
    cin>>n>>m;
    for(i=1;i<=n;i++){
        cin>>a[i];
    }
    for(j=62;j>=0;j--){
        ll tmp=0,sum=0;
        for(i=1;i<=n;i++){
            tmp ^= (a[i]>>j) & 1;
            //判断第j位的异或和是否为1
            if(!tmp && !flag[i]) sum++;
            //同时要保证不与高位冲突
        }
        if((tmp&1) || (sum<m)){
         //如果该位最终结果为1，或者不能分成超过M段
            ans+= 1ll<<j;
            continue;
        }
        tmp=0;
      //将第j为的断点标记加上去
        for(i=1;i<=n;i++){
            tmp^= (a[i]>>j) & 1;
            if(tmp && !flag[i]) flag[i]=1;
        }
    }
    cout<<ans;
    return 0;
}