[USACO6.3.1 COWXOR] Trie 2进制分解

题目:

http://www.wzoi.org/usaco/16%5C107.asp

总的来说就是给定一个数列(n<=100000)。

求一段连续的子数列,使得其中的数都xor在一起以后,得到的值最大。

分析:

自己想的原创算法吖

首先我们先分析一下xor这个运算的性质。

易得y=y xor t xor t(即偶数次xor同一个数,结果和原来一样)

于是我们可以设s[i]表示从a[1]xor到a[i]的值。(定义s[0]=0)

如果我们需要某一段[i,j]的xor值,就可以这样求s[j] xor s[i-1],因为a[1]到a[i-1]的数被xor了两次!

这样,问题转化为:求max(s[i] xor s[j]),其中i∈[0,j],j∈[1,n]。

于是现在要求的是取两个数的xor值最大!

首先我们应该明白,对于一个数字,我们可以把它看成一个长度为20的字符串(题目给的a[i]<=2^21-1)!

那么我们怎么比较这些字符串的大小呢?

很明显,我们是从首位扫到末尾!

于是假设我们现在枚举j,即已经确定了s[j],然后在[0,j]的范围类找一个s[i] xor s[j]最大。

因为是当成字符串,我们用Trie树来储存那些数字!

然后从首位开始

1、如果我这个s[j]的这一位是0,那么另外一个配对最好是1,

因为这样xor会得到1。如果找不到那就只能到0那边去。

2、如果我这个s[j]的这一位是1,那么另外一个配对最好是0,

理由同上。

因为越前的位在大小上影响更大,所以我们这样就贪心的走一遍Trie树,

所得的结果就是和s[j]配对最大的s[i]。

然后统计每个j对应的最大值,输出结果即可。

HINT

UASCO给的空间比较小,用指针可以过,但静态空间的Trie就不能开到极限那么大,开小一点就能过。

code:

/*
ID:jie22221
TASK:cowxor
LANG:C++
*/
#include const int N=111111;
struct treetype{int l,r,dep;}T[5*N];
struct gtp{int x,y,next;}g[N];
int n,a[N],s[N],ans=-1,ansi=0,ansj=0,tot,root,e=0,ls[5*N];

void addedge(int x,int y){
       e++;
       g[e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=e;
}

void add(int &p,int x,int dep,int link){
     if (p==0){
       tot++;
       p=tot;
       T[p].l=0;
       T[p].r=0;
       T[p].dep=dep;
     }
     if (dep==-1){
       addedge(p,link);
       return;
     }
     if (((1<                     else add(T[p].l,x,dep-1,link);
}

void init(){
     scanf("%d",&n);
     for (int i=1;i<=n;i++) scanf("%d",&a[i]);
     for (int i=1;i<=n;i++){
         s[i]=s[i-1]^a[i];
         if (a[i]>ans){
           ans=a[i];
           ansi=i;
           ansj=i;
         }
         if (s[i]>ans){
           ans=s[i];
           ansi=1;
           ansj=i;
         }
     }
     tot=1;
     root=1;
     T[1].l=0;
     T[1].r=0;
     T[1].dep=22;
}

inline bool flag(int x,int y,int z){
       if (x>ans) return true;
       if (x       if (z       if (z>ansj) return false;
       if (z-y       return false;
}

void work(){
     add(root,s[1],22,1);
     for (int i=2;i<=n;i++){
         int p=root,now=0;
         for (int j=22;j>=0;j--)
           if ((s[i]|(1<               if (T[p].l!=0) {p=T[p].l; now|=1<                         else p=T[p].r;
             }
           else {
               if (T[p].r!=0) {p=T[p].r; now|=1<                         else p=T[p].l;
               }
           if (flag(now,g[ls[p]].y+1,i)){
              ans=now;
              ansi=g[ls[p]].y+1;
              ansj=i;
           }
         add(root,s[i],22,i);
     }
}

void print(){
     printf("%d %d %dn",ans,ansi,ansj);
}

int main(){
    freopen("cowxor.in","r",stdin);
    freopen("cowxor.out","w",stdout);
    init();
    work();
    print();
    return 0;
}

留下评论

您的电子邮箱地址不会被公开。