给n个数

求异或前缀（从前连续取一些数全作异或）和异或后缀（从后连续取一些数全作异或）异或的最大值

好坑啊，指针好坑啊

第一道trie树

简单说下解法（其实壳还是不深）：

先异或所有数作为初始后缀

然后从前往后的数逐个从后缀出来，进入前缀，

在这个过程中，都把当前前缀变成二进制压入trie，然后当前后缀变成二进制从高位到低位尽量取和它数位不同的值，沿着trie往下走，得到一个最好的数，然后和后缀异或，维护最大值

简直了，指针就是坑

其实还是自己有点坑

说下遇到的坑吧

一开始没有全存64位数（导致可能一个长为30的后缀匹配出来的”最优“前缀长度为6什么的）

然后，我判断每个数位的时候是这样的 num&(1< >i)&1

还有，应该是把prefix压入trie，我却把number[i]压入trie

还有就是。。。1<<55是错的，应该是1LL<<55

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; #define MAX 5 typedef struct Trie { Trie *next[MAX]; long long v; //根据需要变化 }; Trie root; void createTrie(char *str) { long long len = strlen(str); Trie *p = &root, *q; for(long long i=0; i
       
        next[id] == NULL) { q = (Trie *)malloc(sizeof(Trie)); q->v = 1; //初始v==1 for(long long j=0; j
        
         next[j] = NULL; p->next[id] = q; p = p->next[id]; } else { p->next[id]->v++; p = p->next[id]; } } p->v = -1; //若为结尾，则将v改成-1表示 } long long findTrie(char *str) { long long len = strlen(str); Trie *p = &root; for(long long i=0; i
         
          next[id]; if(p == NULL) //若为空集，表示不存以此为前缀的串 return 0; if(p->v == -1) //字符集中已有串是此串的前缀 return -1; } return -1; //此串是字符集中某串的前缀 } long long dealTrie(Trie* T,bool isroot) { long long i; if(T==NULL) return 0; for(i=0;i
          
           next[i]!=NULL) dealTrie(T->next[i],false); } if(!isroot) free(T); return 0; } const long long NN=111111; long long f[NN]; #define SAVE 62 void get_bina(long long s,char* to){ long long que=0; for(long long i=SAVE;i>=0;i--){ to[que++]=((s>>i)&1)+'0';//应该是 (s>>i)&1 } to[que]='\0'; } int main(){ #ifndef ONLINE_JUDGE freopen("/home/rainto96/in.txt","r",stdin); #endif long long n;cin>>n; for(long long i=1;i<=n;i++){ cin>>f[i]; } long long prefix=0,postfix=0,ans=0; for(long long i=1;i<=n;i++) postfix^=f[i];//初始后缀 ans=postfix;//ans初始就是取所有后缀 for(long long i=1;i<=n;i++){ postfix^=f[i]; prefix^=f[i]; char tmp[99]; get_bina(prefix,tmp);//把当前前缀变成二进制 createTrie(tmp);//把当前前缀压入trie get_bina(postfix,tmp);//把当前后缀
           编程二进制 Trie* p =&root; long long len=strlen(tmp); long long get_num=0; ans=max(ans,postfix);//不取前缀 for(long long i=0;i<=SAVE;i++){//逐个取 long long want = 1 - (tmp[i]-'0');//最优匹配 if(p->next[want]==NULL){//如果没有最优匹配的 if(p->next[1-want]==NULL){//如果都没有，就是到了结尾 ans=max(ans,get_num^postfix); break; }else{//有不优匹配 p=p->next[1-want]; get_num=get_num*2+1-want; } }else{//有最优匹配 p=p->next[want]; get_num=get_num*2+want; } } ans=max(ans,get_num^postfix); } cout<