自动搬运

查看原文

来自洛谷，原作者为

	cyffff Not yet for the story on the last page, it's not the end.

搬运于2025-08-24 22:28:53，当前版本为作者最后更新于2021-01-14 21:13:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

$\text{Link}$

题意

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

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

$1\le k\le n\le 3000,0\le a_i\le 10^9$。

保证数据随机。

思路

$\text{Update 2022.4.22}$：重构全文。

$\text{Subtask 1}$

$O(n^{2k})$ 暴力寻找左右端点即可。

$\text{Subtask }2 \sim4$

我们首先思考怎么处理 $k=1$ 的情况，这是一个经典问题。

设 $p_i=\bigoplus_{j=1}^{i}a_j$，则 $\bigoplus_{j=l}^{r}a_j=p_r\text{ xor }p_{l-1}$，我们考虑对于每个 $r$ 快速找出 $l$ 使得上式最大，对 $p$ 建出 $\text{01Trie}$，在上面贪心地选择不同的儿子即可。

我们设 $f_{l,r}=\displaystyle\max_{l\le i,j\le r}p_i\text{ xor }p_j$，即在 $p_{l,l+1,...,r}$ 中选 $2$ 个数使它们异或和最大。

设处理到第 $i+1\sim n$ 个数，第 $j\sim k$ 个区间的答案为 $dp_{i,j}$，则 $dp_{i,j}=\displaystyle\max_{k=i}^{n-1}(dp_{k,j+1}+f_{i,k+1})$。

暴力处理，时间复杂度 $O(n^3)$。

$\text{Subtask }5\sim7$

发现上面的状态转移方很难优化，因为 $f_{i,k+1}$ 是变化的，如果 $k=f_{i,k+1}$ 不变的话，$dp_{i,j}=\displaystyle\max_{k=i}^{n-1}(dp_{k,j+1}+f_{i,k+1})=\displaystyle\max_{k=i}^{n-1}(dp_{k,j+1})+k$.

于是我们打一个表观察一下发现 $i$ 固定时，对于 $k\in[i,n]$，$f_{i,k}$ 不同的值很少，于是我们可以想到把相同的 $f_{i,k}$ 压缩起来，对于 $f_{i,k}$ 相同的一段区间 $k\in[l,r]$，我们求出 $f_{i,l}+\displaystyle\max_{i=l}^rdp_{i,j+1}$ 即可。

我们发现 $f$ 数组单调不递减，$dp$ 数组单调不递增，于是上面的式子就等价于 $dp_{i,j}=\displaystyle\max_{l,r}(f_{i,l}+dp_{l,j+1})$。

现在我们来证明这个算法的复杂度正确。

由于数据随机生成，当我们插入一个数时，设此时已经插入 $m$ 个数，这时候一共有 $\dfrac {(m+1)m} 2$ 个异或和，这个数可以贡献 $m$ 个异或和。即有 $\dfrac 2 {m+1}$ 的几率成为 $\max$，这个数贡献了 $\dfrac 2 {m+1}$ 的期望。

所以 $f_{i,k}$ 中的数的个数的期望为 $\sum_{i=1}^{n}\dfrac 2 {i}≈2\times\log n$，所以期望时间复杂度为 $O(n^2\log w+nk\log n)$。

期望得分 $100$ 分。

另外，由于数据随机，暴力转移较少的数的 $\text{dp}$ 也可以过，对策在考虑。

具体实现见以下代码（我很久以前写的，有点丑请见谅）：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int maxn;
struct trie{//01-Trie
	int cnt;
	int son[90005][2];
	trie(){
		cnt=1;
	}
	void clear(){
		for(int i=1;i<=cnt;i++){
			son[i][0]=son[i][1]=0;
		}
		cnt=1;
	}
	void insert(int x){
		int rt=1;
		for(int i=29;i>=0;i--) {
			if(!son[rt][(x>>i)&1])
				son[rt][(x>>i)&1]=++cnt;
			rt=son[rt][(x>>i)&1];
		}
	}
	int find(int x){
		int rt=1,ans=0;
		for(int i=29;i>=0;i--){
			if(son[rt][!((x>>i)&1)]) rt=son[rt][!((x>>i)&1)],ans+=1<<i;
			else rt=son[rt][(x>>i)&1];
		}
		return ans;
	}
}t;
struct line{
	int l,r;
	int val;
	line(){
		l=r=val=0;
	}
	line(int a,int b,int c){
		l=a,r=b,val=c;
	}
};
struct array{
	line s[100];
	int len;
	array(){
		len=0;
	}
	int operator[](const int &x){
		return s[x].val;
	}
	inline void init(int i){
		len=1;
		s[1].l=0;
		s[1].r=i;
		s[1].val=0;
	}
	inline void insert(int x,int v){//压缩ans数组
		if(v==s[len].val){
			s[len].r=x;
		}else{
			len++;
			s[len].l=x;
			s[len].r=x;
			s[len].val=v;
		}
	}
	inline int top(){
		return s[len].val;
	}
}ans[3005];
int a[3005];
int n,k;
void init(){//预处理ans
	for(int i=0;i<=n;i++){
		t.clear();
		t.insert(a[i]);
		ans[i].init(i);
		for(int j=i+1;j<=n;j++){
			int now=t.find(a[j]);
			ans[i].insert(j,max(ans[i].top(),t.find(a[j])));
			t.insert(a[j]);
		}
	}	
}
namespace IO{
	//read()
}using namespace IO;
ll dp[3005][2];
int main(){
	n=read(),k=read();
	for(int i=1;i<=n;i++)
		a[i]=read()^a[i-1];
	init();
	for(int i=k-1;i<=n;i++){
		dp[i][k&1]=ans[i].top();
	}
	for(int d=k-1;d;d--){//dp
		int s=d&1;//滚动数组优化
		for(int l=n;l>=0;l--){
			ll mx=0;
			int r=1;
			mx=ans[l][r]+dp[l][!s];
			for(r++;r<=ans[l].len;r++){
				if(dp[ans[l].s[r].l][!s]+ans[l].top()<mx) break;//剪枝
				mx=max(mx,dp[ans[l].s[r].l][!s]+ans[l][r]);
			}
			dp[l][s]=mx;
		}
	}
	cout<<dp[0][1];
}

再见 qwq~