P5283-[十二省联考2019]异或粽子
题目:
题目描述:
小粽是一个喜欢吃粽子的好孩子。今天她在家里自己做起了粽子。
小粽面前有 $n$ 种互不相同的粽子馅儿，小粽将它们摆放为了一排，并从左至右编号为 $1$ 到 $n$。第 $i$ 种馅儿具有一个非负整数的属性值 $a_i$。每种馅儿的数量都足够多，即小粽不会因为缺少原料而做不出想要的粽子。小粽准备用这些馅儿来做出 $k$ 个粽子。
小粽的做法是：选两个整数数 $l$, $r$，满足 $1 \leqslant l \leqslant r \leqslant n$，将编号在 $[l, r]$ 范围内的所有馅儿混合做成一个粽子，所得的粽子的美味度为这些粽子的属性值的异或和。（异或就是我们常说的 xor 运算，即 C/C++ 中的 ˆ 运算符或 Pascal 中的 xor 运算符）
小粽想品尝不同口味的粽子，因此它不希望用同样的馅儿的集合做出一个以上的
粽子。
小粽希望她做出的所有粽子的美味度之和最大。请你帮她求出这个值吧！
输入格式:
第一行两个正整数 $n$, $k$，表示馅儿的数量，以及小粽打算做出的粽子的数量。
接下来一行为 $n$ 个非负整数，第 $i$ 个数为 $a_i$，表示第 $i$ 个粽子的属性值。
对于所有的输入数据都满足：$1 \leqslant n \leqslant 5 \times 10^5$, $1 \leqslant k \leqslant \min\left{\frac{n(n-1)}{2},2 \times 10^{5}\right}$, $0 \leqslant a_i \leqslant 4 294 967 295$。
输出格式:
输出一行一个整数，表示小粽可以做出的粽子的美味度之和的最大值。
样例:
样例输入1:
样例输出1:
思路:
实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| #include "ybwhead/ios.h"
int n, k;
const int maxn = 5e5 + 10;
long long a[maxn];
priority_queue<pair<pair<long long, int>, int>> q;
long long ans = 1, x;
int cc[maxn * 40][2], siz[maxn * 40], tot;
void ins(long long x)
{
int u = 0;
for (int i = 31; i >= 0; i--)
{
int ch = (x >> i) & 1;
siz[u]++;
if (!cc[u][ch])
cc[u][ch] = ++tot;
u = cc[u][ch];
}
siz[u]++;
}
long long query(long long x, int rk)
{
int u = 0;
long long ans = 0;
for (int i = 31; i >= 0; i--)
{
int ch = (x >> i) & 1;
if (!cc[u][ch ^ 1])
u = cc[u][ch];
else if (rk <= siz[cc[u][ch ^ 1]])
u = cc[u][ch ^ 1], ans |= 1LL << i;
else
rk -= siz[cc[u][ch ^ 1]], u = cc[u][ch];
}
return ans;
}
int main()
{
yin >> n >> k;
for (int i = 1; i <= n; i++)
yin >> a[i], a[i] ^= a[i - 1];
k <<= 1;
for (int i = 0; i <= n; i++)
ins(a[i]);
for (int i = 0; i <= n; i++)
{
q.push(make_pair(make_pair(query(a[i], 1), i), 1));
}
for (int i = 1; i <= k; i++)
{
pair<pair<long long, int>, int> x = q.top();
ans += x.first.first;
q.pop();
if (x.second < n)
{
x.second++;
x.first.first = query(a[x.first.second], x.second);
q.push(x);
}
}
cout << (ans >> 1) << endl;
return 0;
}
|