题解 P7335【[JRKSJ R1] 异或】

cyffff · 2021-01-14 21:13:41 · 题解

\text{Link}

题意

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

我们首先思考怎么处理 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~