当前位置:网站首页>bzoj4260: Codechef REBXOR(01Trie)

bzoj4260: Codechef REBXOR(01Trie)

2020-12-07 14:36:24 osc_r2jpynxi

题目传送门

解法:
01Trie。
听名字大概就知道怎么回事了。
自己yy了下也不知道对不对。。
问题大概就是:
很多个数,求他们异或某一个数的最大值。
我的建法是这样的:
每个数转化成二进制的01序列。
从最高位开始建01trie。跟普通trie差不多。只是一个点只有两个儿子的区别。
这里的最高位不是指数本身的最高位。而是最大数的最高位。
那么此题中范围为int。我把最高位设成了30位。









那么怎么求最大值呢。
因为异或是同为0不同为1。
那么每到一个位的时候就去问问相反的儿子有没有。
有的话这个位就为1,否则为0。


举个例子:
如果当前位为1。那么我们应该去找当前Trie上的位置有没有0。
有0的话那么这个位置异或后就为1,否则为0。

这样我们可以贪心出最大值。
对于此题:
异或和是满足加法的性质。
比如:sum[i]表示a[1]^a[2]^…a[i]。
那么sum[i]^sum[j]=a[j+1]^a[j+1]….a[i]。



这样我们就可以求出从每个点往左/右最大异或和。

然后O(n)求解就行了

代码实现:

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
struct node {
  
  int son[2];node(){son[0]=son[1]=-1;}}tr[15100000];int tot,root,a[410000],s[31];
void build() {
    int x=root;
    for(int i=30;i>=1;i--) {
        if(tr[x].son[s[i]]==-1) {tot++;tr[x].son[s[i]]=tot;}
        x=tr[x].son[s[i]];
    }
}
void get(int x) {
    int len=0;
    while(x!=0) {
  
  s[++len]=x%2;x/=2;}
    for(int i=len+1;i<=30;i++)s[i]=0;
}
int L[410000],R[410000];
int main() {
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    int sum=0;tot=root=0;
    for(int i=1;i<=n;i++) {
        sum^=a[i];get(sum);build();int x=root;
        int t=0;
        for(int j=30;j>=1;j--) {
            if(tr[x].son[1-s[j]]!=-1) {
  
  x=tr[x].son[1-s[j]];t=t*2+1;}
            else {
  
  x=tr[x].son[s[j]];t=t*2;}
        }L[i]=max(sum,t);
    }
    for(int i=0;i<=tot;i++)tr[i].son[1]=tr[i].son[0]=-1;
    root=tot=0;
    sum=0;
    for(int i=n;i>=1;i--) {
        sum^=a[i];get(sum);build();int x=root;
        int t=0;
        for(int j=30;j>=1;j--) {
            if(tr[x].son[1-s[j]]!=-1) {
  
  x=tr[x].son[1-s[j]];t=t*2+1;}
            else {
  
  x=tr[x].son[s[j]];t=t*2;}
        }R[i]=max(sum,t);
    }
    int l=L[1],ans=0;
    for(int i=2;i<=n;i++) {
        ans=max(ans,l+R[i]);l=max(l,L[i]);
    }printf("%d\n",ans);
    return 0;
}

版权声明
本文为[osc_r2jpynxi]所创,转载请带上原文链接,感谢
https://my.oschina.net/u/4416538/blog/4778629