首页 > 代码库 > 【BZOJ-4245】OR-XOR 按位贪心

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

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

3

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 longinline LL read(){    LL x=0,f=1; char ch=getchar();    while (ch<0 || ch>9) {if (ch==-) f=-1; ch=getchar();}    while (ch>=0 && ch<=9) {x=x*10+ch-0; ch=getchar();}    return x*f;}#define MAXN 500010int N,M,d[MAXN][65],visit[MAXN];LL a[MAXN],sum[MAXN],ans;void Get(LL x,int dx[]) {int tot=0; while (x) dx[tot++]=x%2,x/=2;}int main(){    N=read(),M=read();    for (int i=1; i<=N; i++) a[i]=read(),sum[i]=sum[i-1]^a[i];    for (int i=1; i<=N; i++) Get(sum[i],d[i]);    for (int i=62; i>=0; i--)        {            int tot=0;            for (int j=1; j<=N; j++)                if (!visit[j] && !d[j][i]) tot++;            if (tot>=M && !d[N][i])                 for (int j=1; j<=N; j++) if (d[j][i]) visit[j]=1; else;            else ans|=(1LL<<i);        }    printf("%lld\n",ans);    return 0;}

 

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