题解：P7335 [JRKSJ R1] 异或

5pts：

直接爆搜。

O(n^{2k})

。

40pts：

发现可能可以 DP。记

f_{i,j}

为前

i

个数中选

j

个区间，则转移方程：

f_{i,j}=f_{i-1,j}

。（不选区间）

f_{i,j}=f_{l-1,j-1}+w_{l,i}

。（选区间）

时间复杂度

O(n^2k)

。

100pts：

我们定义一个区间是“无用的”，当且仅当存在另一个区间，使得这个区间比另一个区间长，且没有另一个区间异或和大。

我们将这些无用区间抛弃掉，剩下几个区间？考虑一个长度为

1

的区间，必然是有用的。长度为

2

的呢？因为数据随机，所以

a_i

异或

a_{i-1}

大于

a_i

的概率是

\dfrac{1}{2}

，同理，一个长度为

len

的区间，是有用的概率为

\dfrac{1}{len}

。

所以在剔除无效区间后再 DP。调和级数

1+\dfrac{1}{2}+\dfrac{1}{3}+\cdots+\dfrac{1}{n}

是

O(\ln n)

的，所以时间复杂度

O(nk \ln n)

。

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3009;
struct Node{
	int l,r,w;
}s[N][N];
int n,k,V,x[N],num[N],mx[N][N];
ll f[N][2];
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		cin>>x[i],x[i]=x[i-1]^x[i];
	for(int i=1;i<=n;i++)
		for(int j=i-1,tmp=0;j>=0;j--)
			tmp=max(tmp,x[i]^x[j]),mx[j][i]=max(mx[j][i-1],tmp);
	for(int i=1;i<=n;i++){
		s[i][1].l=s[i][1].r=0;
		s[i][1].w=mx[0][i];
		num[i]=1;
		for(int j=1;j<i;j++)
			if(mx[j][i]==mx[j-1][i]) s[i][num[i]].r++;
			else{
				s[i][++num[i]].l=j;
				s[i][num[i]].r=j;
				s[i][num[i]].w=mx[j][i];
			}
	}
	for(ll j=1;j<=k;j++)
		for(ll i=1;i<=n;i++){
			f[i][j%2]=0;
			for(ll x=1;x<=num[i];x++)
				f[i][j%2]=max(f[i][j%2],f[s[i][x].r][(j%2)^1]+s[i][x].w);
		}
	cout<<f[n][k%2]<<endl;
	return 0;
}

题解：P7335 [JRKSJ R1] 异或

文章操作

相关推荐

评论

题解：P7335 [JRKSJ R1] 异或