4245: [ONTAK2015]OR-XOR
1 /* 2 要求分成m份,总价值为a1|a2|a3...,总价值最小,ai为第i份的异或和。 3 4 首先预处理异或和。 5 根据贪心的思想,高位最好是0。 6 于是从高位往低位枚举,看一下每一位是否可以为0。 7 如果当前这一位可以为0,每一份的(异或和)(或)起来都是0,所以每一份异或和的这一位不能有1 8 那么一个点可以成为分割点当且仅当这个点的sum值的这一位为0,然后统计有多少个点的sum为0 9 如果个数>=m且这一位上的所有1为偶数个(sum[n]&(1LL< 14 using namespace std;15 typedef long long LL;16 17 inline LL read() {18 LL x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;19 for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;20 }21 22 const int N = 500100;23 LL a[N],sum[N],flag[N];24 25 int main() {26 int n,m;cin >> n >> m;27 for (int i=1; i<=n; ++i) 28 a[i] = read(),sum[i] = sum[i-1] ^ a[i];29 LL ans = 0; 30 for (int i=62; i>=0; --i) { // 看第i位能否为0 31 int cnt = 0;32 for (int j=1; j<=n; ++j) { // 统计有多少个右端点满足条件 33 if (!flag[j] && (sum[j]&(1LL< = m && (sum[n]&(1LL< << i);40 }41 cout << ans;42 return 0;43 }