【BZOJ4245】[ONTAK2015]OR-XOR 贪心

时间:2022-12-17 18:50:07

【BZOJ4245】[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。

题解:首先我们肯定要贪心来搞,我们肯定是切的次数越少越好,如果我们想让第i位为0,那么需要切出来的每一段的第i位xor起来都是0

从大到小枚举第i位,如果第i位为1的数的个数为奇数,那么我们无论怎么切答案的第i位肯定都是1,所以不管;如果第i位为1的数的个数为偶数,那么我们将他们两两配对,每对的中间肯定是不能被切过的,剩余位置切不切无所谓。所以我们统计出不能切的数量sum,如果sum+m<=n-1那么这些位置我们就都不切,否则答案的第i位只能是1,切不切我们不管。

#include <cstdio> 
#include <cstring> 
#include <iostream> 
using namespace std; 
const int maxn=500010; 
typedef long long ll; 
int n,m,sum,tot; 
ll ans; 
ll v[maxn]; 
int s[maxn]; 
int main() 
{ 
    scanf("%d%d",&n,&m); 
    int i,flag=0; 
    ll j; 
    for(i=1;i<=n;i++) 
    { 
        scanf("%lld",&v[i]); 
    } 
    for(j=1ll<<62;j;j>>=1) 
    { 
        for(sum=0,i=1;i<=n;i++)  if(v[i]&j)  sum++; 
        if(sum&1)   ans^=j; 
        else
        { 
            for(flag=sum=0,i=1;i<n;i++) 
            { 
                if(v[i]&j)  flag^=1; 
                s[i]+=flag,sum+=(s[i]==1)&flag; 
            } 
            if(sum+tot+m>n) 
            { 
                ans^=j; 
                for(flag=sum=0,i=1;i<n;i++) 
                { 
                    if(v[i]&j)  flag^=1; 
                    s[i]-=flag; 
                } 
            } 
            else    tot+=sum; 
        } 
    } 
    printf("%lld",ans); 
    return 0; 
}