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

    • 738通过
    • 3.6K提交
  • 题目提供者 Anguei 管理员
  • 评测方式 云端评测
  • 标签 各省省选 2019
  • 难度 省选/NOI-
  • 时空限制 3000ms / 1024MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

    小粽面前有 $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: 复制
    3 2
    1 2 3
    输出样例#1: 复制
    6

    说明

    测试点 $n$ $k$
    $1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$ $\leqslant 10^3$ $\leqslant 10^3$
    $9$, $10$, $11$, $12$ $\leqslant 5 \times 10^5$ $\leqslant 10^3$
    $13$, $14$, $15$, $16$ $\leqslant 10^3$ $\leqslant 2 \times 10^5$
    $17$, $18$, $19$, $20$ $\leqslant 5 \times 10^5$ $\leqslant 2 \times 10^5$
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。