BZOJ 4260: Codechef REBXOR 【Trie树贪心求区间异或和最值】

题目传送门

题目分析：

设$f[i]$表示$[1,i]$中区间异或和的最大值 ，$g[i]$表示$[i,n]$中区间异或和的最大值
（一个前缀一个后缀）
那么答案就是 m a x { f [ i ] + g [ i + 1 ] } max{f[i]+g[i+1]} max{f[i]+g[i+1]}
考虑如何求$f$，记$s[i]$表示$[1,i]$的异或和：
$$f[i]=max(f[i-1],s[i]xors[j]),j\in [0,i-1]$$
要求后者的最值，只需要把前面的每个$s[j]$拆成二进制位插入Trie树中，用$s[i]$进去从高位到低位贪心，看是否有与当前位相反的数存在，存在就加入贡献，往那边走；不存在就往另一边走即可。（贪心是因为$2^n>2^{n-1}+\cdots +2^0$）

最开始插入一个0，这样代码会好写很多。
Code：

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define maxn 400005
using namespace std;
inline void read(int &a){
    char c;while(!isdigit(c=getchar()));
    for(a=c-'0';isdigit(c=getchar());a=a*10+c-'0');
}
int n,a[maxn],s[maxn],f[maxn],g[maxn],ans;
int ch[maxn*30][2],tot;
void insert(int x){
    int r=0,v;
    for(int i=30;i>=0;i--,r=ch[r][v]) if(!ch[r][v=(x>>i&1)]) ch[r][v]=++tot;
}
int find(int x){
    int ret=0,r=0,v;
    for(int i=30;i>=0;i--,r=ch[r][v])
        if(ch[r][v=!(x>>i&1)]) ret+=1<<i;
        else if(ch[r][!v]) v=!v;
    return ret;
}
int main()
{
    read(n);
    for(int i=1;i<=n;i++) read(a[i]);
    insert(0);
    for(int i=1;i<=n;i++) s[i]=s[i-1]^a[i],f[i]=max(f[i-1],find(s[i])),insert(s[i]);
    memset(ch,0,sizeof ch);
    insert(0);
    for(int i=n;i>=1;i--) s[i]=s[i+1]^a[i],g[i]=max(g[i+1],find(s[i])),insert(s[i]);
    for(int i=1;i<n;i++) ans=max(ans,f[i]+g[i+1]);
    printf("%d",ans);
}

最后

以上就是朴素黑猫为你收集整理的BZOJ 4260: Codechef REBXOR 【Trie树贪心求区间异或和最值】的全部内容，希望文章能够帮你解决BZOJ 4260: Codechef REBXOR 【Trie树贪心求区间异或和最值】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。