【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 
      
        #include 
       
         #include 
        
          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)             {                 ans^=j;                 for(flag=sum=0,i=1;i