当前位置：首页 > news >正文

《P5283 [十二省联考 2019] 异或粽子》

news 2025/5/19 10:12:05

题目描述

小粽是一个喜欢吃粽子的好孩子。今天她在家里自己做起了粽子。

小粽面前有 n 种互不相同的粽子馅儿，小粽将它们摆放为了一排，并从左至右编号为 1 到 n。第 i 种馅儿具有一个非负整数的属性值 ai。每种馅儿的数量都足够多，即小粽不会因为缺少原料而做不出想要的粽子。小粽准备用这些馅儿来做出 k 个粽子。

小粽的做法是：选两个整数数 l, r，满足 1⩽l⩽r⩽n，将编号在 [l,r] 范围内的所有馅儿混合做成一个粽子，所得的粽子的美味度为这些粽子馅儿的属性值的异或和。（异或就是我们常说的 xor 运算，即 C/C++ 中的 ˆ 运算符或 Pascal 中的 xor 运算符）

小粽想品尝不同口味的粽子，因此它不希望用同样的馅儿的集合做出一个以上的粽子。

小粽希望她做出的所有粽子的美味度之和最大。请你帮她求出这个值吧！

输入格式

第一行两个正整数 n, k，表示馅儿的数量，以及小粽打算做出的粽子的数量。

接下来一行为 n 个非负整数，第 i 个数为 ai，表示第 i 个粽子的属性值。对于所有的输入数据都满足：1⩽n⩽5×105, 1⩽k⩽min{2n(n−1),2×105}, 0⩽ai⩽4294967295。

输出格式

输出一行一个整数，表示小粽可以做出的粽子的美味度之和的最大值。

输入输出样例

输入 #1复制

3 2
1 2 3

输出 #1复制

代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

int main() {
int n, k;
cin >> n >> k;

vector<ll> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}

// 计算所有可能的区间异或和
vector<ll> xor_sums;
for (int l = 0; l < n; l++) {
ll current_xor = 0;
for (int r = l; r < n; r++) {
current_xor ^= a[r];
xor_sums.push_back(current_xor);
}
}

// 对所有异或和进行排序（降序）
sort(xor_sums.begin(), xor_sums.end(), greater<ll>());

// 取前k大的异或和相加
ll result = 0;
for (int i = 0; i < min(k, (int)xor_sums.size()); i++) {
result += xor_sums[i];
}

cout << result << endl;
return 0;
}