题解：P7335 [JRKSJ R1] 异或
AeeE5x
·
·
题解
提供一种没有常数的做法。
随便实现都能跑到最优解 rk1。
Solution
考虑 DP。
因为发现每次转移都只需要上一层，所以可以把 DP 数组压成一维的，重复做 $k$ 次即可。
朴素做法是对每个 $i$ 枚举所有可能的 $j$，转移 $dp_{i}\gets\max(dp_{i},dplast_{j-1}+\operatorname{xor}_{l=j}^{i}a_l)$。
最后对 DP 数组做一遍前缀 $\max$。
---
现在考虑数据随机带来的性质。
考虑一个点往左，哪些决策点是可能的。
从这个点往左，做一个后缀异或和，则所有可能的决策点是后缀异或和的每个后缀最大值的位置。因为非后缀最大值位置会被其右边的后缀最大值位置偏序。（DP 数组不降）
对每个 $i$ 而言这个决策点的数量期望应该是 $O(\log V)$ 的。这等价于随机序列前缀 $\max$ 的数的数量。
处理出来这个信息，每次暴力转移，跑 $k$ 次 DP，就做完了。
期望 $O(nk\log V)$。
## Code
没有经过任何卡常。
:::info[代码]
```cpp
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3fll
using namespace std;
int n,k;
int a[3010],pre[3010];
vector<int> ts[3010];
long long dp[3010],dp_last[3010];
void solve(){
memcpy(dp_last,dp,(n+1)*(sizeof(long long)));
memset(dp,0,(n+1)*(sizeof(long long)));
for(int i=1;i<=n;i++) for(int x:ts[i]) dp[i]=max(dp[i],dp_last[x-1]+(pre[i]^pre[x-1]));
for(int i=1;i<=n;i++) dp[i]=max(dp[i],dp[i-1]);
}
int main(){
cin.tie(0)->sync_with_stdio(false);
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) pre[i]=pre[i-1]^a[i];
for(int i=1;i<=n;i++){
int nowxor=0,maxxor=-1;
for(int p=i;p>=1;p--){
nowxor^=a[p];
if(nowxor>maxxor) ts[i].push_back(p),maxxor=nowxor;
}
}
while(k--) solve();
cout<<dp[n]<<"\n";
# ifdef TakanashiHoshino
cerr<<"\nUsed time: "<<clock()*1.0/CLOCKS_PER_SEC<<"s.\n";
# endif
return 0;
}
```
:::