首页技术正文

【BZOJ-4245】OR-XOR 按位贪心

程序员胜楠技术 2022年11月14日

0 收藏 648 点赞 4,663 浏览 1348 个字

4245: [ONTAK2015]OR-XOR

Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 486 Solved: 266
[Submit][Status][Discuss]

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

HINT

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

Source

By Claris

Solution

按位贪心。

首先预处理出前缀异或和，然后对这些异或和分成M段，考虑按位or运算的性质，当前位存在1即为1，所以，贪心的看当前位是否能只取M个0，如果可以则当前位为0，否则在答案中or上$2^{i}$即可。

这么做显然应该按数位从高到低枚举，还需要注意的地方就是，并不是当前位能取M个0当前位就可以选0，同时应该满足第N个数的当前位也必须为0，这里很容易遗漏。

在贪心的把当前位选成0后，要将当前位为1的数打上标记，表示低位不能选此数。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define LL long long
inline LL read()
{
    LL x=,f=; char ch=getchar();
    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
    return x*f;
}
#define MAXN 500010
int N,M,d[MAXN][],visit[MAXN];
LL a[MAXN],sum[MAXN],ans;
void Get(LL x,int dx[]) {int tot=; while (x) dx[tot++]=x%,x/=;}
int main()
{
    N=read(),M=read();
    for (int i=; i<=N; i++) a[i]=read(),sum[i]=sum[i-]^a[i];
    for (int i=; i<=N; i++) Get(sum[i],d[i]);
    for (int i=; i>=; i--)
        {
            int tot=;
            for (int j=; j<=N; j++)
                if (!visit[j] && !d[j][i]) tot++;
            if (tot>=M && !d[N][i])
                for (int j=; j<=N; j++) if (d[j][i]) visit[j]=; else;
            else ans|=(1LL<<i);
        }
    printf("%lld\n",ans);
    return ;
}