[JRKSJ R1] 异或

ID: 6253

远端评测题

1200ms

128MiB

难度: 4

上传者:

标签>

动态规划,dp

2021

洛谷原创

O2优化

字典树,Trie 树

其它技巧

题目描述

给你 $n,k$ 和序列 $a_{1,2\dots n}$ ，选出 $k$ 个不交区间 $[l_i,r_i]\subseteq[1,n]$ ，求出

\max_{l_i,r_i}\sum_{i=1}^k\bigoplus_{j=l_i}^{r_i}a_j

式中 $\oplus$ 表示二进制异或运算。

保证数据随机。

输入共 $2$ 行。
第 $1$ 行输入两个数 $n,k$ 。
第 $2$ 行输入 $n$ 个非负整数代表序列 $a$ 。

$1$ 行输出一个非负整数，代表这个式子的最大值。

6 3
2 1 3 4 4 4

7 2
3 4 5 6 7 8 9

对于 $100\%$ 的数据， $1\le k\le n\le 3000$ ， $0\le a_i\le 10^{9}$ 。保证数据随机。

本题采用捆绑测试。

$\text{Subtask}$	$n\le$	特殊性质	分值
$1$	$30$	$k\le3$	$5$
$2$	$500$	$a_i\le10^7$	$10$
$3$	$1000$	无	$10$
$4$	$1500$		$15$
$5$	$2000$		$15$
$6$	$2500$		$20$
$7$	$3000$		$25$

序列的三个区间分别为:

2,1,[3,4],[4],[4]

所得的三个区间的异或和之和为 $7+4+4=15$ .