[文章目录]
Description
给定一个长度为n的序列a[1],a[2],...,a[n]，请将它划分为m段连续的区间，设第i段的费用c[i]为该段内所有数字的异或和，则总费用为c[1] or c[2] or ... or c[m]。请求出总费用的最小值。1<=m<=n<=500000,0<=a[i]<=10^18)
自己YY，丰衣足食。
拆位，贪心的想，如果能满足更高位为0，那么一定得满足。
如果当前位上有奇数个1，那么不存在变为0的方法。如果有偶数个1，将m段区间n-1个位置看成插m-1个隔板，那么第一个1~第二个1之间的位置就不能插入隔板，第三个1到第4个1之间不能插入隔板，以此推类。如果空的位置足够m-1个，那么可以，反之不可以则继续处理更低位。
细节好像挺多的，或者说我失了智。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int n,m;
ll a[501000];
bool v[501000];
inline char nc()
{
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2) ? EOF : *p1++;
}
inline void read(ll &x)
{
char ch=nc();
while(ch<'0'||ch>'9') ch=nc();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=nc();
}
int main()
{
scanf("%d%d",&n,&m); int cnt,num=n-1; m--;
for(int i=1;i<=n;++i) read(a[i]);
for(int i=62;~i;--i)
{
cnt=0;
for(int j=1;j<=n;++j) cnt+=(a[j]&(1ll<<i))?1:0;
if(cnt&1) continue;
bool fl=0; int c=num;/*bug3:并不将num还原*/
for(int j=1;j<n;++j)
{
if(a[j]&(1ll/*bug4:不转换成ll*/<<i)) fl^=1;
if(fl&&!v[j]) num--;
}
if(num<m) {num=c; continue;/*bug2:break*/}
fl=0;
for(int j=1;j<n;++j)
{
if(a[j]&(1ll<<i/*bug1:i写成j*/)) fl^=1;
v[j]|=fl;
}
}
ll ans=0,now=0;
for(int i=1;i<=n;++i)
{
now^=a[i];
if(m&&!v[i]) ans|=now,now=0,m--;
}
ans|=now;
printf("%lld",ans);
return 0;
}