剪贴板 - 4sub0wlj

T2 异或

T650098 异或 - 洛谷
网页版题解

Subtask 1

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

---

Subtask 2~8

考虑$k=1$的情况
设$p_{i}$=$\oplus^{i}{j=1}a$，则$\oplus_{j=l}^{r}a_{j}=p_{r}$ $xor$ $p_{l-1}$，考虑对于每个$r$快速找出$l$使得上式最大，对$p$构建$01Trie$树，即可在上面贪心选择不同的儿子
设$f_{l,r}=\max \limits_{1\leq i,j\leq r}$，即在$p_{l,l+1,\dots,r}$中选$2$个数使它们异或和最大
设处理到第$i$+1-$n$个数，第$j$-$k$个区间的答案为$dp_{i,j}$，则$dp_{i,j}=\max \limits_{k=i}^{n-1}(dp_{k,j+1}+f_{i,k+1})$
时间复杂度$O(n^3)$

---

Subtask 9~20 (100pts)

考虑暴力$dp$
先把序列上的点变成前缀异或和
$f_{i,j}$表示$1-i$选择了$j$个区间，答案最大是多少，$mx_{i,j}$表示在$i-j$区间选择两个点使得$a\oplus b$最大
假设现在已经将$1-i$的所有区间求出来了，现在要求出$[1,i]-i+1$
考虑从后向前一个个加入节点，每次加入的时候求出和$i+1$的最大异或对，然后和$mx_{k,i}$拼起来，就能求出$mx_{k,i+1}$

---

附玄学优化(好像不需要)

暴力对拍可以发现对于大样例，$mx$数组有很长的段是同一个值，可以考虑将同一段的$mx_{k,i}$压缩
那么对于$mx_{k,i}(l-r)$相同的转移，容易发现，$f_{r,j-1}$必为最优解，因为$f$数组一维一定单调不降
最后还可以对$dp$使用滚动数组，$j$的那一维在外层枚举后就可以滚掉
复杂度是$O(n^2$ $log$ $n)$级别

---

参考代码

#include<bits/stdc++.h>
#define N 3005
typedef long long ll;
using namespace std;
struct NODE{ ll l,r,w; }s[N][N];
ll n,k,V,a[N],nm[N],mx[N][N],f[N][2];
int main(){
    cin>>n>>k>>V;
    for(ll i=1;i<=n;i++) cin>>a[i],a[i]=a[i]^a[i-1];
    for(ll i=1;i<=n;i++) for(ll j=i-1,tmp=0;j>=0;j--)
        tmp=max(tmp,a[i]^a[j]),mx[j][i]=max(mx[j][i-1],tmp);
    for(ll i=1;i<=n;i++){
		s[i][1].l=s[i][1].r=0,s[i][1].w=mx[0][i],nm[i]=1;
        for(ll j=1;j<i;j++)
            if(mx[j][i]==mx[j-1][i]) s[i][nm[i]].r++;
            else s[i][++nm[i]].l=j,s[i][nm[i]].r=j,s[i][nm[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<=nm[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];
	return 0;
}