大意: 给定数组, 求划分为$m$段, 第$i$段费用$c_i$为异或和, 总的费用为$c_1 or c_2 or ... or c_m$, 求最少费用.
从高位到低位贪心, 若第$i$位$1$的个数为奇数, 费用一定会加上$2^i$.
否则的话, 可以求出所有可以分割的位置个数, 若不少于$m$则可以不用增加费用.
#include <iostream>
#include <cstdio>
#define REP(i,a,n) for(int i=a;i<=n;++i)
#define PER(i,a,n) for(int i=n;i>=a;--i)
using namespace std;
typedef long long ll;
const int N = 1e6+10;
int n, m;
ll a[N], ans, lim;
int chk(ll x) {
if (a[n]&x) return 0;
int cnt = 0;
REP(i,1,n) if (!(a[i]&lim)&&!(a[i]&x)) ++cnt;
return m<=cnt;
}
int main() {
scanf("%d%d", &n, &m);
REP(i,1,n) scanf("%lld", a+i),a[i]^=a[i-1];
PER(i,0,63) {
if (chk(1ll<<i)) lim ^= 1ll<<i;
else ans ^= 1ll<<i;
}
printf("%lld\n", ans);
}
bzoj 4245 [ONTAK2015]OR-XOR (贪心)
原文：https://www.cnblogs.com/uid001/p/11140709.html